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][1] 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.*


  [1]: http://mathoverflow.net/questions/131650/eigenvalues-of-permutations-of-a-real-matrix-how-complex-can-they-be