Immanant

In mathematics, the immanant of a matrix was defined by Dudley E. Littlewood and Archibald Read Richardson as a generalisation of the concepts of determinant and permanent.

Let $\lambda =({\lambda }_1,{\lambda }_2,\dots )$ be a partition of an integer $n$ and let ${\chi }_{\lambda }$ be the corresponding irreducible representation-theoretic character of the symmetric group $S_n$. The immanant of an $n\times n$ matrix $A=(a_{ij})$ associated with the character ${\chi }_{\lambda }$ is defined as the expression

${\mathrm{Imm}}_{\lambda }(A)=\sum _{\sigma \in S_n}{\chi }_{\lambda }(\sigma )a_{1\sigma (1)}{a}_{2\sigma (2)}\cdots a_{n\sigma (n)}=\sum _{\sigma \in S_n}{\chi }_{\lambda }(\sigma )\prod _{i=1}^n{a}_{i\sigma (i)}.$

Examples

The determinant is a special case of the immanant, where ${\chi }_{\lambda }$ is the alternating character $\mathrm{sgn}$, of S_n, defined by the parity of a permutation.

The permanent is the case where ${\chi }_{\lambda }$ is the trivial character, which is identically equal to 1.

For example, for $3\times 3$ matrices, there are three irreducible representations of $S_3$, as shown in the character table:

$S_3$	$e$	$(12)$	$(123)$
${\chi }_1$	1	1	1
${\chi }_2$	1	−1	1
${\chi }_3$	2	0	−1

As stated above, ${\chi }_1$ produces the permanent and ${\chi }_2$ produces the determinant, but ${\chi }_3$ produces the operation that maps as follows:

$\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)⇝2a_{11}{a}_{22}{a}_{33}-a_{12}{a}_{23}{a}_{31}-a_{13}{a}_{21}{a}_{32}$

Properties

The immanant shares several properties with determinant and permanent. In particular, the immanant is multilinear in the rows and columns of the matrix; and the immanant is invariant under simultaneous permutations of the rows or columns by the same element of the symmetric group.

Littlewood and Richardson studied the relation of the immanant to Schur functions in the representation theory of the symmetric group.

The necessary and sufficient conditions for the immanant of a Gram matrix to be $0$ are given by Gamas's Theorem.

Computational complexity

The immanant generalizes both the determinant and the permanent, and this generality is reflected in the computational difficulty of evaluating these functions. While the determinant can be computed in polynomial time using Gaussian elimination, computing the permanent of a general matrix is #P-complete, even when restricted to 0–1 matrices, a result due to Valiant.

Immanants are indexed by irreducible characters of the symmetric group S_n, or equivalently by Young diagrams. The computational complexity of evaluating an immanant depends strongly on the shape of the associated diagram. Early results in algebraic complexity theory showed that for many families of partitions the corresponding immanants are VNP-complete in the sense of Valiant, generalizing the hardness of the permanent.

A more refined classification was obtained by Curticapean, who proved a full complexity dichotomy for families of immanants. Let b(λ) denote the number of boxes to the right of the first column of the Young diagram of a partition λ. If b(λ) is bounded for a family of partitions, then the corresponding immanants can be evaluated in polynomial time. If b(λ) is unbounded, then under standard assumptions from parameterized complexity theory no polynomial-time algorithm exists. Moreover, if b(λ) grows polynomially with the matrix size, evaluating the corresponding immanants is #P-hard and VNP-complete, extending classical hardness results for the permanent and earlier work of Bürgisser and of Brylinski and Brylinski. Further work strengthened these hardness results by showing that many immanants remain #P-hard even when evaluated on restricted classes of matrices, including 0–1 matrices and structurally constrained inputs such as adjacency matrices of graphs.

These results suggest that, aside from the determinant, most nontrivial immanants are computationally intractable. The complexity of immanants plays a role in algebraic complexity theory and is connected to broader research programs such as Geometric Complexity Theory, where representation-theoretic properties of immanants are used to study lower bounds for the permanent and related functions.

References

• D. E. Littlewood; A.R. Richardson (1934). "Group characters and algebras". Philosophical Transactions of the Royal Society A 233 (721–730): 99–124. doi:10.1098/rsta.1934.0015. Bibcode: 1934RSPTA.233...99L. 
• D. E. Littlewood (1950). The Theory of Group Characters and Matrix Representations of Groups (2nd ed.). Oxford Univ. Press (reprinted by AMS, 2006). p. 81.