6
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ 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$.) $\endgroup$
    – Yemon Choi
    Nov 14, 2011 at 3:57
  • $\begingroup$ Note that if $\bf v$ is an eigenvector for any eigenvalue other than 1 then $\bf v$ is orthogonal to the all-ones vector. $\endgroup$ Nov 14, 2011 at 4:12

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Nov 14, 2011 at 11:44
  • $\begingroup$ just because I don't know how to explain that of the author: the eigenvalues are real. $\endgroup$ Nov 14, 2011 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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