4
$\begingroup$

I am trying to justify fact $ 5 $ in this link which states that if $ A $ is a column stochastic matrix, then $ A $ has eigenvalue $ 1 $ and a unique eigenvector such that all entries are either negative or positive. I have successfully proved that $ A $ has an eigenvalue $ 1 $ but still stuck on the second part of the fact. It seems that this is the Perron Frobenius theorem, but the proof for this theorem requires materials that are beyond a first course in linear algebra that I haven't learned about, so is there any way to prove this fact without using the PF theorem?

$\endgroup$
1
  • $\begingroup$ A crucial assumption is missing in your question (but not in the mentioned fact): in fact 5, $A$ is assumed to be positive. If this requirement is removed, the "fact" is no longer a fact. Counterexample: every positive or negative vector is an eigenvector of $A=I_2$ corresponding to the eigenvalue 1. $\endgroup$
    – user1551
    Jun 26 '16 at 12:32
5
$\begingroup$

For one thing, the eigenvector is unique up to scalar. That's easier to prove for the transpose $A^T$: the only eigenvectors for $1$ are multiples of $(1,...,1)^T.$ If $v$ is any eigenvector, then let $k$ be an index such that $v_k$ is maximal; then $$v = A^T v, \; \mathrm{so} \; v_k = \sum_{i=1}^n a_{ik} v_i \le \sum_{i=1}^n a_{ik} v_k = v_k,$$ and equality implies that all $v_i$ equal $v_k.$

Now that we know this, let $v$ be an eigenvector of $A$. It's enough to show that $|v|$, whose components are the absolute values $|v_k|$, is also an eigenvector.

I will use the notation $v \le w$ and $v < w$ to mean that $v_k \le w_k$ or $v_k < w_k$ for all $k$.

Define $y := A|v| - |v| \ge |Av| - |v| = 0.$ Assume that $y \ne 0$; then $Ay$ and $A|v|$ both have strictly positive elements, so there is $\varepsilon > 0$ with $Ay > \varepsilon A |v|.$ Then $$Ay = A (A|v| - |v|) > \varepsilon A|v|$$ implies $$A^2 |v| = A (A|v| - |v|) + A|v| > (1+\varepsilon) A |v|.$$ By taking the $\ell^1$-norm (i.e. sum of elements), it follows that $$\|A |v|\|_1 = \|A\|_1 \cdot \|A |v|\|_1 \ge \|A^2 |v|\|_1 > \|(1+\varepsilon) A |v|\|_1 = (1+\varepsilon) \|A|v|\|_1.$$ This is a contradiction. So $y = 0$ and $|v|$ was already our eigenvector for $1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.