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

Setup

Let $A$ be a stochastic matrix.

Let the eigenvalues of $A$ be $1 = \lambda_1 \geq \lambda_2 \geq \lambda_3 ... \geq -1$.

Let $\lambda = \max_{x: x \perp 1} \frac{||Ax||}{|| x ||}$

Question:

Besides $\lambda_2 \leq \lambda$, is there any relation between $\lambda$ and $\lambda_2$? In particular, I would love to see something of the form $\lambda \leq \lambda_2$.

Context:

Reading about expanders. Many of the proofs appears to prove upper bounds on $\lambda_2$, but I want upper bounds on $\lambda$, and it's not obvious to me:

(1) how an upper bound on $\lambda_2$ becomes an upper bound on $\lambda$ or (2) how to generalize some of these proofs.

Thanks!

share|improve this question
    
I think some stochastic matrices have complex eigenvalues; so are you assuming some other conditions on $A$ at the start? (These might be relevant if you are trying to get relations between $\lambda$ and $\lambda_2$.) –  Yemon Choi Nov 14 '11 at 3:57
    
Note that if $\bf v$ is an eigenvector for any eigenvalue other than 1 then $\bf v$ is orthogonal to the all-ones vector. –  Gerry Myerson Nov 14 '11 at 4:12
add comment

1 Answer 1

The answer is due to Boyd, Diaconis, Sun & Xiao. If $A$ is a symmetric and bi-stochastic, then $\mu:=\max(\lambda_2,-\lambda_n)$ satisfies $$\mu\ge\cos\frac\pi{n}.$$ In addition, there exists such a matrix for which the equality holds. See Exercise 164 of my list http:\www.umpa.ens-lyon.fr/~serre/DPF/exobis.pdf .

P.S. Because you assume that the eigenvalues are real, I presume that you have in mind that the matrix is symmetric.

share|improve this answer
    
But it is possible for the eigenvalues to be real even if the matrix is not symmetric, so I'm not sure why you make that assumption. –  Gerry Myerson Nov 14 '11 at 11:44
    
just because I don't know how to explain that of the author: the eigenvalues are real. –  Denis Serre Nov 14 '11 at 12:23
add comment

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.