Skip to main content
1 of 6
Wolfgang
  • 13.4k
  • 5
  • 45
  • 102

Eigenvalues of permutations of a real matrix: can they all be real?

For a matrix $M\in GL(n,\mathbb R)$, consider the $n!$ matrices obtained by permutations of the rows (say) of $M$ and define the total spectrum $TS(M)$ as the union of all their spectra (counting repeated values separately).

Can all these $n!\cdot n$ eigenvalues be real?

Denote by $c(M)$ the number of pairs of non-real eigenvalues in $TS(M)$.
For a matrix of rank 1, its TS is trivially real. But trying a continuity argument in a neighborhood of such a matrix will fail miserably, e.g. if $J=J_n$ denotes the all-1-matrix and $I=I_n$ the unit matrix, it is easy to show that $c(J+\epsilon I)=c(I)$ for all $\epsilon\in\mathbb R$ (corresponding permutations of both matrices have the same eigenvalues), but $c(I)$ is far from $c(J)=0$, e.g. $c(I_5)=118$.

Examples for $c(M)=0$:

For $n=3$, take $M=\pmatrix{ 4&3&0\cr2&1&-2\cr0&0&1}$.

For $n=4$, take $M=\pmatrix{ 83& 81& 64& 58\cr 79& 67& 65& 63\cr 74& 71& 58& 53\cr 67& 53& 79& 80}$.

For $n=5$, so far I have been only able to get $c(M)$ as low as $11$; one such matrix is $$M=\pmatrix{ 9885& 9887& 9887& 9765& 9894\cr 9887& 9888& 9883& 9887& 9891\cr 9887& 9883& 10013& 9765& 9755\cr 9752& 9762& 10141& \color{red}{7013}& 9789\cr 9772& 10149& 9922& 9654& \color{red}{-47650}}.$$ Note that an environment of $M$ contained in $c^{-1}(11)$ cannot be very ‘big’: change e.g. $M_{1,1}$ by only $\pm.005$ and already $c(M)$ will go up! (Of course my search wasn't for integer matrices, rather once I’d found a real $M$ with $c(M)$ that small, I have tweaked it to obtain a matrix with not-too-big integer entries.)
There should be $M\in GL(5,\mathbb R)$ with $c(M)$ smaller than that, and I'd even conjecture with $c(M)=0$. But given that the average of $c(M)$ for random $5\times5$ matrices appears to be about $175$, finding those is just way beyond my computer’s capacities, and so is the $n\ge 6$ case. Human intelligence is needed.

Wolfgang
  • 13.4k
  • 5
  • 45
  • 102