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