The multiplicity of the max eigenvalue in matrix multiplication

2012-03-05T15:55:22Z

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.

Are all eigenvalues of the product $AB$ are positive real numbers? If not, which property of them can we infer?
Is the max eigenvalue of $AB$ real? Does it has multiplicity of 1?

Thanks a lot, David

Answer by Igor Rivin for The multiplicity of the max eigenvalue in matrix multiplication

2012-03-05T16:10:11Z

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.

Answer by Misha for The multiplicity of the max eigenvalue in matrix multiplication

2012-03-05T17:01:01Z

This question is a special case of Deligne-Simpson Problem which asks about restrictions on conjugacy classes of square matrices $A_1,...,A_k$ whose product equals $1$. See for instance

http://www.icm2006.org/proceedings/Vol_II/contents/ICM_Vol_2_06.pdf

and references therein.

(And, yes, there are some nontrivial restrictions even for triples of matrices!)

There is also an interesting variation on this question where one is asking about singular values of the matrices (google "Thompson's conjecture").

Addendum. Following Igor's suggestions, I add few more details on this problem.

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.

Note. I realize that the original question was about real matrices. However, the necessary conditions for complex matrices are, of course, also necessary for the real matrices. I do not know if somebody worked on the sufficient conditions in the real case.

Problem (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. $$

Definition. The tuple $(A_1,...,A_k)$ is {\em irreducible} if the action of $\Gamma$ on ${\mathbb C}^n$ is irreducible.

Note that (since we are considering only diagonalizable matrices), the Product of Matrices Problem (PMP) reduces to the case of irreducible tuples (otherwise, you the problem reduces to the block-diagonal case).

Problem (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. $$

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.")

Notation. 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)$.

Theorem (C.Simpson, [1]) The following are necessary conditions on the conjugacy classes $C_j$ in DSP:

$d_1+...+d_p \ge 2n^2-2$.
For every $j$, $$ r_1+...+ \hat{r}_j+...+r_p\ge n. $$

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$).

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 sufficient in DSP.

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 some restrictions on the eigenvalues.

Example. 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).

References.

[1] C. Simpson, Products of matrices, In “Diﬀerential Geometry, Global Analysis and Topology”, Canadian Math. Soc. Conference Proceedings 12, AMS, (1991), 157 – 185.

[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.

[3] W. Crawley-Boevey,
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.

Answer by Aaron Meyerowitz for The multiplicity of the max eigenvalue in matrix multiplication

2012-03-05T21:06:51Z

I don't think one can say much of anything. Let $A= \begin{pmatrix}1&b\cr 0&1/2\end{pmatrix}$ and $B= \begin{pmatrix}1&0\cr -b&1/2\end{pmatrix},$ then $AB=( \begin{smallmatrix}1-b^2&b/2\cr -b/2&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.

The example $A= \begin{pmatrix}1&0\cr 0&1/2\end{pmatrix}$ and $B= \begin{pmatrix}1/2&0\cr 0&1\end{pmatrix}$ shows that the maximum eigenvalue need not have multiplicity 1.

The multiplicity of the max eigenvalue in matrix multiplication - MathOverflow

The multiplicity of the max eigenvalue in matrix multiplication

Answer by Igor Rivin for The multiplicity of the max eigenvalue in matrix multiplication

Answer by Misha for The multiplicity of the max eigenvalue in matrix multiplication

Answer by Aaron Meyerowitz for The multiplicity of the max eigenvalue in matrix multiplication