What are the applications of immanants? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T15:16:36Z http://mathoverflow.net/feeds/question/66284 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66284/what-are-the-applications-of-immanants What are the applications of immanants? Marcin Kotowski 2011-05-28T14:53:39Z 2011-05-29T17:27:18Z <p>Definitions of determinant:</p> <p>$det(A) = \sum_{\sigma \in S_n}(-1)^{\operatorname{sgn} \sigma}\prod_{i}a_{i, \sigma(i)}$</p> <p>and permanent:</p> <p>$perm(A) = \sum_{\sigma \in S_n}\prod_{i}a_{i, \sigma(i)}$</p> <p>admit a generalization in the form of <a href="http://en.wikipedia.org/wiki/Immanant" rel="nofollow">immanant</a>:</p> <p>$Imm_{\lambda}(A) = \sum_{\sigma \in S_n}\chi_{\lambda}(\sigma)\prod_{i}a_{i, \sigma(i)}$</p> <p>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}$.</p> <p>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?</p> http://mathoverflow.net/questions/66284/what-are-the-applications-of-immanants/66303#66303 Answer by S. Sra for What are the applications of immanants? S. Sra 2011-05-28T18:03:42Z 2011-05-28T18:03:42Z <p>This is a comment, but too long, so have put it down here.</p> <p>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. </p> <p><a href="http://eom.springer.de/i/i130010.htm" rel="nofollow">Link to entry on Immanants</a></p> <p>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</p> <p><code>$$\text{per}(A) \ge \overline{\text{Imm}}_\chi(A),$$</code> where $\overline{\text{Imm}}_\chi(A)$ denotes the normalized Immanant.</p> <p>But I don't think that counts as an "application."</p> http://mathoverflow.net/questions/66284/what-are-the-applications-of-immanants/66306#66306 Answer by Igor Pak for What are the applications of immanants? Igor Pak 2011-05-28T18:40:14Z 2011-05-28T18:40:14Z <p>Yes, the immanants of <i>positive definite matrices</i> are very natural and their studies go back to I. Schur (1918). Start with <a href="http://www-math.mit.edu/~rstan/papers/problems.ps" rel="nofollow">"Positivity Problems and Conjectures in Algebraic Combinatorics"</a> survey by R. Stanley and follows the references, notably <a href="http://www.sciencedirect.com/science/article/pii/002186939290196S" rel="nofollow">"Immanants of combinatorial matrices"</a> by I.P. Goulden and D.M. Jackson, and <a href="http://web.math.berkeley.edu/~mhaiman/ftp/heckeimm/jams1.pdf" rel="nofollow">"Hecke Algebra Characters and Immanant Conjectures"</a> 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. <a href="http://www.springerlink.com/content/pt30440612t7j062/" rel="nofollow">this</a> paper by B. Rhoades and M. Skandera, and a number of followup papers). </p> http://mathoverflow.net/questions/66284/what-are-the-applications-of-immanants/66333#66333 Answer by Gjergji Zaimi for What are the applications of immanants? Gjergji Zaimi 2011-05-29T03:48:14Z 2011-05-29T03:48:14Z <p>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 (<a href="http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete" rel="nofollow">#P-complete</a>). P. Burgisser has some articles in this direction, for instance "The computational complexity of Immanants". See also <a href="http://arxiv.org/abs/cs/0301024" rel="nofollow">"Complexity and completeness of Immanants"</a> by J-L. Brylinski and R. Brylinski.</p> http://mathoverflow.net/questions/66284/what-are-the-applications-of-immanants/66380#66380 Answer by Douglas Zare for What are the applications of immanants? Douglas Zare 2011-05-29T17:27:18Z 2011-05-29T17:27:18Z <p>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 <a href="http://en.wikipedia.org/wiki/Hamiltonian_path_problem" rel="nofollow">Hamiltonian cycle problem</a>). You notice that this is expressible as a linear combination of immanants of the adjacency matrix:</p> <p>$$\sum_{\sigma \in S_n} f(\sigma)\prod_{i}a_{i, \sigma(i)}$$</p> <p>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.</p>