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!

Improve this question
$\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
    Commented 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$
    – Gerry Myerson
    Commented Nov 14, 2011 at 4:12

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Gerry Myerson
    Commented 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$
    – Denis Serre
    Commented Nov 14, 2011 at 12:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .