<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 <span class="math-container">$D_{ii}^\lambda$</span>), but it's a little too long for a comment.</p>
<p>Bürgisser showed that <span class="math-container">$(g,v) \mapsto D^{\lambda}(g)\cdot v$</span> on <span class="math-container">$GL_m \times \mathbb{C}^m$</span> can be computed in <span class="math-container">$poly(m,d_{\lambda},\log|\lambda|, mult(\lambda))$</span> arithmetic operations, where <span class="math-container">$mult(\lambda)$</span> is the maximum multiplicity of restriction between any nodes two levels apart in the Gelfand-Tsetlin graph of <span class="math-container">$\lambda$</span>. Can be found as Theorem 6.6 in his book Completeness &amp; Reductions.</p>
<p>In Theorem 6.9 he shows that the dependence on <span class="math-container">$d_\lambda$</span> is unavoidable.</p>

CC BY-SA 4.0
2021-09-17T18:50:15.483Z
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.
ZeroTheHero
CC BY-SA 4.0
2021-09-20T03:10:40.360Z
@Joshua Thank you for the comment. I'm interested in what you say about how the complexity could change depending on what basis is used. Is there a reference that you could refer me too so I can read more?
Teferi
CC BY-SA 4.0
2021-09-20T04:35:38.113Z
@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.
Joshua Grochow
CC BY-SA 4.0
2021-09-21T19:30:58.503Z
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$?
ZeroTheHero
CC BY-SA 4.0
2021-09-16T20:04:56.410Z
2021-09-16T20:04:56.410Z
Joshua Grochow
<p>The fermionant is a matrix function from physics, which is indexed by a positive integer <span class="math-container">$k$</span>:</p>
<p><span class="math-container">\begin{align}
\operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A). 
\end{align}</span></p>
<p>In the above <span class="math-container">$A$</span> is an <span class="math-container">$n \times n$</span> matrix, <span class="math-container">$\lambda$</span> ranges over all partitions of <span class="math-container">$n$</span> with at most <span class="math-container">$k$</span> parts, <span class="math-container">$\lambda^T$</span> is the transpose of the partition <span class="math-container">$\lambda$</span>, <span class="math-container">$d_{\lambda}^{(k)}$</span> is the number of semi-standard Young tableaux of shape <span class="math-container">$\lambda$</span> and content <span class="math-container">$\{1,2,\dots k \}$</span>, and <span class="math-container">$\operatorname{Imm}_{\lambda}(A)$</span> is the <span class="math-container">$\lambda$</span>-immanant of the matrix <span class="math-container">$A$</span>.</p>
<p>In S. Mertens and C. Moore &quot;The complexity of the fermionant and immanants of constant width&quot;(2013), it is shown for <span class="math-container">$k=2$</span> that <span class="math-container">$\operatorname{Ferm}_k$</span> is in the class <span class="math-container">$\oplus \bf{P}$</span>.</p>
<p>In the above-mentioned paper, it is said that:</p>
<p>If <span class="math-container">$k=\mathcal{O}(1)$</span>, there are <span class="math-container">$\mathcal{O}(n^{k-1})=\operatorname{poly}(n)$</span> partitions of width <span class="math-container">$k$</span> or less. Thus for any constant <span class="math-container">$k$</span> there is a polynomial-time Turing reduction from the fermionant <span class="math-container">$\operatorname{Ferm}_k$</span> to the problem of computing the immanant <span class="math-container">$\operatorname{Imm}_{\lambda}$</span> where <span class="math-container">$\lambda$</span> is given as part of the input and where <span class="math-container">$\lambda$</span> has width at most <span class="math-container">$k$</span>. It follows that the problem of computing <span class="math-container">$\operatorname{Imm}_{\lambda}(A)$</span> as a function of <span class="math-container">$A$</span> and <span class="math-container">$\lambda$</span> is <span class="math-container">$\oplus \bf{P}$</span> under polynomial-time Turing reductions if <span class="math-container">$k=2$</span>. In particular, unless the polynomial hierarchy collapses, there exits partitions <span class="math-container">$\lambda$</span> of width <span class="math-container">$2$</span> such that <span class="math-container">$\operatorname{Imm}_{\lambda}(A)$</span> is not in <span class="math-container">$\bf{P}$</span>.</p>
<p>I am interested in the computational complexity of group functions <span class="math-container">$\mathcal{D}^{\lambda}_{i,j}$</span> - these functions are the entries in an irreducible matrix representation of <span class="math-container">$GL_n$</span> of type <span class="math-container">$\lambda$</span>. There is a well-known way of relating group functions and immanants:</p>
<p><span class="math-container">\begin{align}
\operatorname{Imm}_{\lambda}(A) = \sum_{i=1}^{s_{\lambda}} \mathcal{D}^{\lambda}_{i,i}.
\end{align}</span></p>
<p>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 <span class="math-container">$\mathcal{D}^{\lambda}_{i,i}$</span> is <span class="math-container">$\oplus \bf{P}$</span> under polynomial-time Turing reductions if <span class="math-container">$k=2$</span>; in particular, unless the polynomial hierarchy collapses, there exits partitions <span class="math-container">$\lambda$</span> of width <span class="math-container">$2$</span> such that <span class="math-container">$\mathcal{D}^{\lambda}_{i,i}$</span> is not in <span class="math-container">$\bf{P}$</span>?</p>

<cc.complexity-theory><complexity-classes><linear-algebra><reductions>
complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)
Teferi
# complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

(Asked by: username_0 on 2021-09-16)

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}$?

**Tags:** cc.complexity-theory, complexity-classes, linear-algebra, reductions

---

## 1 answers

### Answer by username_1 on 2021-09-16. Score: 3

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.

> **Comments:**
> **username_2**: 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.  
> **username_0**: @Joshua Thank you for the comment. I'm interested in what you say about how the complexity could change depending on what basis is used. Is there a reference that you could refer me too so I can read more?  
> **username_1**: @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.  
> **username_2**: 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$?  

---

