Immanant

In connection with his work on the representation theory of groups (cf. also Schur functions in algebraic combinatorics), I. Schur introduced the following class of matrix functions. For a character $\chi$ of a subgroup $G$ of the symmetric group $S _ { n }$ (cf. also Symmetric group; Character of a group), the associated generalized matrix function $d _ { \chi } ^ { G } : \mathbf{C} ^ { n \times n } \rightarrow \mathbf{C}$ acts on the $( n \times n )$-matrix $A = [ a _ {i j } ]$ by

\begin{equation*} d _ { \chi } ^ { G } ( A ) : = \sum _ { \sigma \in G } \chi ( \sigma ) \prod _ { i = 1 } ^ { n } a _ {i \sigma ( i ) }. \end{equation*}

When $G = S _ { n }$ and $\chi = \chi _ { \lambda }$ is an irreducible character of $S _ { n }$ indexed by the partition $\lambda$ of $n$, D.E. Littlewood [a25], Chap. VI, called the matrix function $d _ { \chi _ { \lambda } } ^ { S _ { n } }$ an immanant. He used the immanants of certain matrices whose entries are symmetric functions to define the Schur functions (cf. also Schur functions in algebraic combinatorics). The immanant $d _ { \chi _ { \lambda } } ^ { S _ { n } }$ is also denoted by the less cumbersome notation $d \lambda$.

The familiar determinant and permanent functions of a matrix are examples of immanants, and they correspond to the immanants associated with the alternating, respectively the trivial, character of $S _ { n }$. Indeed, for a matrix $A = [ a _ {i j } ]$,

$$ d_{(1^n)}(A) = \det (A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i\sigma(i)}, $$

where the signature $\operatorname { sgn } ( \sigma ) = 1$ if $\sigma$ is an even permutation and $- 1$ otherwise (cf. also Permutation), and

\begin{equation*} d _{( n )} ( A ) = \operatorname { per } ( A ) = \sum _ { \sigma \in S _ { n } } \prod _ { i = 1 } ^ { n } a _ { i \sigma ( i ) }. \end{equation*}

Given the plethora of inequalities and identities that involve the determinant and permanent functions, it is natural to seek generalizations of these relations to other immanants. For instance, in 1918 Schur [a40] obtained the following spectacular generalization of the Hadamard–Fischer inequality for positive semi-definite Hermitian matrices.

Schur's inequality: Let $\chi$ be a character of the subgroup $G$ of $S _ { n }$ and let $\operatorname{id}$ be the identity permutation. For a positive semi-definite Hermitian matrix $A$ one has

\begin{equation} \tag{a1} d _ { \chi } ^ { G } ( A ) \geq \chi ( \text { id } ) \operatorname { det } ( A ). \end{equation}

If one defines the normalized immanant $\overline { d } _ { \chi } ^ { G }$ to be

\begin{equation*} \overline { d } _ { \chi } ^ { G } ( A ) : = d _ { \chi } ^ { G } ( A ) / \chi ( \text { id } ) = d _ { \chi } ^ { G } ( A ) / d _ { \chi } ^ { G } ( I _ { n } ) , \end{equation*}

where $ { I } _ { n }$ is the identity $( n \times n )$-matrix, then Schur's inequality (a1) may be written as

\begin{equation*} \overline { d } _ { \chi } ^ { G } ( A ) \geq \operatorname { det } ( A ) = \overline { d } _ { ( 1 ^ { n } )} ( A ). \end{equation*}

The permanental analogue of the Hadamard inequality for the determinant of a positive semi-definite Hermitian matrix was obtained by M. Marcus [a26] in 1963, when he showed that for any positive semi-definite Hermitian matrix $A = [ a _ {i j } ]$,

\begin{equation*} \operatorname { per } ( A ) \geq \prod _ { i = 1 } ^ { n } a _ { i i } . \end{equation*}

In 1966, Marcus' inequality was generalized by E.H. Lieb [a24], who showed that for a positive semi-definite Hermitian matrix $A$ that is partitioned in the form $A = \left( \begin{array} { c c } { B } & { C } \\ { C ^ { * } } & { D } \end{array} \right)$, where $C ^ { * } = \overline { C ^ { T } }$ denotes the transpose conjugate of $C$, one has

\begin{equation*} \operatorname { per } ( A ) \geq \operatorname { per } ( B ) \operatorname { per } ( D ) \geq \prod _ { i = 1 } ^ { n } a _ { i i }. \end{equation*}

