Immanant

The determinant is a special case of the immanant, where \chi_\lambda is the alternating character \sgn, of Sn, 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: As stated above, \chi_1 produces the permanent and \chi_2 produces the determinant, but \chi_3 produces the operation that maps as follows: :\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix} \rightsquigarrow 2 a_{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(\lambda) denote the number of boxes to the right of the first column of the Young diagram of a partition \lambda. If b(\lambda) is bounded for a family of partitions, then the corresponding immanants can be evaluated in polynomial time. If b(\lambda) is unbounded, then under standard assumptions from parameterized complexity theory no polynomial-time algorithm exists. Moreover, if b(\lambda) 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. 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==