Markov matrices with no ones on off-diagonals don't have -1 as an eigen value

Question

Every time I saw a Markov matrix with an Eigen value of -1, it had some 1's on its off-diagonals. The most obvious example is a simple permutation matrix:

$$M = \left(\begin{array}{ccc}0&1\\1&0\end{array}\right)$$

With eigen values 1 and -1. As soon as you subtract $\epsilon$ from the 1's and add them to the 0's, the -1 eigen value decreases in magnitude.

For another example, see the matrix $M$ this answer. Again, an eigen value of -1 with multiple 1's on the off-diagonals.

Is there a way to prove or refute this claim?

All I have so far are examples to support it and haven't been able to come up with a direction for how to prove it.

---

Why do I care about this result? Because I'm considering Markov matrices formed from coin flips where the coins can never be one-sided. Such matrices might have 1's on their diagonals, but never on the off-diagonals.

If this is true, we can write for such a matrix $M$,

$$vM^n = c_1+c_2\lambda_1^n+\dots$$

Since $\lambda_1$ and other eigen values must be $<1$, we can say as $n \to \infty$,

$$vM^n = c_1$$

Answer 1

Yes, there's a way to refute the claim - a counterexample.

The matrix $\begin{bmatrix}0&0&\frac12&\frac12\\ 0&0&\frac12&\frac12\\ \frac12&\frac12&0&0\\ \frac12&\frac12&0&0\end{bmatrix}$ has $-1$ as an eigenvalue with eigenvector $\begin{bmatrix}1\\1\\-1\\-1\end{bmatrix}$.

Eigenvalues of $-1$ are associated with bipartite graphs; if every step alternates between two subgraphs, there will be an eigenvector for $-1$ weighting everything in one of those subgraphs positive and everything in the other negative. Other roots of unity are associated with directed cycles of longer lengths; they're less likely to come up unless you specifically rig the system to get them, but they're possible.

Answer 2

Too long for a comment.

The only thing that can derail my argument in the blog is if the matrices have an eigen value, -1

Then eigenvalue $−1$ of the matrix $M$ does not cause big problems for the investigation, because to it correspond an eigenvalue $1$ of the matrix $M^2$, and we can consider the convergence of odd and even powers separately. This is a direction in which I 'm going to continue my answer to the linked question.

The same approach is applicable for eigenvalues $\xi$ which are roots of unity of a small order $m$. Moreover, if all entries of $n\times n$ matrix $M$ are rational, then order $[\Bbb Q(\xi):\Bbb Q]$ of the extension $\Bbb Q(\xi)$ over $\Bbb Q$ is at most $\varphi(m)$, where $\varphi$ is the Euler function (see, for instance, [L, Ch. VIII, $\S$3, Theorem 6]). This allows us bound $m$ in terms of $n$ as follows.

Let $m=p_1^{m_1}\dots p_k^{m_k}$ be a product of powers of distinct primes. Then, according to [M]

$$\varphi(m)=m\left(1-\frac 1{p_1}\right)\dots\left(1-\frac 1{p_k}\right)\ge \frac{cm}{\log_e \log_e m}.$$

I guees that $c$ is a constant. Then more aysmpotically weak but more concrete lower bound for $\varphi(m)$ follows from an observation that $k\le\log_2 m$ and $1-\frac 1{p_i}\ge 1-\frac 1{i+1}$ for each $i$, so

$$\varphi(m)\ge m\frac 12\frac 23\cdots\frac k{k+1}=\frac m{k+1}\ge \frac{m}{\log_2 m +1}.$$

References

[L] Serge Lang, Algebra, Addison-Wesley Publ., 1965 (Russian translation, M.:Mir, 1968).

[M] Mathematical encyclopedia, vol. 5, 1985 (in Russian).