What are the applications of immanants? - MathOverflow

What are the applications of immanants?

2011-05-28T14:53:39Z

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?

Answer by S. Sra for What are the applications of immanants?

2011-05-28T18:03:42Z

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.

Link to entry on Immanants

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.

But I don't think that counts as an "application."

Answer by Igor Pak for What are the applications of immanants?

2011-05-28T18:40:14Z

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).

Answer by Gjergji Zaimi for What are the applications of immanants?

2011-05-29T03:48:14Z

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.

Answer by Douglas Zare for What are the applications of immanants?

2011-05-29T17:27:18Z

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.