In the same paper [a24], the following permanental analogue of Schur's inequality was conjectured.

The permanental dominance conjecture, or permanent-on-top conjecture (POT conjecture), states that for all positive semi-definite Hermitian matrices $A$,

\begin{equation} \tag{a2} \overline { d } _{(n)} ( A ) = \operatorname { per } ( A ) \geq \overline { d } _ { \lambda } ( A ). \end{equation}

More generally, given two irreducible characters $\chi_{ \lambda}$ and $\chi _ { \mu }$ of $S _ { n }$, one writes $\chi _ { \lambda } \preceq \chi _ { \mu }$ if $\overline { d } _ { \lambda } ( A ) \leq \overline { d } _ { \mu } ( A )$ for all positive semi-definite Hermitian matrices $A$. This gives a partial order on the characters and also the immanants. In this context, Schur's inequality says that the alternating character $\chi_{ ( 1 ^ { n } )}$ is the smallest element of the resulting partially ordered set and the permanent-on-top conjecture asserts that the trivial character $\chi _ {( n )}$ is the largest element. A clear exposition on this topic can be found in [a33], Chap. 7.

There was little work done in this area before the appearance of a series of papers [a13], [a19], [a20], [a22], [a28] by several authors in the mid 1980s. These papers provide a partial resolution to the conjectured inequality in (a2), by showing that the permanent dominates the immanants associated with various characters. Since then there has been much progress; see, e.g., [a14], [a15], [a23], [a31], [a41]; and especially [a17], [a18], [a21], [a34], [a35], [a36], [a37], [a38], [a39], for the nature of the partial order on the characters. For instance, P. Heyfron [a17] proved that the hook immanants $\overline { d } _ { ( k , 1 ^ { n - k } ) }$ are ordered as

\begin{equation} \tag{a3} \overline { d } _ { ( 1 ^ { n } ) } \preceq \overline { d } _ { ( 2,1 ^ { n - 2 } ) } \preceq \ldots \preceq \overline { d } _ { ( k , 1 ^ { n - k } ) } \preceq \ldots \preceq \overline { d } _ { ( n ) }. \end{equation}

The ordering in (a3) is part of a more general result of Th.H. Pate [a34] saying that if $\lambda = ( \lambda _ { 1 } , \dots , \lambda _ { s } , \dots , \lambda _ { t } )$ is a non-increasing partition of $n$ with $\lambda _ { s } > \operatorname { max } \{ \lambda _ { s +1 } ,1 \}$ and $\lambda ^ { \prime } = ( \lambda _ { 1 } , \dots , \lambda _ { s } - 1 , \lambda _ { s + 1 } , \dots , \lambda _ { t } , 1 )$, then $\chi _ { \lambda ^ { \prime } } \preceq \chi _ { \lambda }$. The POT conjecture has been established for all $n \leq 15$ with the exception of the three partitions $( 4 ^ { 2 } , 3 ^ { 2 } )$, $( 3 ^ { 5 } )$ and $( 5,4,3 ^ { 2 } )$ by Pate in [a39]. The article [a39] gives a good survey of the results related to the POT conjecture and also discusses some topics related to immanants. In [a41], G.W. Soules considered an alternative approach to the POT conjecture through the eigenvalues of the Schur power matrix. In a similar vein, R. Merris [a31] investigated the extent to which the POT conjecture depends on the theory of group representations.

Immanants of other families of matrices besides the positive semi-definite Hermitian matrices have been studied. In [a11] I.P. Goulden and D.M. Jackson studied immanants of Jacobi–Trudi matrices and incidence matrices of directed trees. Their work inspired further results and conjectures about immanants of Jacobi–Trudi matrices and totally positive matrices, see, e.g., [a12], [a16], [a42], [a44].

