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

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

-
Wow, impressive! – Suvrit Jun 4 '13 at 20:19
This is an interesting question but I have some trouble reproducing the examples. For instance, if I take the $3 \times 3$ matrix in the first example I get $c(M)=4$ instead of zero. (If you change places between the 1st and the 3rd rows, you get a matrix whose char. poly. is $x^{3}-x^{2}+2x-2$ which has two non-real roots. There is also another pair of non-real eigenvalues). Perhaps there is a bug in the OP's program. – Felix Goldberg Jul 4 '13 at 20:50
I also get $c(I_{5})=8$ so this is all very odd - perhaps I am missing something? – Felix Goldberg Jul 4 '13 at 21:09
You are right for the first 3x3 one. I don't know what happened. Maybe a simple typo. Did you check my other ones? – Wolfgang Jul 5 '13 at 7:33
for $c(I_n)$, each cycle of length $d$ in a permutation contributes [(d-1)/2] conjugate pairs. $c(I_5)=118$ is correct. – Wolfgang Jul 5 '13 at 7:34

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()
z = z + gp.polsturm(u) + 6 - u.degree() // adds 6 iff all roots are real
return z

-
Yes, I am fully with you. The "stretching" of these matrices (i.e. increasing $T$) doesn't seem to remove real eigenvalues, if T is big enough. I see that in rank 6, looking at the sequence 13,7,21,7,13 in your example, like me you did not yet succeed in finding a matrix such that all diagonals (in your notation) are "concave", let alone constant (i.e. 'triangular' Hankel matrices in my notation). But by the same "possibly irrational exuberance", I'd expect those to exist, too (like for $n\le 5$). When I have time, I'll play more. I don't understand though why you mention "complex hull"? – Wolfgang Aug 11 '13 at 18:00
The "hull complex" is a tool in commutative algebra that is not particularly relevant to this problem. An explanation is in chapter 4 of Miller, Sturmfels Combinatorial Commutative algebra. I simply noticed that the construction of the hull complex uses a large parameter $T$ that is eventually thrown away. As far as my rank 6 answer goes, I decided to initialize my optimization by taking base 2 logs of the non-diagonal entries of your near-solution. Unsurprisingly, I didn't need to change much to get an actual solution. – S. Carnahan Aug 12 '13 at 0:06
@Wolfgang I am unable to get all real eigenvalues in rank 7. Using a similar program, I have been unable to reduce the defect below 648 (which seems to be a broad local minimum), even after destroying the symmetry. Here is one of the minimal exponent collections: 0,59,75,99,108,132,52 | 0,27,101,107,111,124 | 0,85,107,109,104 | 0,88,105,104 | 0,40,73 | 0,56 | 0 – S. Carnahan Sep 6 '13 at 18:09
Well, my best attempt was inspîred by your rank 5 example. I noticed that the exponents 0,3,5,6 (ignoring the last one, which can be anything from 0 to 6) have differences 3,2,1. And generalising this seems quite promising as a start: Taking 0,4,7,9,10,x for rank 6 yields a defect of 11 (and now I don't believe anymore that a solution with constant diagonals is possible for n>5). Likewise, 0,5,9,12,14,15,x for rank 7 yields only 70, much better than your 648. (Here x can be anything between 0 and 10 resp. 15). Even a slight modification of one of these exponents increases the defect strongly. – Wolfgang Sep 7 '13 at 19:00
(cont'd) This can certainly be improved by breaking the symmetry for n=7. My code takes 3 min, so I left it there. (for the moment) :) For n=7 and T=4, more than half of the complex roots have |Im/Re|<.025, so there is much room for improvements. – Wolfgang Sep 7 '13 at 19:04

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.

-

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

-

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

-
Looks interesting. But if I am right that e.g. $A_5=\pmatrix{0&1&0&0&0\cr-1&0&1&0&0\cr0&-1&0&1&0\cr0&0&-1&0&1\cr0&0&0&-1&0}$, then for odd $n$, $A_n$ is not invertible. And I find $c(A_5)=110$ (the EV $\pm i$ alone occur 14 times) and $c(A_6)=1274.$ Are you sure your program runs through all the $n!$ permutations? I use the numtoperm function in Pari. – Wolfgang Jul 5 '13 at 7:36
@Wolfgang I mean a different kind of matrix. I've added now an example that shows what I mean. The downside is that the matrix is singular. – Felix Goldberg Jul 5 '13 at 8:48
However, it might be possible to play a bit with it and obtain a similar non-singular matrix. – Felix Goldberg Jul 5 '13 at 8:49
For $c(M)$, that is the same as diag(1,1,1,1,0). I find $c(M)=22$ here: 6 pairs $\pm i$ and 16 pairs of 3rd roots of unity. BTW, I really doubt that this can lead to a "similar non-singular matrix": if all EVs of a matrix are 0, a small perturbation will produce "lots" of complex roots. :( Believe me, it seems hopeless to start with a singular matrix! – Wolfgang Jul 5 '13 at 9:24