The multiplicity of the max eigenvalue in matrix multiplication - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T03:00:42Z http://mathoverflow.net/feeds/question/90287 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90287/the-multiplicity-of-the-max-eigenvalue-in-matrix-multiplication The multiplicity of the max eigenvalue in matrix multiplication David 2012-03-05T15:55:22Z 2012-03-08T00:31:43Z <p>Suppose that eigenvalues of two real square matrix $A$ and $B$ are $1 = \lambda^A_1 > \lambda^A_2 \geq \ldots \geq \lambda^A_n > 0$ and $1 = \lambda^B_1 > \lambda^B_2 \geq \ldots \geq \lambda^B_n > 0$. All eigenvalues are real; and the multiplicity of $\lambda^A_1$ and $\lambda^B_1$ are 1. I'm not sure whether the following properties are true. Could you please help me to prove or disprove them.</p> <ol> <li><p>Are all eigenvalues of the product $AB$ are positive real numbers? If not, which property of them can we infer? </p></li> <li><p>Is the max eigenvalue of $AB$ real? Does it has multiplicity of 1?</p></li> </ol> <p>Thanks a lot, David </p> http://mathoverflow.net/questions/90287/the-multiplicity-of-the-max-eigenvalue-in-matrix-multiplication/90289#90289 Answer by Igor Rivin for The multiplicity of the max eigenvalue in matrix multiplication Igor Rivin 2012-03-05T16:10:11Z 2012-03-05T16:10:11Z <p>I am afraid you can infer almost nothing. For example, it is a result of Frobenius (1910) that every square matrix is a product of two symmetric matrices. Since the eigenvalues of the symmetric matrices are real, you can not infer anything about the reality of the eigenvalues of the product. I am pretty sure you can play around with multiplicities, as well (check out the very concrete proof of Frobenius' theorem by A. J. Bosch (The factorization of a square matrix into two symmetric matrices, American Math. Monthly, 1986). In fact, as pointed out by M. Sapir, you can take $B=A^{-1},$ in which case the product has very high multiplicity of its one eigenvalue.</p> http://mathoverflow.net/questions/90287/the-multiplicity-of-the-max-eigenvalue-in-matrix-multiplication/90292#90292 Answer by Misha for The multiplicity of the max eigenvalue in matrix multiplication Misha 2012-03-05T17:01:01Z 2012-03-07T20:14:47Z <p>This question is a special case of <em>Deligne-Simpson Problem</em> which asks about restrictions on conjugacy classes of square matrices $A_1,...,A_k$ whose product equals $1$. See for instance </p> <p><a href="http://www.icm2006.org/proceedings/Vol_II/contents/ICM_Vol_2_06.pdf" rel="nofollow">http://www.icm2006.org/proceedings/Vol_II/contents/ICM_Vol_2_06.pdf</a></p> <p>and references therein. </p> <p>(And, yes, there are some nontrivial restrictions even for triples of matrices!) </p> <p>There is also an interesting variation on this question where one is asking about <em>singular values</em> of the matrices (google "Thompson's conjecture"). </p> <p><em>Addendum.</em> Following Igor's suggestions, I add few more details on this problem. </p> <p>Let $A_1,...,A_p$ be matrices in $SL(n, {\mathbb C})$ and $\Gamma$ be the subgroup that they generate. Let $C_j$ denote the conjugacy class of $A_j$ in $SL(n, {\mathbb C})$. For simplicity, I will assume that each $C_j$ consists of diagonalizable matrices only. </p> <p><em>Note</em>. I realize that the original question was about <em>real</em> matrices. However, the <em>necessary</em> conditions for complex matrices are, of course, also <em>necessary</em> for the real matrices. I do not know if somebody worked on the <em>sufficient</em> conditions in the real case. </p> <p><em>Problem</em> (PMP, Product of Matrices Problem). Describe necessary and sufficient conditions on conjugacy classes $C_1,...,C_p$ so that there exist matrices $A_j\in C_j$ satisfying $$A_1 \ldots A_p=1.$$</p> <p><em>Definition</em>. The tuple $(A_1,...,A_k)$ is {\em irreducible} if the action of $\Gamma$ on ${\mathbb C}^n$ is irreducible. </p> <p>Note that (since we are considering only diagonalizable matrices), the <em>Product of Matrices Problem</em> (PMP) reduces to the case of irreducible tuples (otherwise, you the problem reduces to the block-diagonal case). </p> <p><em>Problem</em> (DSP, Deligne-Simpson Problem). Describe necessary and sufficient conditions on conjugacy classes $C_1,...,C_p$ so that there exist an irreducible tuple matrices $A_j\in C_j$ satisfying $$A_1 \ldots A_p=1.$$</p> <p>As Aaron correctly observed, the first interesting case of the PMP and DSP is when $n=3$ (see the example below). For instance, the case $n=2$ when the eigenvalues are all real, there are indeed no restrictions on the eigenvalues since for every collection of positive real numbers $\ell_1,...,\ell_p$ there exists a hyperbolic surface $\Sigma$ with geodesic boundary which is (topologically) a $p$-holed sphere, so that the lengths of the boundary components are $\ell_1,...,\ell_p$. (This is a nice geometric fact that has a computation-free geometric proof using right-angled hyperbolic hexagons, see for instance Thurston's book "3-dimensional geometry and topology.") </p> <p><em>Notation</em>. For a diagonalizable matrix $A$ we let $(m_1,...,m_k)$ denote the multiplicities of its eigenvalues, the number $d(A):=n^2- (m_1^2+...+m_k^2)$ is the dimension of the conjugacy class of $A$. We also let $r(A)$ denote $$n-\max(m_1,...,m_k).$$ Since we are having $p$ conjugacy classes of matrices, we have the quantities $d_j:=d(A_j)$ and $r_j:=r(A_j)$. </p> <p>Theorem (C.Simpson, [1]) The following are <em>necessary</em> conditions on the conjugacy classes $C_j$ in DSP:</p> <ol> <li><p>$d_1+...+d_p \ge 2n^2-2$. </p></li> <li><p>For every $j$, $$r_1+...+ \hat{r}_j+...+r_p\ge n.$$</p></li> </ol> <p>Here $\hat{r}$ as usual means "skip it." Note that for $n=2$ Simpson's conditions always hold (provided that all matrices are different from $\pm I$). </p> <p>Simpson also proves in [1] that under some "genericity conditions'' on the eigenvalues and assuming that $r_j=1$ for at least one $j$, the above conditions are also <em>sufficient</em> in DSP. </p> <p>Crawley-Boevey reformulated DSP using quivers and solved it completely, see Theorem 10 and the following comments in [2]. However, the conditions that Crawley-Boevey formulates are in terms of roots of Kac-Moody algebra associated with the conjugacy classes $C_j$. I suspect that in the diagonalizable case his conditions are not too bad and can be read off from the multiplicities of eigenvalues. However, to be honest, I am not the right person to do the translation, since I do not know enough about quivers. (Maybe when and if I have more time, I could invest some of it in the translation.) For now, Simpson's conditions above provide <em>some</em> restrictions on the eigenvalues. </p> <p><em>Example.</em> In [3], page 176, Crawley-Boevey gives the following translation of his conditions in the case of three 3-by-3 matrices $A_1, A_2, A_3$. Assume that $r_1=r_2=r_3=1$ (i.e., all three conjugacy classes have one eigenvalue of multiplicity 2). Let $\lambda_i$ denote eigenvalues of multiplicity 2 of $A_i$. Then the solution of the PMP is: $$\prod_i \lambda_i=1$$ (i.e., this is necessary and sufficient condition). </p> <p>References. </p> <p>[1] C. Simpson, Products of matrices, In “Diﬀerential Geometry, Global Analysis and Topology”, Canadian Math. Soc. Conference Proceedings 12, AMS, (1991), 157 – 185. </p> <p>[2] W. Crawley-Boevey, Quiver algebras, weighted projective lines, and the Deligne-Simpson problem. International Congress of Mathematicians. Vol. II, 117–129, Eur. Math. Soc., Zurich, 2006. </p> <p>[3] W. Crawley-Boevey,<br> Indecomposable parabolic bundles and the existence of matrices in prescribed conjugacy class closures with product equal to the identity. Publ. Math. Inst. Hautes Etudes Sci. No. 100 (2004), 171–207. </p> http://mathoverflow.net/questions/90287/the-multiplicity-of-the-max-eigenvalue-in-matrix-multiplication/90307#90307 Answer by Aaron Meyerowitz for The multiplicity of the max eigenvalue in matrix multiplication Aaron Meyerowitz 2012-03-05T21:06:51Z 2012-03-05T21:06:51Z <p>I don't think one can say much of anything. Let $A= \begin{pmatrix}1&amp;b\cr 0&amp;1/2\end{pmatrix}$ and $B= \begin{pmatrix}1&amp;0\cr -b&amp;1/2\end{pmatrix},$ then $AB=( \begin{smallmatrix}1-b^2&amp;b/2\cr -b/2&amp;1/4\end{smallmatrix})$ has eigenvalues $$\frac{5-4b^2\pm\sqrt{(4b^2-1)(4b^2-9)}}8.$$ We may concentrate on $b \ge 0.$ For $3/2 \lt b$ these values are distinct but both negative. For $b=3/2$, the only eigenvalue is $-1/2$ (with multiplicity 1 or 2 depending on how you count.). For $1/2 \lt b \lt 3/2$ they are not real. for $0 \le b \lt 1/2$ they are distinct and positive. </p> <p>The example $A= \begin{pmatrix}1&amp;0\cr 0&amp;1/2\end{pmatrix}$ and $B= \begin{pmatrix}1/2&amp;0\cr 0&amp;1\end{pmatrix}$ shows that the maximum eigenvalue need not have multiplicity 1.</p>