5
$\begingroup$

Let $A$ be an $n \times n$ matrix over some field $\mathbb{F}$. The determinant

$$ \det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}$$

can be evaluated in $O(n^3)$ field operations (via Gaussian elimination, say). Note that this is much better than naive evaluation of the polynomial above, which has $n!$ terms. On the other hand, the similar-looking permanent

$$ \operatorname{perm}(A) = \sum_{\sigma \in S_n} A_{1 \sigma(1)} \cdots A_{n \sigma(n)} $$

has no known polynomial-time evaluation algorithm: it is $\#P$-complete even for matrices containing only zeros and ones over $\mathbb{F} = \mathbb{Q}$. The other significant difference is that the determinant is invariant under an arbitrary change of basis ($A \mapsto P A P^{-1}$ for any invertible $P$), whereas the immanant is only invariant under a permutation of basis elements ($A \mapsto P A P^{-1}$ for $P$ a permutation matrix).

There are a finite number of functions which interpolate between the determinant and the permanent. For any irreducible character $\chi \colon S_n \to \mathbb{Z}$, we can define the immanant of the matrix $A$ to be $$ \operatorname{Imm}_\chi(A) = \sum_{\sigma \in S_n} \chi(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}. $$ Then the permanent corresponds to the trivial character $\chi(\sigma) = 1$, and the determinant corresponds to the sign character $\chi(\sigma) = (-1)^k$ where $k$ is the number of inversions in $\sigma$.

Question: What is known about the complexity of computing immanants? At what point do they switch over from being polynomial time to being NP-hard?

In order for this question to make sense, we need to know about what kinds of immanants arise for a given $n$, or in other words what the irreducible characters of $S_n$ are. It turns out that the irreducible characters of $S_n$ are in bijection with integer partitions of $n$, or in other words decreasing lists of positive integers adding to $n$. These are often also represented by their Young diagrams, for example the integer partitions of $n = 5$ are shown below:

Integer partitions of 5

In the standard way of associating partitions to characters, the one-row partition $(n)$ corresponds to the trivial representation (and to the permanent), while the one-column partition $(1, \ldots, 1)$ corresponds to the sign representation (and to the determinant).

There are some natural partial orders that can be put on the set of partitions of $n$, which place the one-row partition at one end of the order and the one-column partition at the other, such as the dominance order. We could perhaps fantasise that as you move up this order from the "easy" determinant to the "hard" permanent, you come across some kind of barrier where computation starts getting harder and harder.

$\endgroup$
5
$\begingroup$

The state of affairs as of 2013 is described in Mertens and Moore, The Complexity of the Ferminonants and Immanants of Constant Width. Let $\lambda$ be the partition corresponding to $\chi$.

  • Immanants are easy if the leftmost column of $\lambda$ contains $n - O(1)$ boxes (Barvinok; Bürgisser).
  • Immanants are hard if $\lambda_i - \lambda_{i+1} = \Omega(n^\delta)$ (Brylinsky and Brylinsky, improving on results of Hartmann and Bürgisser which applied only to hooks and rectangles).
  • The problem of computing the $\lambda$-immanant given $\lambda$ is hard even if $\lambda$ is restricted to have width 2, and promised to have at least $n^\delta$ boxes in the second column (Mertens and Moore; de Rugy-Altherre).

The paper of de Rugy-Altherre is subsequent to Mertens–Moore.

$\endgroup$
1
  • $\begingroup$ Thanks very much for the references - I also learned what Fermionants are today! I find the first result you mention not surprising, but the third one certainly is - it reminds me of a result that computing Littlewood-Richardson coefficients even for partitions of at most two rows is NP-hard. $\endgroup$
    – Joppy
    Oct 8 '20 at 10:29
2
$\begingroup$

Shameless self-promotion: Under standard complexity assumptions, A full complexity dichotomy for immanant families shows that immanant families (satisfying minimal computability and density requirements) are polynomial-time computable iff the involved partitions have only finitely many boxes outside of the first column.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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