A random walk matrix has eigenvalue 1 with multiplicty 1 - why? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T08:16:49Z http://mathoverflow.net/feeds/question/6845 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/6845/a-random-walk-matrix-has-eigenvalue-1-with-multiplicty-1-why A random walk matrix has eigenvalue 1 with multiplicty 1 - why? Martin 2009-11-25T21:19:44Z 2009-11-28T01:19:00Z <p>A random walk matrix has largest eigenvalue 1 with multiplicty 1 - why?</p> <p>Let $G$ be a non-directed, regular connected graph with degree $d$. Let $A$ be its random walk matrix, i.e. it's adjacency matrix, with each entry divided by $d$.</p> <p>i) It is easy to observe that $A$ is symmetric, hence normal, that it has real eigenvalues only and can be diagonalized by a pair of orthogonal matrices (at least if don't mix up something from my past course in linear algebra)</p> <p>ii) Second, one can observe that the all-one vector scaled by $1/n$ is an eigenvector of $A$ for the eigenvalue $1$</p> <p>iii) Furthermore, by observing that for any natural $k$, $A^k$ is doubly-stochastic, too, and applying Gelfands formula with $l^1$-norm, we can see that the spectral norm is $1$</p> <p>It remains to show that $1$ has multiplicity $1$. After hours I couldn't manage to figure this out, although it seems rather simple at first sight. So probably I simply don't know the 'trick', which yields this result.</p> <p>Can somebody help me?</p> http://mathoverflow.net/questions/6845/a-random-walk-matrix-has-eigenvalue-1-with-multiplicty-1-why/6849#6849 Answer by Steven Sivek for A random walk matrix has eigenvalue 1 with multiplicty 1 - why? Steven Sivek 2009-11-25T22:03:01Z 2009-11-25T22:03:01Z <p>For large enough n, the matrix B = A + A<sup>2</sup> + ... + A<sup>n</sup> has positive entries since there's a path of length at most n connecting any two vertices. Thus by the Perron-Frobenius theorem B has a unique maximal eigenvalue and its multiplicity is 1.</p> <p>Any eigenvector of A with eigenvalue &lambda; is an eigenvector of B with eigenvalue f(&lambda;)=&lambda;+&lambda;<sup>2</sup>+...+&lambda;<sup>n</sup>, and f(&lambda;) is maximized on [-1,1] at &lambda;=1, so if there were two independent eigenvectors of A with &lambda;=1 then B would have two independent eigenvectors achieving the maximal eigenvalue f(1) and this is a contradiction.</p> http://mathoverflow.net/questions/6845/a-random-walk-matrix-has-eigenvalue-1-with-multiplicty-1-why/6856#6856 Answer by alex for A random walk matrix has eigenvalue 1 with multiplicty 1 - why? alex 2009-11-25T23:41:26Z 2009-11-25T23:51:27Z <p>Here is a simple proof. </p> <p>Suppose $Ax = x$. Consider the entry of $x$ with the largest absolute value; lets use $x_k$ to denote this entry (e.g. if $x=[1,2,-4,3]^T$, then $k=3, x_k=-4$). Consider the $k$'th row of the equation $Ax=x$; it's telling you that $x_k$ is a convex combination of the $x_i$'s of its neighbors $i$ in the graph $G$. This immediately implies that $x_k=x_i$ for all neighbors $i$ of $k$ in $G$. </p> <p>Now you iterate this argument and apply it to each neighbor $i$ of $k$. Using connectivity of $G$, eventually you get the conclusion that every entry of $x$ equals $x_k$. Thus the only solutions to $Ax=x$ are multiples of the all ones vector.</p> <p>Observe that some of the conditions you imposed were not used: the above proof did not use the fact that $A$ is symmetric or that the graph is regular. </p> http://mathoverflow.net/questions/6845/a-random-walk-matrix-has-eigenvalue-1-with-multiplicty-1-why/6877#6877 Answer by Ori Gurel-Gurevich for A random walk matrix has eigenvalue 1 with multiplicty 1 - why? Ori Gurel-Gurevich 2009-11-26T07:03:52Z 2009-11-26T07:03:52Z <p>Another look at this: an eigenvector with eigenvalue of 1 is just an harmonic function (it's value is the average over neighbors' value). By the maximum principle (the maximum of harmonic function must be on the boundary of the set), it must be constant. Thus the eigenspace is of dimension 1.</p> http://mathoverflow.net/questions/6845/a-random-walk-matrix-has-eigenvalue-1-with-multiplicty-1-why/6917#6917 Answer by gowers for A random walk matrix has eigenvalue 1 with multiplicty 1 - why? gowers 2009-11-26T21:24:58Z 2009-11-26T21:24:58Z <p>I'm pretty sure if you calculate the $\ell_2$ norm of $Av$ (where $A$ is the transition matrix) you find quite easily that it is less than $\|v\|$ with equality if and only if $v$ is a constant vector. </p> http://mathoverflow.net/questions/6845/a-random-walk-matrix-has-eigenvalue-1-with-multiplicty-1-why/7007#7007 Answer by gmatt for A random walk matrix has eigenvalue 1 with multiplicty 1 - why? gmatt 2009-11-28T01:19:00Z 2009-11-28T01:19:00Z <p>Markov Chain theory shows that such a walk has a unique stationary distribution, yielding the answer to your question/</p>