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

Question

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

Answer 1

$$\pmatrix{0&1&.5\cr1&0&.5\cr0&0&0\cr}$$ has $-1$ as an eigenvalue.

Answer 2

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

Answer 3

All examples in the answers given so far are block triangular with a permutation matrix as the diagonal block with the critical eigenvalue.

If you want something different, you can take $$ M = \begin{bmatrix} A & 0 & 0\\ 0 & 0 & A\\ 0 & A & 0 \end{bmatrix}, \quad A = \begin{bmatrix}1/2 & 1/2 \\ 1/2 & 1/2\end{bmatrix}. $$ This matrix has a diagonal that is not all zero, and contains no entries equal to 1.

Answer 4

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