Largest eigenvalue of a simple graph

Question

Let $\Gamma$ be a simple graph with $n$ vertices, $e$ edges and largest eigenvalue $\lambda_{max}$. Show that $\lambda_{max} = \frac{2e}{n}$ iff $\Gamma$ is regular.

I've already shown the if part, which is kinda obvious.

For the converse, I have no idea how to prove it. I've already checked in the internet and even here in MathStackExchange but found almost no clue, and the clue that I found was not useful at all (I will put a link to it). Can someone give me a really useful hint?

Do I need any deep knowledge in Linear Algebra that I don't know because I had not been taught?

I'm currently taking a course in Combinatorics, in a master's degree, and this is part of a suggested exercise by the Professor after a class.

Largest eigenvalue of the adjacency matrix of a graph

Answer 1

By Rayleigh-Ritz, the maximum eigenvalue satisfies:

$$\lambda_1 = \max \frac{v^T A v}{v^T v}.$$

Now, consider the vector $\mathbb{1}$ of all $1.$ Then, $$\mathbb{1}^t A \mathbb{1}=$\frac1n \sum_{j, j} A_{ij} = \frac{2e}n,$$ so $\lambda_1 \geq \frac{2e}n$ (which is the average degree). We have equality if and only if $\mathbb{1}$ is an eigenvector, which means that the graph is regular (notice that a non-negative matrix has at most one non-negative eigenvector).

Answer 2

We should assume that $A$ is connected/irreducible-- otherwise recurse on each irreducible component. Mapping this over to quasi-Markov chain territory: First, by divide by $\frac{2e}{n}$. In this setup $A$ being regular is now called being doubly stochastic (and conversely being doubly stochastic implies regularity).

averaging over all $n\times n$ permutation matrices
$A':=\frac{1}{n!}\sum_{k} \big(P^{(k)}\big)A\big(P^{(k)}\big)^T$
(where $A'$ is necessarily doubly stochastic)

there are two ways to finish
(1) Use sub-additivity of operator 2 norm
$1=\Big \Vert A'\Big \Vert_2=\frac{1}{n!}\Big \Vert\sum_{k} \big(P^{(k)}\big)A\big(P^{(k)}\big)^T\Big \Vert_2\leq \frac{1}{n!}\sum_{k} \Big \Vert\big(P^{(k)}\big)A\big(P^{(k)}\big)^T\Big \Vert_2=\Big \Vert A\Big \Vert_2 = \lambda_1$
with equality iff each graph isomorphic representation of $A$ has a Perron vector in common, i.e. iff the Perron vector is invariant to permutation.

(2) A different way of looking at the equality conditions: $\mathbf v:= \frac{1}{\sqrt{n}}\mathbf 1$
$1=\Big \Vert A'\Big \Vert_2= \mathbf v^T A'\mathbf v = \frac{1}{n!}\sum_{k}\mathbf v^T\big(P^{(k)}\big)A\big(P^{(k)}\big)^T\mathbf v= \frac{1}{n!}\sum_{k}\mathbf v^TA\mathbf v = \mathbf v^TA \mathbf v\leq \lambda_1$
with equality iff $\mathbf v$ is the Perron vector of $A$, that is iff $A$ is doubly stochastic