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

Question

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

(The image of the distribution of $c(M)$ in this related thread suggests that the probability for a random $4\times4$ matrix to have $c(M)=0$ must be extremely small, maybe $10^{-20}$ at best.)

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.

UPDATE: Here is a different $M\in GL(4,\mathbb R)$ which should be one of the smallest integer ones with $c(M)=0$: $$ M=\pmatrix{7& 5& 5& 6\cr 5& 3& 7& 2\cr 5& 7& 2& 9\cr 6& 2& 9& 0}$$ It has full rank but, like $J$, is not in the interior of $c^{-1}(0)$, due to the fact that several eigenvalues are repeated in the TS, e.g. the EVs $\pm1$ occur 10 times each and the EV $20$ occurs 12 times.

And finally I have found $M\in GL(5,\mathbb R)$ with $c(M)=0$!! $$M=\pmatrix{\color{red}{4188} &\color{red}{4588}&4948&4925&4919\cr 4948&4979&5001&5008&4990\cr 4988&4989&4989&4998&5065\cr 5077&5032&5005&5015&4948\cr 4966&4923&5096&4948&\color{red}{-24543}}$$

UPDATE 2: Even nicer but very very tight: $$ M=\pmatrix{0&0&1 \cr0&1&3 \cr1&3&2} \qquad M=\pmatrix{0&0&0&1\cr0&0&1&4\cr0&1&5&8\cr1&4&8&2} \qquad M=\pmatrix{0&0&0&0&1\cr0&0&0&1&2\cr0&0&1&144&18\cr0&1&144&5839&409\cr1&2&18&409&3}$$ The existence of $M$'s with such special shapes for $n=3,4,5$ is of course a huge heuristic argument in favor of a positive answer to the initial question.
To find those, I actually minimized instead of $c(M)$ the continuous function $\sum\limits_{z\in TS(M)}\arctan\left|\frac{\Im(z)}{\Re(z)}\right|$. Note that each complex root contributes at worst $\pi/2$ to this sum.

UPDATE 3: I couldn't resist to try $n=6$, even though each TS takes my poor computer already about 3 sec. My best is $c(M)=9$, which seems not too bad compared with $c(I_6)=948$. Here goes: $$M=\pmatrix{0& 0& 0& 0& 0& 6\cr 0& 0& 0& 0& 2& 9204\cr 0& 0& 0& -1& -145& -265335\cr 0& 0& -1& 20 54947& 30426445& 5683742\cr 0& 2& -127& 30426614& 368233489& 735312954\cr 6& 9195& - 265314& 5683632& 735312686& 47613387}$$

Answer 1

This is not a complete answer, but it might help with some higher-rank computations if you decide to do them.

Out of some possibly irrational exuberance, I guessed that if there are any solutions, there should be solutions in the asymptotic unipotent regime, where we don't need to care about fine details of matrix entries, but only roughly how their logarithms compare (if you're familiar with the hull complex, this shouldn't be a new idea to you). We let $T$ be any very large positive number, and choose exponents attached to $T$ for entries above the diagonal. As long as we use positive integer exponents, it usually suffices to optimize when $T$ is 2 or 3.

In rank 3, we have $M = \pmatrix{1 & T^2 & T^3 \\ 0 & 1 & T^2 \\ 0 & 0 & 1 }$ as a satisfactory form. In fact, when we have only 3 entries to vary, it is not too hard to write down all six characteristic polynomials, and the criteria for real roots.

In rank 4 and 5, a small amount of trial and error yields $M = \pmatrix{1 & T^2 & T^3 & T^3 \\ 0 & 1 & T^2 & T^3 \\ 0 & 0 & 1 & T^2 \\ 0 & 0 & 0 & 1}$ and $M = \pmatrix{1 & T^3 & T^5 & T^6 & T^3 \\ 0 & 1 & T^3 & T^5 & T^6 \\ 0 & 0 & 1 & T^3 & T^5 \\ 0 & 0 & 0 & 1 & T^3 \\ 0 & 0 & 0 & 0 & 1 }$.

In rank 6, we have $M = \pmatrix{1 & T^{13} & T^{19} & T^{25} & T^{31} & T^{25} \\ 0 & 1 & T^7 & T^{25} & T^{27} & T^{31} \\ 0 & 0 & 1 & T^{21} & T^{25} & T^{25} \\ 0 & 0 & 0 & 1 & T^7 & T^{19} \\ 0 & 0 & 0 & 0 & 1 & T^{13} \\ 0 & 0 & 0 & 0 & 0 & 1 }$.

There seems to be much more flexibility in choosing the entries far from the diagonal than those that are close.

Working beyond rank 6 is quite cumbersome for me, in part because of the factorial speed penalty, and in part because SAGE hits some array bound - I guess it can only pass 65536 objects to GP in a given session before yelling at me. Here's the basic function I used for working in rank 6:

def char6(a1,a2,a3,b1,b2,c1,c2,d,e):
    z=0
    t = 4
    for g in SymmetricGroup(6):
        s = (g.matrix()*MatrixSpace(QQ,6,6)([1,t^a1,t^b1,t^c1,t^d,t^e,0,1,t^a2,t^b2,t^c2,t^d,0,0,1,t^a3,t^b2,t^c1,0,0,0,1,t^a2,t^b1,0,0,0,0,1,t^a1,0,0,0,0,0,1])).charpoly()
        u = s.radical()
        z = z + gp.polsturm(u) + 6 - u.degree() // adds 6 iff all roots are real
    return z

Answer 2

Here is finally a solution for the $n=7$ case! Putting $T=2$, we have $c(M)=0$, where $$M=\pmatrix {1&T^{17}&T^{{32}}&T^{45}&T^{56}&T^{65}&T^{72} \\0&1&\color{red}2\cdot T^{17}& T^{32}&T^{45}&T^{56} &T^{65} \\0&0&1&\color{red}{\frac98}\cdot T^{17}& \color{red}{\frac{171}{64}} \cdot T^{32}&T^{45}&T^{56} \\0&0&0&1&\color{red}{\frac98}\cdot T^{17} &T^{32}&T^{45} \\0&0&0&0&1&\color{red}2\cdot T^{17}&T^{{32}} \\0&0&0&0&0&1&T^{17} \\0&0&0&0&0&0&1} $$

Similarly to what I had said in the comments of S. Carnahan's answer, this is again based on a triangular matrix $A$ with constant diagonals, given by $A_{ij}=T^{k(18-k)}$ where $k=j-i$ for $j\geqslant i$. For this kind of matrices, the TS seems to have very few complex roots (why?), e.g. $m(A)=42$ which is quite a bit less than $m(I_7)=8796$, and with the above adjustments the complex roots of $A$ can be eliminated.
Note that like in the solution for $n=6$ given by S. Carnahan, the first diagonal is not concave.

Answer 3

Is there anything wrong with $GL(2)?$ For that, any diagonal $2\times2$ matrix with positive entries will work...

Answer 4

The matrix $A_{n}$ which is the adjacency matrix of a directed path on $n$ vertices seems to work pretty well.

For example:

$A=\begin{bmatrix}0&1&0&0&0\\\\ 0&0&1&0&0\\\\ 0&0&0&1&0\\\\ 0&0&0&0&1\\\\ 0&0&0&0&0\\\\ \end{bmatrix}$.

Some values I've computed for it:

$c(A_{5})=4$

$c(A_{6})=8$

$c(A_{7})=10$

$c(A_{8})=16$

Perhaps this is related to the OEIS sequence A005232 but computing $c(A_{9})$ was too much for my computer...