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

**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&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=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. 

I couldn't resist to try $n=6$, where each TS takes my poor computer already about 3 sec. But so far, I am only as low as $c(M)=150$ Compare $c(I)=948$.
  [1]: http://mathoverflow.net/questions/131650/eigenvalues-of-permutations-of-a-real-matrix-how-complex-can-they-be