# complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

The fermionant is a matrix function from physics, which is indexed by a positive integer $$k$$:

\begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A). \end{align}

In the above $$A$$ is an $$n \times n$$ matrix, $$\lambda$$ ranges over all partitions of $$n$$ with at most $$k$$ parts, $$\lambda^T$$ is the transpose of the partition $$\lambda$$, $$d_{\lambda}^{(k)}$$ is the number of semi-standard Young tableaux of shape $$\lambda$$ and content $$\{1,2,\dots k \}$$, and $$\operatorname{Imm}_{\lambda}(A)$$ is the $$\lambda$$-immanant of the matrix $$A$$.

In S. Mertens and C. Moore "The complexity of the fermionant and immanants of constant width"(2013), it is shown for $$k=2$$ that $$\operatorname{Ferm}_k$$ is in the class $$\oplus \bf{P}$$.

In the above-mentioned paper, it is said that:

If $$k=\mathcal{O}(1)$$, there are $$\mathcal{O}(n^{k-1})=\operatorname{poly}(n)$$ partitions of width $$k$$ or less. Thus for any constant $$k$$ there is a polynomial-time Turing reduction from the fermionant $$\operatorname{Ferm}_k$$ to the problem of computing the immanant $$\operatorname{Imm}_{\lambda}$$ where $$\lambda$$ is given as part of the input and where $$\lambda$$ has width at most $$k$$. It follows that the problem of computing $$\operatorname{Imm}_{\lambda}(A)$$ as a function of $$A$$ and $$\lambda$$ is $$\oplus \bf{P}$$ under polynomial-time Turing reductions if $$k=2$$. In particular, unless the polynomial hierarchy collapses, there exits partitions $$\lambda$$ of width $$2$$ such that $$\operatorname{Imm}_{\lambda}(A)$$ is not in $$\bf{P}$$.

I am interested in the computational complexity of group functions $$\mathcal{D}^{\lambda}_{i,j}$$ - these functions are the entries in an irreducible matrix representation of $$GL_n$$ of type $$\lambda$$. There is a well-known way of relating group functions and immanants:

\begin{align} \operatorname{Imm}_{\lambda}(A) = \sum_{i=1}^{s_{\lambda}} \mathcal{D}^{\lambda}_{i,i}. \end{align}

My question is as follows. Are the claims that the above-mentioned paper makes also true for group functions? In other words, is it correct to say that the problem of computing a group function $$\mathcal{D}^{\lambda}_{i,i}$$ is $$\oplus \bf{P}$$ under polynomial-time Turing reductions if $$k=2$$; in particular, unless the polynomial hierarchy collapses, there exits partitions $$\lambda$$ of width $$2$$ such that $$\mathcal{D}^{\lambda}_{i,i}$$ is not in $$\bf{P}$$?

This doesn't quite answer your question because you're asking specifically about diagonal entries (in what basis? Any basis will work for the connection to immanents, but the complexity could change depending on what basis you use to actually compute $$D_{ii}^\lambda$$), but it's a little too long for a comment.
Bürgisser showed that $$(g,v) \mapsto D^{\lambda}(g)\cdot v$$ on $$GL_m \times \mathbb{C}^m$$ can be computed in $$poly(m,d_{\lambda},\log|\lambda|, mult(\lambda))$$ arithmetic operations, where $$mult(\lambda)$$ is the maximum multiplicity of restriction between any nodes two levels apart in the Gelfand-Tsetlin graph of $$\lambda$$. Can be found as Theorem 6.6 in his book Completeness & Reductions.
In Theorem 6.9 he shows that the dependence on $$d_\lambda$$ is unavoidable.
• There is a natural basis for this problem and it is the basis of states of weight (1111..1) in $GL(n,\mathbb{C})$. The diagonal entries refer to this basis. See Kostan B. Immanant inequalities and 0-weight spaces. Journal of the American Mathematical Society. 1995 Jan 1;8(1):181-6. Sep 17 '21 at 18:50
• @Tefari: Depends how you measure complexity. If only measuring non-scalar multiplications (i.e. mults by amounts that depend on an input variable, i.e. mult by "non-constants") then complexity doesn't change. If including scalar mults/adds, the complexity of computing $AD^\lambda(g) A^{-1}$ could differ from that of $D^\lambda(g)$ by the complexity to compute the matrix product $A(D^\lambda(g)A^{-1}$. That's for all entries of $D^\lambda(g)$. If you only want the diagonal, it could change more, since the diagonal in a different basis could depend on all entries in the original basis. Sep 20 '21 at 4:35
• Since $v$ is of length $d_{\lambda}$, and $D^\lambda(g)v$ is scale as $d_\lambda$ and other factors, what does it say about the scaling of $D^\lambda(g)$ itself with $d_\lambda$? Sep 21 '21 at 19:30