IMC 2004 · Day 2 · P10

We first solve the problem for the special case when the eigenvalues of $M$ are distinct and all sums $\lambda_r + \lambda_s$ are different. Let $\lambda_r$ and $\lambda_s$ be two eigenvalues of $M$ and $\vec{v}_r$, $\vec{v}_s$ eigenvectors associated to them, i.e.\ $M \vec{v}_j = \lambda \vec{v}_j$ for $j = r, s$. We have $M \vec{v}_r (\vec{v}_s)^T + \vec{v}_r (\vec{v}_s)^T M^T = (M \vec{v}_r)(\vec{v}_s)^T + \vec{v}_r \bigl( M \vec{v}_s \bigr)^T = \lambda_r \vec{v}_r (\vec{v}_s)^T + \lambda_s \vec{v}_r (\vec{v}_s)^T$, so $\vec{v}_r (\vec{v}_s)$

is an eigenmatrix of $L_M$ with the eigenvalue $\lambda_r + \lambda_s$.

Notice that if $\lambda_r \ne \lambda_s$ then vectors $\vec{u}, \vec{w}$ are linearly independent and matrices $\vec{u}(\vec{w})^T$ and $\vec{w}(\vec{u})^T$ are linearly independent, too. This implies that the eigenvalue $\lambda_r + \lambda_s$ is double if $r \ne s$.

The map $L_M$ maps $n^2$–dimensional linear space into itself, so it has at most $n^2$ eigenvalues. We already found $n^2$ eigenvalues, so there exists no more and the problem is solved for the special case.

In the general case, matrix $M$ is a limit of matrices $M_1, M_2, \dots$ such that each of them belongs to the special case above. By the continuity of the eigenvalues we obtain that the eigenvalues of $L_M$ are

• $2 \lambda_r$ with multiplicity $m_r^2$ ($r = 1, \dots, k$);
• $\lambda_r + \lambda_s$ with multiplicity $2 m_r m_s$ ($1 \le r < s \le k$).

(It can happen that the sums $\lambda_r + \lambda_s$ are not pairwise different; for those multiple values the multiplicities should be summed up.)