A generalization of immanants based on partition algebra characters

Abstract

We introduce a generalization of immanants of matrices, using partition algebra characters in place of symmetric group characters. We prove that our immanant-like function on square matrices, which we refer to as the recombinant, agrees with the usual definition for immanants for the special case whereby the vacillating tableaux associated with the irreducible characters correspond, according to the Bratteli diagram for partition algebra representations, to the integer partition shapes for symmetric group characters. In contrast to previously studied variants and generalizations of immanants, as in Temperley–Lieb immanants and f-immanants, the sum that we use to define recombinants is indexed by a full set of partition diagrams, as opposed to permutations.

1 Introduction

The concept of the immanant of a matrix was introduced in a seminal 1934 article by Littlewood and Richardson [19]. As suggested by Littlewood and Richardson [19], by generalizing determinants and permanents of matrices using symmetric group characters, this provides a way of unifying disparate areas of combinatorial analysis, linear algebra, and representation theory. Since partition algebras are such natural extensions of symmetric group algebras [11], this leads us to consider how immanants of matrices may be generalized using partition algebra characters. This forms the main purpose of our article, in which we introduce the concept of the recombinant of a matrix. This gives us a generalization of immanants that is separate from the concept of an f-immanant.

Given an $n \times n$ matrix

(1.1) $$ \begin{align} A = \left( a_{i, j} \right)_{n \times n} = \left( \begin{matrix} a_{1, 1} & a_{1, 2} & \cdots & a_{1, n} \\ a_{2, 1} & a_{2, 2} & \cdots & a_{2, n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n, 1} & a_{n, 2} & \cdots & a_{n, n} \end{matrix} \right), \end{align} $$

the Leibniz identity for determinants is as below:

(1.2) $$ \begin{align} \mathrm{det}(A) = \sum_{\sigma \in S_{n}} \left( \mathrm{sgn}(\sigma) \prod_{i=1}^{n} a_{i, \sigma_{i}} \right), \end{align} $$

letting $S_{n}$ denotes the group of all permutations of $\{ 1, 2, \ldots , n \}$ . The permanent of (1.1) is defined by replacing the sign function in (1.2) as below:

(1.3) $$ \begin{align} \mathrm{perm}(A) = \sum_{\sigma \in S_{n}} \prod_{i = 1}^{n} a_{i, \sigma_{i}}. \end{align} $$

The matrix functions in (1.2) and (1.3) are special cases of the immanant function defined in [19] and as below.

An integer partition is a finite tuple $\lambda $ of nonincreasing natural numbers. If the sum of all of the entries of $\lambda $ is a natural number n, then $\lambda $ is said to be a partition of n, and this is denoted as $\lambda \vdash n$ . For $\lambda \vdash n$ , we may let $\chi _{S_n}^{\lambda }$ be the irreducible character that is of the symmetric group $S_n$ and that corresponds to $\lambda $ . The immanant $\mathrm {Imm}^{\lambda }$ of (1.1) may be defined so that

(1.4) $$ \begin{align} \mathrm{Imm}^{\lambda}(A) = \sum_{\sigma \in S_{n}} \chi^{\lambda}_{S_{n}}(\sigma) \prod_{i = 1}^{n} a_{i, \sigma_{i}}. \end{align} $$

We find that the $\lambda = (1^{n})$ case of (1.4) agrees with (1.2) and the $\lambda = (n)$ case of (1.4) agrees with (1.3). The purpose of this article is to generalize (1.2), (1.3), and (1.4) using partition algebra characters, as opposed to symmetric group characters.

Immanants are of interest within many different areas of advanced linear algebra (see, for example, [2, 4, 5, 8, 12, 13, 15, 18, 26, 32] and many related references). The definition of immanants in terms of the irreducible characters of the symmetric group naturally lends itself to applications related to many different areas of algebraic combinatorics (see, for example, [1, 6, 7, 9, 17, 31] and many similar references). The foregoing considerations reflect the interdisciplinary nature about immanants and motivate our generalization of immanants.

