Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A random walk matrix has largest eigenvalue 1 with multiplicty 1 - why?

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

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)

ii) Second, one can observe that the all-one vector scaled by $1/n$ is an eigenvector of $A$ for the eigenvalue $1$

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$

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.

Can somebody help me?

share|improve this question
    
Is this homework? –  Jonas Meyer Nov 25 '09 at 21:44
1  
It has been - almost one year ago, in a Computational Complexity course. It already got my grades there - well, I am going to dvelve into this for my thesis, so I started repeating the matter. That's it. Therefore it is not MY homework, nor does anything for me crucially depend on this getting solved. –  shuhalo Nov 25 '09 at 21:57

5 Answers 5

up vote 5 down vote accepted

Here is a simple proof.

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

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.

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.

share|improve this answer

For large enough n, the matrix B = A + A2 + ... + An 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.

Any eigenvector of A with eigenvalue λ is an eigenvector of B with eigenvalue f(λ)=λ+λ2+...+λn, and f(λ) is maximized on [-1,1] at λ=1, so if there were two independent eigenvectors of A with λ=1 then B would have two independent eigenvectors achieving the maximal eigenvalue f(1) and this is a contradiction.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Markov Chain theory shows that such a walk has a unique stationary distribution, yielding the answer to your question/

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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