patternMinor
Time complexity of the immanant
Viewed 0 times
immanantthecomplexitytime
Problem
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 repr
$$ \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 repr
Solution
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$.
The paper of de Rugy-Altherre is subsequent to Mertens–Moore.
- 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.
Context
StackExchange Computer Science Q#130947, answer score: 5
Revisions (0)
No revisions yet.