Let V denote an r-dimensional vector space. Let the general linear group $\mathrm {GL}_{r}(\mathbb {C})$ act on the tensor space $V^{\otimes n}$ diagonally. By taking $S_{r}$ as a subgroup of $\mathrm {GL}_{r}(\mathbb {C})$ and restricting the action of $\mathrm {GL}_{r}(\mathbb {C})$ to permutation matrices, partition algebras may be defined via the centralizer algebra

(1.5) $$ \begin{align} P_{n}(r) \cong \mathrm{End}_{S_{r}}\left(V^{\otimes n}\right). \end{align} $$

The study of partition algebras was developed in the field of statistical mechanics via the centralizer algebra in (1.5), with reference to the work of Jones [16] and Martin [21–24]. This again speaks to the interdisciplinary interest surrounding our generalization of immanants via partition algebra characters.

2 Preliminaries

Our notation concerning partition algebras is mainly borrowed from Halverson’s article on the character theory for partition algebras [10].

Definition 2.1 A partition diagram is the equivalence class of a simple graph with $2n$ vertices labeled with $\{ 1, 2, \ldots , n, 1', 2', \ldots , n' \}$ , where two such graphs are considered to be equivalent if the connected components are the same.

A partition diagram d is often denoted with any simple graph in the equivalence class d, and in such a way so that the vertices labeled with $1$ , $2$ , $\ldots $ , n are arranged into a top row and the vertices labeled with $1'$ , $2'$ , $\ldots $ , $n'$ are arranged into a bottom row. A given partition diagram d may also be denoted with the set-partition given by the connected components of any graph in the equivalence class d. We let it be understood that we may identify a partition diagram d with any graph in the equivalence class d.

Example 2.1 The partition diagram associated with the set-partition $\{ \{ 4'$ , $ 4 \}$ , $ \{ 3' \}$ , $ \{ 2'$ , $1$ , $2$ , $3 \}$ , $ \{ 1' \} \}$ may be denoted as

(2.1)

and as

Definition 2.2 The propagation number of a partition diagram d refers to the number of connected components of d with at least one upper vertex and at least one lower vertex.

Example 2.2 The propagation number of the partition diagram shown in (2.1) is $2$ .

We let $P_{n}(r)$ denote the $\mathbb {C}$ -span of all order-n partition diagrams, and we endow this space with the multiplicative operation specified in [10]. Structures of this form are referred to as partition algebras. We find that the symmetric group algebra of order n spanned by $\mathbb {C}$ is naturally a subalgebra, by taking the span of partition diagrams of order n and of propagation number n.

For integer partitions $\lambda $ and $\mu $ , if $\mu _{i} \leq \lambda _{i}$ for all i, then $ \lambda / \mu $ denotes the skew shape obtained by removing $\mu $ from $\lambda $ . We let $P_{n-1}(r)$ be embedded in $P_{n}(r)$ by adding vertices labeled with n and $n'$ and by letting these vertices be adjacent. From the branching rules subject to the restriction from $P_{n}(r)$ to $P_{n-1}(r)$ , and with the use of double centralizer theory via (1.5), it can be shown that the irreducible representations of $P_{n}(r)$ are in bijection with

(2.2) $$ \begin{align} \widehat{P_{n}(r)} = \{ \lambda \vdash r \ : \ |\lambda^{\ast}| \leq n \}, \end{align} $$

where $\lambda ^{\ast } = \lambda / (\lambda _{1})$ .

We let $M^{\lambda }$ denote the irreducible representation of $P_{n}(r)$ indexed by $\lambda \in \widehat {P_{n}(r)}$ . Following [10], we establish a bijection between (2.2) and the set $ \widehat {P_{n}} $ consisting of all expressions of the form $\lambda ^{\ast }$ in (2.2), i.e., by mapping $\lambda $ to $\lambda ^{\ast }$ and, conversely, by adding a row to $\lambda ^{\ast }$ appropriately. For $\lambda \in \widehat {P_{n}(r)}$ , we may let $\chi _{P_{n}(r)}^{\lambda }$ denote the irreducible character of $P_{n}(r)$ corresponding to $M^{\lambda }$ .

A basic result in the representation theory of groups is that characters are constant on conjugacy classes. Halverson [10] introduced a procedure for collecting partition diagrams so as to form analogues of conjugacy classes. Refer to [10] for details. For a diagram d, we let $d_{\mu }$ denote the analogue of a conjugacy class representative, according to Halverson’s procedure [10], such that $ \chi (d) $ and $ \chi (d_{\mu })$ are equal up to a power of r in $P_{n}(r)$ , for a given partition algebra character $\chi $ .

Following Halverson’s construction [10], we set $\gamma _{1} = 1$ , and, for $t> 1$ , we set $\gamma _{t}$ as the partition diagram corresponding to the set-partition $\{ \{ 1, 2' \}, \{ 2, 3' \}, \ldots , \{ t-1, t' \}, \{ t, 1' \} \}$ .

Example 2.3 The order- $5$ partition diagram $\gamma _{5}$ is

The operation $\otimes $ on partition diagrams is such that: For partition diagrams $d_{1}$ and $d_{2}$ of orders $n_{1}$ and $n_{2}$ , the concatenation $d_{1} \otimes d_{2}$ is the partition diagram of order $n_1 + n_2$ given by positioning $d_{2}$ to the right of $d_{1}$ . A weak composition $\mu $ of a nonnegative integer k is a finite tuple of nonnegative integers that sum to k. For a weak composition $\mu = (\mu _{1}, \mu _{2}, \ldots , \mu _{\ell (\mu )})$ of k, we may write $|\mu |$ in place of k. For $|\mu |> 0$ , we write

(2.3) $$ \begin{align} \gamma_{\mu} = \gamma_{\mu_{\iota(1)}} \otimes \gamma_{\mu_{\iota(2)}} \otimes \cdots \otimes \gamma_{\mu_{\iota(\kappa)}}, \end{align} $$

where the sequence of indices for $\gamma $ -expressions on the right of (2.3) is such that $\iota (1) < \iota (2) < \cdots < \iota (\kappa )$ and where $\{ \iota (1), \iota (2), \ldots , \iota (\kappa ) \}$ consists of the indices i such that $\mu _{i}$ is positive. Letting $E_{1}$ denote the partition diagram in $P_{1}(r)$ without any edges, and letting $|\mu | \leq n$ , we borrow Halverson’s notation [10]

$$\begin{align*}d_{\mu} = \gamma_{\mu} \otimes \underbrace{E_{1} \otimes E_{1} \otimes \cdots \otimes E_{1}}_{n - |\mu|}, \end{align*}$$

letting it be understood that $\gamma _{\mu }$ denotes the empty diagram for the trivial case such that $|\mu | = 0$ .

3 A generalization of immanants

For a permutation p of order n that we denote as a function

(3.1) $$ \begin{align} p\colon \{ 1, 2, \ldots, n \} \to \{ 1, 2, \ldots, n \}, \end{align} $$

we identify this permutation with the partition diagram corresponding to $\{ \{ 1, (p(1))' \}$ , $ \{ 2, (p(2))' \}$ , $ \ldots $ , $ \{ n, (p(n))' \} \}$ . We then consider this partition diagram as being associated with the product

(3.2) $$ \begin{align} \prod_{i=1}^{n} a_{i, p(i)}, \end{align} $$

for the matrix A in (1.1), and with regard to the summand in (1.4). So, this raises the question as to what would be appropriate as an analogue of the product in (3.2), for an arbitrary partition diagram. This leads us toward the following.

Definition 3.1 For the $n \times n$ matrix in (1.1), we let the product $ \prod _{d} a_{i, j}$ or $ \prod _{d} A$ be defined in the following manner. If d is of propagation number $0$ , then we let the expression $\prod _{d} a_{i, j}$ vanish. If d is of a positive propagation number, let B be a component of d that is propagating. We then form the product of all expressions of the form $a_{i, j}$ such that i is in B and $j'$ is in B. Let $ \Pi _{B}$ denote this product we have defined using the component B. We then define $\prod _{d} a_{i,j}$ as the product of all expressions of the form $\Pi _{B}$ for all propagating components B of d.

Example 3.1 For the partition diagram

and for the $5 \times 5$ case of (1.1), we find that

$$ \begin{align*}\prod_{d} a_{i, j} = \prod_{d} A = \left( a_{2,1} a_{2,2} a_{2, 3} \right) \left( a_{3, 4} a_{3, 5} a_{5, 4} a_{5, 5} \right).\end{align*} $$

Definition 3.1 puts us in a position to offer a full definition for the concept of the recombinant of a matrix, as below.

Definition 3.2 Let $\lambda $ be an integer partition of r such that $|\lambda ^{\ast }| \leq n$ . We define the recombinant of the $n \times n$ matrix in (1.1) so that

(3.3) $$ \begin{align} \mathrm{Rec}^{\lambda}(A) = \sum_{d} \chi_{P_{n}(r)}^{\lambda}(d) \prod_{d} a_{i, j}, \end{align} $$

where the sum in (3.3) is over all partition diagrams in $P_{n}(r)$ .

Example 3.2 Let $\mathrm {Rec}^{0}$ denote the recombinant corresponding to irreducible partition algebra submodules spanned by linear combinations of partition diagrams of propagation number $0$ . Correspondingly, we let the irreducible characters be written as $\chi ^{0}$ . According to Definition 3.2, by writing

$$ \begin{align*} & \mathrm{Rec}^{0}\left( \begin{matrix} a_{1, 1} & a_{1, 2} \\ a_{2, 1} & a_{2, 2} \end{matrix}\right) = \sum_{d} \chi^{0}(d) \prod_{d} a_{i, j} \\ & = \chi^{0}(d_{1}) \prod_{d_{1}} a_{i, j} + \chi^{0}(d_{2}) \prod_{d_{2}} a_{i, j} + \cdots + \chi^{0}(d_{15}) \prod_{d_{15}} a_{i, j} \end{align*} $$

according to the ordering shown in Table 1, we may evaluate the recombinant $\mathrm {Rec}^{0}$ according to the character values shown in Table 1, so as to obtain that

$$ \begin{align*} \mathrm{Rec}^{0}\left( \begin{matrix} a_{1, 1} & a_{1, 2} \\ a_{2, 1} & a_{2, 2} \end{matrix}\right) & = a_{1, 1} a_{1, 2} a_{2, 1} a_{2, 2} + \\ &\quad a_{1, 1} a_{2, 1} + a_{1, 1} a_{1, 2} + a_{1, 2} a_{2, 2} + a_{2, 1}a_{2, 2} + \\ &\quad 2 \left( a_{1, 1}a_{2, 2} + a_{1, 2} a_{2, 1} \right) + \\ &\quad r \left( a_{1, 1} + a_{1, 2} + a_{2, 1} + a_{2, 2} \right). \end{align*} $$

We may verify the above evaluation by computing the traces associated with the linear transforms given by the action of left-multiplication by diagram basis elements on the irreducible $P_{2}(r)$ -module $\mathscr {L}\{ d_{4}, d_{14} \}$ .

Table 1 The SageMath ordering for partition diagrams of order $2$ , along with the irreducible character evaluations corresponding to a non-propagating submodule.

Since our article is based on generalizing immanants using partition algebra characters, it would be appropriate to prove, as below, that Definition 3.2 does indeed generalize (1.4). In our below proof, we will make use of the property described by Halverson [10] whereby character tables for partition algebras satisfy a recursion of the form

(3.4) $$ \begin{align} \Xi_{P_{n}(r)} = \left[ \begin{matrix} r \Xi_{P_{n-1}(r)} & \vdots & \ast \\ \cdots & & \cdots \\ 0 & \vdots & \Xi_{S_{n}} \end{matrix} \right], \end{align} $$

where $ \Xi _{S_{n}} $ denotes the character table of $S_{n}$ .

By direct analogy with how Young tableaux are formed from paths in Young’s lattice, vacillating tableaux are formed from paths in a Bratteli diagram associated with partition algebras [11, p. 884]. This Bratteli diagram $\hat {A}$ is defined and illustrated in Halverson and Ram’s seminal article on partition algebras [11, pp. 883–884]. For the case whereby such a path ends on an integer partition of order n at level n in $ \hat {A}$ , this corresponds to an embedding of an irreducible representation of $\mathbb {C}S_n$ . For a vacillating tableau T of this form, Theorem 3.3 gives us that the recombinant corresponding to the partition algebra representation $\rho $ corresponding to T is the same as the immanant corresponding to the symmetric group algebra representation corresponding to $\rho $ .

Theorem 3.3 Let $\lambda $ be an integer partition of r such that $|\lambda ^{\ast }| \leq n$ . For an $n \times n$ matrix A, if $|\lambda ^{\ast }| = n$ , then $\mathrm {Rec}^{\lambda }(A) = \mathrm {Imm}^{\lambda ^{\ast }}(A)$ .

Proof Suppose that $\mu $ is a weak composition such that $0 \leq |\mu | \leq n$ . By Corollary 4.2.3 from [10], we have that

(3.5) $$ \begin{align} \chi_{P_{n}(r)}^{\lambda}\left( d_{\mu} \right) = 0 \ \ \ \mathrm{if}\ |\mu| < |\lambda^{\ast}|, \end{align} $$

and that the equality $|\mu | = |\lambda ^{\ast }| = n$ implies that

(3.6) $$ \begin{align} \chi_{P_{n}(r)}^{\lambda}\left( d_{\mu} \right) = \chi_{S_{n}} ^{\lambda^{\ast}}\left( \gamma_{\mu} \right). \end{align} $$

For a permuting diagram d, Halverson’s procedure for conjugacy class analogues [10] gives us that $\gamma _{\mu }$ and d are conjugate as permutations. So, for an $n \times n$ matrix A and for $|\lambda ^{\ast }| = n$ , we find, from (3.5), that $\chi _{P_{n}(r)}^{\lambda }(d)$ vanishes for all non-propagating partition diagrams d, as in the lower left block of the character table in (3.4), so that we may rewrite (3.3) so that

(3.7) $$ \begin{align} \mathrm{Rec}^{\lambda}(A) = \sum_{\mathrm{prop}(d) = n} \chi_{P_{n}(r)}^{\lambda}(d) \prod_{d} a_{i, j}, \end{align} $$

and where the character $ \chi _{P_{n}(r)}^{\lambda }(d) $ reduces, in the manner specified in (3.6), to the corresponding character of $S_{n}$ evaluated at the permutation corresponding to the permuting diagram d. By Definition 3.1, the product $\prod _{d} a_{i, j}$ in (3.7) is equal to $a_{1, d(1)} a_{2, d(2)} \dots a_{n, d(n)}$ , writing the permuting diagram d as a permutation as in (3.1).

Remark 3.4 Let us write $E_{\ell }$ to denote the partition diagram corresponding to

$$ \begin{align*}\frac{1}{r} \{ \{ 1, 1' \}, \{ 2, 2' \}, \ldots, \{ \ell - 1, (\ell - 1)' \}, \{ \ell, \ell + 1, \ldots, n \}, \{ \ell', (\ell + 1)', \ldots, n' \} \}.\end{align*} $$

We find that $P_{n}(r) E_{\ell } P_{n}(r)$ is a two-sided ideal and consists of all linear combinations of partition diagrams with propagation number strictly less than $\ell $ . Fundamental results in the representation theory of partition algebras are such that

(3.8) $$ \begin{align} \mathbb{C}S_n \cong P_{n}(r) / \left( P_{n}(r) E_{n} P_{n}(r) \right) \end{align} $$

and such that any irreducible representation of $P_{n}(r)$ is either an irreducible representation of $E_{n} P_{n}(r) E_{n}$ or an irreducible representation of the right-hand side of (3.8) (see, for example, [20, Section 4] and the references therein). These properties can be used to formulate an alternative proof of Theorem 3.3.

Our generalization of immanants, as above, is fundamentally different compared to previously considered generalizations or variants of the immanant function. Notably, Definition 3.2 is separate relative to how f-immanants are defined. Following [29], an f-immanant, by analogy with (1.4), is of the form

(3.9) $$ \begin{align} \mathrm{Imm}^{f}(A) = \sum_{\sigma \in S_{n}} f(\sigma) \prod_{i=1}^{n} a_{i, \sigma_{i}} \end{align} $$

for an arbitrary function $f\colon S_{n} \to \mathbb {C}$ . A notable instance of an f-immanant that is not of the form indicated in (1.4) is the Kazhdan–Lusztig immanant, where the f-function in (3.9) is given by Kazhdan–Lusztig polynomials associated with certain permutations. In contrast to generalizations of immanants of the form shown in (3.9), our lifting of the definition in (1.4) is based on a sum indexed by the diagram basis of $P_{n}(r)$ , in contrast to the index set for the sum in (3.9). In contrast to immanants of $n \times n$ matrices being in correspondence with integer partitions of n, and in contrast to f-immanants of $n \times n$ matrices being in correspondence with class functions on $S_{n}$ , we have that recombinants of $n \times n$ matrices are in correspondence with the family of integer partitions in (2.2).

4 Future research

We conclude with some areas for future research concerning the matrix function introduced in this paper.

Immanants are often applied in the field of algebraic graph theory, via immanants of Laplacian matrices and the like. How could recombinants be applied similarly?

Immanants of Toeplitz matrices are often studied due to recursive properties of such immanants. What is the recombinant of a given Toeplitz matrix?

A fundamental formula in algebraic combinatorics is Frobenius’ formula for irreducible characters of the symmetric group, which, following [10], was later shown by Schur to be a consequence of what is now known as Schur–Weyl duality between symmetric groups and general linear groups. The irreducible character basis introduced in [25] may be defined via a lifting of the consequence

(4.1) $$ \begin{align} p_{\mu} = \sum_{\lambda \vdash n} \chi_{S_{n}}^{\lambda}(\mu) s_{\lambda} \end{align} $$

of Schur–Weyl duality, with partition algebra characters used in place of symmetric group characters in an analogue of (4.1). The SageMath implementation of the $\tilde {s}$ -basis from [25] provides a useful way of computing partition algebra characters, which could be used to obtain a useful way of computing recombinants. We encourage applications of this.

Temperley–Lieb algebras form an important family of subalgebras of partition algebras. The Temperley–Lieb immanants introduced by Rhoades and Skandera [28] are f-immanants defined in a way related to Temperley–Lieb algebras, referring to [28] for details. It seems that past research influenced by [28], including relevant research on immanants or immanant-type functions as in [3, 27, 29, 30], has not involved any generalizations of immanants using partition algebra characters. It may be worthwhile to explore relationships among recombinants and Temperley–Lieb immanants, or to explore generalizations or variants of recombinants related to the way Temperley–Lieb immanants are defined.

The concept of a twisted immanant was introduced in [14] and was based on how the irreducible character $\chi ^{\lambda }$ , if restricted to an alternating subgroup, splits as a sum of two irreducible characters, writing $\chi ^{\lambda } = \chi ^{\lambda _{+}} + \chi ^{\lambda _{-}}$ . What would be an appropriate notion of a twisted recombinant, and how could this be applied in a similar way, relative to [14]?