MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

distribution 4x4

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.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.