This is sort of complementary to this thread. I’ll repeat the definitions here:
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).
Denote by $c(M)$ the number of pairs of non-real eigenvalues in $TS(M)$. By definition, $c(M)\leqslant n! \cdot [n/2]$.
For given $n$, what is $\max c(M)$?
For $n=3$, $\max c(M)=6$ can be easily attained.
For $n=4$, we have $c(M)\leqslant48$, but it seems like $\max c(M)=36$, which is made plausible not only by the graphic below but also by the observation that the eigenvalues of the extremal matrices seem to exhibit a certain pattern:
If $ c(M)=36$, then in the set of the 24 matrices obtained by row permutations of $M$, there are $12$ with one pair of complex eigenvalues and $12$ with two pairs, moreover (which should not come as a surprise) those two sets of $12$ correspond to the even and the odd permutations of $S_4$.
The following is a bit weaker and more accessible, but it is easy to see that it is equivalent to the above one:
Conjecture: For a real $4\times4$ matrix $M$, if $ c(M)=36$, then swapping two lines changes the number of real eigenvalues by 2.
Is there an expert in linear algebra who can prove that assertion, and prove moreover that $36$ is the maximal possible number of complex EV pairs?
The distribution of $c(M)$ for 80,000 $4\times4$ matrices with random entries in $[-1,1]$ looks approximately as follows:
For $n=5$, we have $c(M)\leqslant 240$, and I have found experimentally $\max c(M)\geqslant 228$. Unlike the $n=4$ case, for an extremal $M$ there is no particular structure in the set of ‘exceptional’ permutations of $S_5$, i.e. the ones producing the $12$ matrices which have only two instead of four complex eigenvalues. So it is not clear if it is reasonable to conjecture that $228$ is sharp.
