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 be a partition of an integer and let be the corresponding irreducible representation-theoretic character of the symmetric group. The immanant of an matrix associated with the character is defined as the expression

Examples

The determinant is a special case of the immanant, where is the alternating character, of S_n, defined by the parity of a permutation.
The permanent is the case where is the trivial character, which is identically equal to 1.
For example, for matrices, there are three irreducible representations of, as shown in the character table:


1	1	1
1	−1	1
2	0	−1

As stated above, produces the permanent and produces the determinant, but produces the operation that maps as follows:

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 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 matrices, a result due to Valiant.
Immanants are indexed by irreducible characters of the symmetric group, 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 denote the number of boxes to the right of the first column of the Young diagram of a
partition. If is bounded for a family of partitions, then the corresponding immanants
can be evaluated in polynomial time. If is unbounded, then under standard assumptions from
parameterized complexity theory no polynomial-time algorithm exists. Moreover, if 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 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.