positive Markov Matrix

Question

For a positive Markov matrix which satisfy 1) every element is positive 2) each column sums to 1. It's easy to prove that 1 is a eigenvalue and every $ | \lambda | \leq 1 $. However, is there any way to prove that $ \lambda \neq -1 $ ?

Answer 1

Here is a quick proof of 1:

Because the entries of $A$ are positive, there exists an $\alpha > 0$ for which $A - \alpha I$ has positive entries. Define $B = \frac 1{1 - \alpha}(A - \alpha I)$. We note that $B$ is a positive Markov matrix, which means that every eigenvalue $\mu$ of $B$ satisfies $|\mu| \leq 1$. On the other hand, we have $$ A = \alpha I + (1 - \alpha) B, $$ which means that each eigenvalue $\lambda$ of $A$ satisfies $\lambda = \alpha + (1 - \alpha )\mu$ for some eigenvalue $\mu$ of $B$. Now, argue that if $|\mu| \leq 1$ and $\mu \neq 1$, then $|\alpha + (1 - \alpha) \mu| < 1$.

---

Fact 2 can be proved using the following fact:

Claim 1: If $x \in \Bbb C^n$ is such that $Ax = x$, then we also have $A|x| = |x|$.

Using this, prove

Claim 2: If $x \in \Bbb C^n$ is such that $Ax = x$, then there is a vector $v > 0$ for which $x = \alpha v$ (for some $\alpha \in \Bbb C$).

From there, suppose for the purpose of contradiction that there exist linearly independent vectors $x,y$ for which $Ax = x$ and $Ay = y$. Without loss of generality, take $x>0,y>0$ (via Claim 2). Argue that there exist non-zero real coefficients $c_1,c_2$ for which $z = c_1 x + c_2 y$ has at least one zero entry. Now, $Az = z$, but there is no $\alpha \in \Bbb C$ and $v > 0$ for which $z = \alpha v$, which contradicts Claim 2.

Answer 2

Suppose $(\lambda,x)$ is a left eigenpair of $A$ for some eigenvalue $\lambda\in\mathbb C$ with unit modulus. By scaling $x$, we may assume that $x_j=\max_i|x_i|=1$. By equating the $j$-th entries on both sides of $|\lambda x^T|=|x^TA|$, we obtain $1=|\lambda x_j|=|\sum_ix_ia_{ij}|\le\sum_i|x_i|a_{ij}\le\sum_ia_{ij}=1$. Therefore $x_i=1$ for all $i$ and $\lambda=1$.

Answer 3

This is an immediate result from applying Gerschgorin Discs -- in particular draw this out!
The symbol manipulation using triangle inequality is below, but the sketch is probably even more compelling.

Since each $a_{k,k} \gt 0$ and each row sum is 1 (with positive only components), each disc $k$ has radius
$r_k =\sum_{j\neq k}\big \vert a_{k,j}\big \vert =\sum_{j\neq k} a_{k,j}$

Then the boundary of disc $k$ is given by
$a_{k,k} + e^{i\theta}r_k$ for $\theta \in [0,2\pi)$ and
$\big \vert a_{k,k} + e^{i\theta}r_k\big \vert \leq \big \vert a_{k,k}\big \vert + \big \vert e^{i\theta}r_k\big \vert = a_{k,k} + r_k \big \vert e^{i\theta}\big \vert +a_{k,k} + r_k =1$

by Triangle Inequality, with equality iff $a_{k,k}$ and $e^{i\theta}r_k$ are on the same ray emanating from the origin -- i.e. iff they are both on the positive half of the real line ($\theta =0$).

Now this holds for all $k\in\big\{1,2,...,n\big\}$ so we have a uniform bound-- the maximum modulus for an eigenvalue of $A$ is 1 and this can only be reached on the ray given by the positive half of the real-line, i.e. when $\lambda =1 $. And conversely $-1$ is outside the boundary of every Gerschgorin Discs so $-1$ cannot be an eigenvalue of $A$.