# The multiplicity of the max eigenvalue in matrix multiplication

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.

1. Are all eigenvalues of the product $AB$ are positive real numbers? If not, which property of them can we infer?

2. Is the max eigenvalue of $AB$ real? Does it has multiplicity of 1?

Thanks a lot, David

-

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.

-
You cannot take $B=A^{-1}$ because its highest eigenvalue will be $>1$. I have deleted my answer. –  Mark Sapir Mar 5 '12 at 16:23
Sigh, reading comprehension is not my friend :( –  Igor Rivin Mar 5 '12 at 16:55
Thank you Igor. Can we add more constrains (properties) on $A$ and $B$ such that the max eigenvalue of $AB$ is real and has multiplicity of 1? If so, can you suggest some kind of constrains that I can use? –  David Mar 5 '12 at 19:50
So $A$ satisfies these constrains, $A^{-1}$ must not satisfies. The question is not reasonable. If matrices $A$ and $B$ are given, does there always exists $k \in Z^+$ such that $C=A(kI + B)$ has the property 2 (i.e. the max eigenvalue of $C$ is real and has multiplicity of 1)? If there always exist $k$, how can we find it? Thanks, David –  David Mar 5 '12 at 20:06
In this variation you want to consider $C=kA+X$ for the matrix $X=AB$. The eigenvalues are simply $k$ times the eigenvalues of $C'=A+X/k.$ So you wonder when $C'$ has all eigenvalue real and the largest one of multiplicity $1$ (given that these things are true of $A$) It seems a sure thing that whatever $X$ is, for and $\epsilon \gt 0$ there is a $K$ such that for all $k \gt K,$ $\max_j(|\lambda^A_j-\lambda^{C'}_j|) \lt \epsilon.$ How to find $K$ given $A$ and $X$, or just their spectra, I can't say. –  Aaron Meyerowitz Mar 5 '12 at 23:01

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:

1. $d_1+...+d_p \ge 2n^2-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.

-
This is an excellent answer, however, the reference seems to be rather opaque, and in particular, I am having trouble deducing any sort of answer to the OP's question from this (the very last theorem in the paper seems relevant, but it seems to be stated on the Lie algebra level, and I am not sure quite what to make of it). Perhaps you can clarify? –  Igor Rivin Mar 5 '12 at 17:07
I must be missing something, but isn't the PMP more complicated than what the OP asked for? His question (1) asks for positive eigenvalues, whereas PMP apparently forces them all to be 1. His question (2) only refers to the largest eigenvalue. So - what have I missed? Thanks! –  Felix Goldberg May 25 '14 at 8:36
@FelixGoldberg: One rewrites PMP (for 3 matrices) as $C=AB$. There is no assumption in PMP for all eigenvalues to be 1. Of course, PMP is much more general than the one in OP's question. My point was to show that there are nontrivial restrictions on the eigenvalues of the products of matrices (which was part 1 of the OP's question). I did not think about the question 2 (and did not think about this question at all since 2 years ago). –  Misha May 25 '14 at 18:22

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.

-

Inspired by @Mark Sapir and @Igor Rivin, just take $B=0.5\lambda_n^A A^{-1}$, so $\lambda_i^B=0.5\lambda_n^A /\lambda_{n+1-i}^A \in (0,1)$. And we have $AB=0.5\lambda_n^A I$, its multiplicity is not one.

This should be a simple comment, but I don't have enough reputation to comment..

-