Immanants of combinatorial matrices, such as the Laplacian matrix of graphs, have been considered in [a2], [a5], [a7], [a32]. Given a graph $G$ on $n$ vertices $\{ v _ { 1 } , \dots , v _ { n } \}$, the Laplacian matrix $L ( G ) = [ l_{ij} ]$ of $G$ is the $( n \times n )$-matrix whose diagonal element $l _ { i i }$ is the degree of the vertex $v_i$ and for $i \neq j$, $I_{i j} = - 1$ or $0$ according to whether $v_i$ and $v _ { j }$ are adjacent or not. Given two graphs $G_1$ and $G_2$ on $n$ vertices, it is of interest to determine the set of immanants $d \lambda$ for which $d_{\lambda} ( L ( G _ { 1 } ) ) \leq d _ { \lambda } ( L ( G _ { 2 } ) )$. See [a2], [a7], for a characterization of the trees in various families that attain the smallest immanant values. See [a6] for a linear relation between the third hook immanant $d _ { ( 3,1 ^ { n - 3 } ) } ( L ( T ) )$ of the tree $T$ and the chemical index, called the Wiener number of $T$. The relation between $d _ { ( 3,1 ^ { n - 3 } ) } ( L ( T ) )$ and other chemical indices is explored in [a4]. The results of Ph. Botti and Merris in [a1] show that immanants of Laplacian matrices of trees do not distinguish non-isomorphic trees in general. More specifically, almost every tree shares the same set of immanant values with another non-isomorphic tree on the same number of vertices.

Linear transformations of a matrix that preserve its immanant values have been investigated in [a8], [a9], [a10]. When an indeterminate $x$ is introduced, the immanant $d _ { \lambda } ( x I _ { n } - A )$ may be expanded as a polynomial in $x$ of degree $n$. This polynomial is known as the immanantal polynomial of $A$. The immanantal polynomials of graph Laplacians have been studied in [a1], [a29], [a30], [a27], [a45]. Computational issues related to the evaluation of immanants are considered in [a3].

References

