2 Preliminaries

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

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

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 [Reference Halverson10]. 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 [Reference Halverson10], 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 [Reference Halverson10] introduced a procedure for collecting partition diagrams so as to form analogues of conjugacy classes. Refer to [Reference Halverson10] for details. For a diagram d, we let $d_{\mu }$ denote the analogue of a conjugacy class representative, according to Halverson’s procedure [Reference Halverson10], 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 [Reference Halverson10], 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 [Reference Halverson10]

$$\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.

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 [Reference Halverson10] 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 [Reference Halverson and Ram11, p. 884]. This Bratteli diagram $\hat {A}$ is defined and illustrated in Halverson and Ram’s seminal article on partition algebras [Reference Halverson and Ram11, 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 $ .

Proof Suppose that $\mu $ is a weak composition such that $0 \leq |\mu | \leq n$ . By Corollary 4.2.3 from [Reference Halverson10], 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 [Reference Halverson10] 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, [Reference Marcott20, 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 [Reference Rhoades and Skandera29], 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 [Reference Halverson10], 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 [Reference Orellana and Zabrocki25] 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 [Reference Orellana and Zabrocki25] 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 [Reference Rhoades and Skandera28] are f-immanants defined in a way related to Temperley–Lieb algebras, referring to [Reference Rhoades and Skandera28] for details. It seems that past research influenced by [Reference Rhoades and Skandera28], including relevant research on immanants or immanant-type functions as in [Reference de Guise, Spivak, Kulp and Dhand3, Reference Pylyavskyy27, Reference Rhoades and Skandera29, Reference Rhoades and Skandera30], 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 [Reference Itoh14] 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 [Reference Itoh14]?