12
$\begingroup$

It is known that if $\alpha,\beta,\gamma$ are three partitions then the Littlewood-Richardson coefficient $c_{\alpha \beta}^{\gamma}$ is positive when the triple ($\alpha,\beta,\gamma$ ) occurs as eigenvalues of Hermitian $n \times n$ matrices $A, B, C$ with $C = A + B$ which can be seen from the following paper.

http://www.ams.org/journals/bull/2000-37-03/S0273-0979-00-00865-X/S0273-0979-00-00865-X.pdf

Is there a way to calculate the exact value of $c_{\alpha \beta}^{\gamma}$ by using this Hermitian matrices and their eigenvalues?

$\endgroup$
1
  • $\begingroup$ A more reasonable question is to relate LR numbers and spherical Hecke ring structure constants, which are responsible for the numerics in the Invariant Factors Problem in Fulton's survey. The point is that both structure constants are integral. In this setting, the numbers are not the same, but related via Satake correspondence from the spherical Hecke ring to the character ring of the dual group. $\endgroup$
    – Misha
    Sep 11, 2013 at 12:33

2 Answers 2

10
$\begingroup$

It's hard to prove that there isn't a way to do something, but I think the answer is no.

The saturation conjecture, now a theorem of Knutson and Tao, says that $c_{(N \alpha) (N \beta)}^{N \gamma} >0$ implies $c_{\alpha \beta}^{\gamma} >0$ for any positive integer $N$ and any partitions $\alpha$, $\beta$ and $\gamma$. Note that the corresponding statement for eigenvalues of Hermitian matrices is obvious. I suspect that any simple answer to your question would lead to a simple proof of the saturation conjecture and, while several proofs are now known, I would describe none of them as simple.

There is a relationship in the other direction. If $\alpha$, $\beta$ and $\gamma$ are partitions with $d$ parts then $c_{(N \alpha) (N \beta)}^{N \gamma}$ is a polynomial of degree $\binom{d-1}{2}$ in $N$ and the leading term (up to constants I'm not going to remember) is the volume of the space of triples $(A,B,C)$ of Hermitian matrices with spectra $(\alpha, \beta, \gamma)$ and $A+B=C$. So computing $c_{(N \alpha) (N \beta)}^{N \gamma}$ for enough values of $N$ allows you to compute the volume of a space of Hermitian matrices.

As a heurisitic, Hermitian matrix questions are about computing volumes of regions in $\mathbb{R}^M$; LR questions are about counting lattice points in those regions. Either one approximates the other, and the asymptotic behavior of lattice point counts tells you about volumes, but just knowing volumes will never tell you lattice point counts.

My favorite survey on the relation between the two problems is this one.

$\endgroup$
3
  • 1
    $\begingroup$ That leading-term statement is in the appendix of Honeycombs ][, at front.math.ucdavis.edu/0107.5011 $\endgroup$ Sep 11, 2013 at 14:30
  • $\begingroup$ @As a very special case of this is that one can pick parameters such that one computes the volume of the Birkhoff polytope, something that is quite tricky - and the general formula for the Ehrhart polynomial is unknown! $\endgroup$ Mar 12, 2016 at 18:04
  • $\begingroup$ The link in Allen's comment is broken, a replacement is arxiv.org/abs/math/0107011 $\endgroup$
    – David Roberts
    Mar 29, 2022 at 1:15
10
$\begingroup$

A sensible "yes" to your question would imply that the computational complexity of the calculation of Littlewood-Richardson coefficients is the same that of a calculation of eigenvalues of Hermitian matrices, so that they can be calculated in polynomial time. This seems to be impossible, see H. Narayanan, On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients.

$\endgroup$
2
  • 1
    $\begingroup$ Nice answer! This paper mentions several nice connections though, example that deciding $c_{\lambda\alpha}^\nu > 0$ can be done in polynomial time. There seems to be also links to implementations that compute LR coefficients (Buch and Stembridge); though I've yet to try these out. $\endgroup$
    – Suvrit
    Sep 11, 2013 at 17:05
  • 1
    $\begingroup$ @suvrit --- thanks --- here's a link to an LR calculator math.rutgers.edu/~asbuch/lrcalc $\endgroup$ Sep 11, 2013 at 17:35

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.