[a1]	Ph. Botti, R. Merris, "Almost all trees share a complete set of immanantal polynomials" J. Graph Th. , 17 : 4 (1993) pp. 467–476
[a2]	R.A. Brualdi, J.L. Goldwasser, "Permanent of Laplacian matrix of trees and bipartite graphs" Discr. Math. , 48 (1984) pp. 1–21
[a3]	P. Bürgisser, "The computational complexity of immanants" SIAM J. Comput. (to appear)
[a4]	O. Chan, I. Gutman, Tao-Kai Lam, R. Merris, "Algebraic connections between topological indices" J. Chemical Inform. & Computer Sci. , 38 : 1 (1998) pp. 62–65
[a5]	O. Chan, T.K. Lam, "Hook immanantal inequalities for trees explained" Linear Alg. & Its Appl. , 273 (1998) pp. 119–131
[a6]	O. Chan, T.K. Lam, R. Merris, "Wiener number as an immanant of the Laplacian of molecular graphs" J. Chemical Inform. & Computer Sci. , 37 : 4 (1997) pp. 762–765
[a7]	O. Chan, T.K. Lam, "Immanant inequalities for Laplacians of trees" SIAM J. Matrix Anal. Appl. , 21 : 1 (1999) pp. 129–144
[a8]	M.P. Coelho, M.A. Duffner, "Linear preservers of immanants on symmetric matrices" Linear Alg. & Its Appl. , 255 (1997) pp. 315–334
[a9]	M.A. Duffner, "Linear transformations that preserve immanants" Linear Alg. & Its Appl. , 197/198 (1994) pp. 567–588
[a10]	M. Do Rosario Fernandes, "Pairs of matrices that have the same immanant" Linear and Multilinear Algebra , 40 (1996) pp. 193–201
[a11]	I.P. Goulden, D.M. Jackson, "Immanants of combinatorial matrices" J. Algebra , 148 (1992) pp. 305–324
[a12]	C. Greene, "Proof of a conjecture on immanants of the Jacobi–Trudi matrix" Linear Alg. & Its Appl. , 171 (1992) pp. 65–79
[a13]	R. Grone, "An inequality for the second immanant" Linear and Multilinear Algebra , 18 (1985) pp. 147–152
[a14]	R. Grone, R. Merris, "A Hadamard inequality for the third and fourth immanants" Linear and Multilinear Algebra , 21 (1987) pp. 201–209
[a15]	R. Grone, R. Merris, W. Watkins, "A Hadamard dominance theorem for a class of immanants" Linear and Multilinear Algebra , 19 (1986) pp. 167–171
[a16]	M. Haiman, "Hecke algebra characters and immanant conjectures" J. Amer. Math. Soc. , 6 (1993) pp. 569–595
[a17]	P. Heyfron, "Immanant dominance orderings for hook partitions" Linear and Multilinear Algebra , 24 : 1 (1988) pp. 65–78
[a18]	P. Heyfron, "Some inequalities concerning immanants" Math. Proc. Cambridge Philos. Soc. , 109 (1991) pp. 15–30
[a19]	G.D. James, "Permanents, immanants, and determinants" , Proc. Sympos. Pure Math. , 47 , Amer. Math. Soc. (1987) pp. 431–436
[a20]	G.D. James, M.W. Liebeck, "Permanents and immanants of Hermitian matrices" Proc. London Math. Soc. , 55 : 3 (1987) pp. 243–265
[a21]	G.D. James, "Hecke algebras and immanants" Linear Alg. & Its Appl. , 197/198 (1994) pp. 659–670
[a22]	Ch.R. Johnson, "The permanent-on-top conjecture: a status report" F. Uhlig (ed.) R. Grone (ed.) , Current Trends in Matrix Theory , Elsevier (1987)
[a23]	Ch.R. Johnson, Stephen Pierce, "Inequalities for single-hook immanants" Linear Alg. & Its Appl. , 102 (1988) pp. 55–79
[a24]	E.H. Lieb, "Proofs of some conjectures on permanents" J. Math. Mech. , 16 : 2 (1966) pp. 127–134
[a25]	D.E. Littlewood, "The theory of group characters" , Oxford Univ. Press (1950) (Edition: Second)
[a26]	M. Marcus, "The permanent analogue of the Hadamard determinant theorem" Bull. Amer. Math. Soc. , 69 (1963) pp. 494–496
[a27]	R. Merris, K.R. Rebman, W. Watkins, "Permanental polynomials of graphs" Linear Alg. & Its Appl. , 38 (1981) pp. 273–288
[a28]	R. Merris, W. Watkins, "Inequalities and identities for generalized matrix functions" Linear Alg. & Its Appl. , 64 (1985) pp. 223–242
[a29]	R. Merris, "The Laplacian permanental polynomial for trees" Czech. Math. J. , 32 (1982) pp. 397–403
[a30]	R. Merris, "The second immanantal polynomial and the centroid of a graph" SIAM J. Algebraic Discr. Meth. , 7 : 3 (1986) pp. 484–497
[a31]	R. Merris, "The permanental dominance conjecture" F. Uhlig (ed.) R. Grone (ed.) , Current Trends in Matrix Theory , Elsevier (1987)
[a32]	R. Merris, "Laplacian matrices of graphs: A survey" Linear Alg. & Its Appl. , 197/198 (1994) pp. 143–176
[a33]	R. Merris, "Multilinear algebra" , Gordon & Breach (1997)
[a34]	Th.H. Pate, "Immanant inequalities and partition node diagrams" J. London Math. Soc. , 46 (1991) pp. 65–80
[a35]	Th.H. Pate, "Partitions, irreducible characters and inequalities for generalized matrix functions" Trans. Amer. Math. Soc. , 325 (1991) pp. 875–894
[a36]	Th.H. Pate, "Descending chains of immanants" Linear Alg. & Its Appl. , 162/164 (1992) pp. 639–650
[a37]	Th.H. Pate, "Psi-functions, irreducible characters and a conjecture of Merris and Watkins" Linear and Multilinear Algebra , 35 (1993) pp. 195–212
[a38]	Th.H. Pate, "Immanant inequalities, induced characters, and rank two partitions" J. London Math. Soc. , 49 (1994) pp. 40–60
[a39]	Th.H. Pate, "Row appending maps, $\Psi$-functions, and immanant inequalities for Hermitian positive semi-definite matrices" Proc. London Math. Soc. , 76 : 3 (1998) pp. 307–358
[a40]	I. Schur, "Über endlicher Gruppen und Hermiteschen Formen" Math. Z. , 1 (1918) pp. 184–207
[a41]	G.W. Soules, "An approach to the permanental-dominance conjecture" Linear Alg. & Its Appl. , 201 (1994) pp. 211–229
[a42]	R.P. Stanley, J.R. Stembridge, "On immanants of Jacobi–Trudi matrices and permutations with restricted position" J. Combin. Th. A , 62 (1993) pp. 263–279
[a43]	J.R. Stembridge, "Immanants of totally positive matrices are non-negative" Bull. London Math. Soc. , 23 (1991) pp. 422–428
[a44]	J.R. Stembridge, "Some conjectures for immanants" Canad. J. Math. , 44 (1992) pp. 1079–1099
[a45]	J. Turner, "Generalized matrix functions and the graph isomorphism problem" SIAM J. Appl. Math. , 16 (1968) pp. 520–526