# 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 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 } ]$, 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 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].

How to Cite This Entry:
Immanant. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Immanant&oldid=50606
This article was adapted from an original article by O. Chan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article