36
$\begingroup$

Definitions of determinant:

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

and permanent:

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

admit a generalization in the form of immanant:

$\mathrm{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 $\mathrm{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 $\mathrm{Imm}_{\lambda}$ other than $\det$ and $\operatorname{per}$ is natural?

$\endgroup$
5
  • 3
    $\begingroup$ 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... $\endgroup$ May 28, 2011 at 16:30
  • 2
    $\begingroup$ 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 ? $\endgroup$ May 28, 2011 at 21:05
  • 5
    $\begingroup$ @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. $\endgroup$ May 28, 2011 at 22:20
  • 5
    $\begingroup$ 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. $\endgroup$ May 29, 2011 at 6:24
  • 2
    $\begingroup$ @Emmanuel Briand: Immanants are discussed in the book by D.E. Littlewood "The Theory of Group Characters and Matrix Representations of Groups" (Oxford, 1950), from the page 81 onwards. I haven't looked on it thoroughly, but probably something is contained there. $\endgroup$ Jun 8, 2011 at 7:37

4 Answers 4

16
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ The link to the paper of B. Rhoades and M. Skandera at springerlink.com is broken. I presume it was meant to link to the following one: Rhoades, Brendon; Skandera, Mark, Temperley-Lieb immanants, Ann. Comb. 9, No. 4, 451-494 (2005). Zbl 1089.15011. $\endgroup$ Apr 9, 2023 at 14:53
13
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

$\endgroup$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.