MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 1 characters in body

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 \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!

1

Stochastic Matrix: Second largest eigenvalue and second largest absolute value of eigen value

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!