# Find a square, stochastic matrix of odd size, not a permutation matrix, with an eigenvalue other than 1 on the unit circle

...or prove that none exists.

Note that such a matrix M couldn't be primitive, so there would be at least one entry equal to zero in every power M^k (Perron-Frobenius theory).

Preferably the matrix would have a diagonal that is not all zero, and at the risk of making the problem imprecise, I'd like to find such a matrix with as few zeros and ones as possible.

Thank you.

• Take a permutation matrix corresponding to an n-cycle – Benjamin Steinberg Apr 12 '16 at 0:49
• Ben, sorry, question fixed. – tarski Apr 12 '16 at 1:34
• The matrix [[0,1,0],[1,0,0],[0,0,0]] meets your description (it has an eigenvalue of -1), but I'm guessing that's not what you intended. Maybe you want to require the eigenvalue to be non-real? – Bill Bradley Apr 12 '16 at 2:37
• @Bill, that's not stochastic (but if you change the last row to $[0,0,1]$, it is). – Gerry Myerson Apr 12 '16 at 2:55
• @GerryMyerson, but if you make said change it becomes a permutation matrix. – tarski Apr 12 '16 at 3:10

$$\pmatrix{0&1&.5\cr1&0&.5\cr0&0&0\cr}$$ has $-1$ as an eigenvalue.
If you want a doubly stochastic matrix, $$\begin{pmatrix} 0&1 & 0&0&0 \\ 1&0 & 0&0&0 \\ 0&0 & 1/3&1/3&1/3 \\ 0&0 & 1/3&1/3&1/3 \\ 0&0 & 1/3&1/3&1/3 \\ \end{pmatrix}$$ has eigenvalue $-1$.
The Karpelevič theorem will make it difficult for the matrix not to at least involve a permutation matrix (notice that the upper-left $2$-by-$2$ block of the matrix given by Gerry is a permutation matrix).
If $C_n$ is the $n$-by-$n$ defined by $C_n = [e_n \mid e_1 \mid \cdots \mid e_{n-1}]$, i.e., $C_n$ is the adjancency matrix of a directed $n$-cycle, where $e_i$ denotes the $i^\text{th}$ canonical basis vector of $\mathbb{C}^n$, then the $n$-by-$n$ (row) stochastic matrix $$M_n := \begin{bmatrix} 0 & e_1^\top \\ 0 & C_{n-1} \end{bmatrix}$$ has spectrum $\sigma(M) = \{ 0, 1, \omega,\dots,\omega^{n-1}\}$, where $\omega:=\exp(2\pi i/n)$. Thus, $M_n$ has $n-2$ eigenvalues (distinct from unity) on the unit-circle.
For instance, the matrix $$M_5= \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ \end{bmatrix}$$ has spectrum $\{0,\pm 1, \pm i\}$.