# What are the applications of immanants?

Definitions of determinant:

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

and permanent:

$perm(A) = \sum_{\sigma \in S_n}\prod_{i}a_{i, \sigma(i)}$

admit a generalization in the form of immanant:

$Imm_{\lambda}(A) = \sum_{\sigma \in S_n}\chi_{\lambda}(\sigma)\prod_{i}a_{i, \sigma(i)}$

where $\lambda$ labels irreducible representations of $S_n$ and $\chi_{\lambda}$ is the character. Determinant and permanent are easily seen to be special cases of $Imm_{\lambda}$.

While determinants are ubiquitous in mathematics and permanents also have many application, esp. in combinatorial problems, other kinds of immanants seem to be rarely used. Are there any problems where use of $Imm_{\lambda}$ other than $det$ and $perm$ is natural?

-
Side question: where do the names permanent and immanent come from? Determinant was introduced by Gauss when dealing with quadratic forms, in in his context it does determine something... –  Mariano Suárez-Alvarez May 28 '11 at 16:30
In the conclusion of the paper where the immanants are introduced, Littlewood and Richardson state that "the immanants of special matrices can be used to give results relating to the numbers of BERNOULLI, STIRLING and EULER". Does anyone know more about this ? –  Emmanuel Briand May 28 '11 at 21:05
@Mariano Suárez-Alvarez: The name "Permanent" comes from Cauchy's paper "Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de signes contraires par suite des transpositions opérées entre les variables qu’elles renferment.". There he introduced the "fonctions symétriques permanentes" = invariant under column permutations. "Immanants" is introduced in the paper "Group characters and invariants" by Littlewood and Richardson, with as a footnote: "A name suggested to us by Professor A. R. Forsyth". But I do not know any explanation for this choice. –  Emmanuel Briand May 28 '11 at 22:20
@Emmanuel: thanks! –  Mariano Suárez-Alvarez May 29 '11 at 4:27
Formally "immanant" is a participle of a made-up compound verb, "in+mano" (like emano from ex+mano), with not clear meaning. Otherwise it is a mispelling of immanent (from in+maneo, like permanent from per+maneo), maybe to rhyme with determinant. –  Pietro Majer May 29 '11 at 6:24

Yes, the immanants of positive definite matrices are very natural and their studies go back to I. Schur (1918). Start with "Positivity Problems and Conjectures in Algebraic Combinatorics" survey by R. Stanley and follows the references, notably "Immanants of combinatorial matrices" by I.P. Goulden and D.M. Jackson, and "Hecke Algebra Characters and Immanant Conjectures" by M. Haiman, and several papers by J. Stembridge. I should mention that in recent years there have been various advances in this direction (see e.g. this paper by B. Rhoades and M. Skandera, and a number of followup papers).

-

I think Immanants are also important in complexity theory because they provide a spectrum of problems with extreme cases from computing the determinant (polynomial time) to computing the permanent (#P-complete). P. Burgisser has some articles in this direction, for instance "The computational complexity of Immanants". See also "Complexity and completeness of Immanants" by J-L. Brylinski and R. Brylinski.

-

A problem with applying immanants is that after expressing something in terms of immanants, you might not be closer to calculating them and you can't easily manipulate expressions of immanants. For example, suppose you want to count Hamiltonian cycles in a graph (positivity solves the Hamiltonian cycle problem). You notice that this is expressible as a linear combination of immanants of the adjacency matrix:

$$\sum_{\sigma \in S_n} f(\sigma)\prod_{i}a_{i, \sigma(i)}$$

where $f(\sigma) = 1$ when $\sigma$ is an $n$-cycle and $0$ otherwise. Since $f$ is constant on conjugacy classes, we can decompose it as a linear combination of characters. However, the Hamiltonian cycle problem is NP-complete, so it would be surprising if there were a quick way to compute this linear combination of immanants. Either there are many terms to compute, or these terms are hard to compute, or both, even if you are just trying to determine whether the result is positive.

-

This is a comment, but too long, so have put it down here.

I found the following link that lists several papers discussing Immanants and conjectures related to them. Most of the applications mentioned therein seem to be graph theoretic.

The only place where I have previously seen Immanants is in the famous *Permanent on Top" conjecture, which states that for any positive semidefinite matrix $A$, we have
$$\text{per}(A) \ge \overline{\text{Imm}}_\chi(A),$$ where $\overline{\text{Imm}}_\chi(A)$ denotes the normalized Immanant.