Problem: Let $G$ be a $d$-regular graph with adjacency matrix $A$ and eigenvalues $\lambda_1 \geq$ $\lambda_2 \geq \cdots \geq \lambda_n$. Let $\lambda=\max _{i \neq 1}\left|\lambda_i\right|$ be the largest absolute value of an eigenvalue other than $\lambda_1$.
- Find a lower bound (in terms of the degree) on the diagonal entries of $A^2$.
- Show that $$ \lambda \geq(1-\varepsilon(n, d)) \sqrt{d} $$ where $\varepsilon(n, d)$ tends to zero as $n \rightarrow +\infty$. You may use the fact that $\lambda_1 =d$.
My attempt:
For any $i \in \left\{1,\ldots,n\right\}$, we have \begin{align*} (A^2)_{ii} &= \sum_{j=1}^n a_{ij}a_{ji} = \sum_{j=1}^n a_{ij}^2 \\ & \ge \dfrac{1}{n}(\sum_{j=1}^n a_{ij})^2 \tag{C-S inequality}\\ & = \dfrac{d^2}{n} \tag{G is $d$-regular} \end{align*}
Firstly, we diagonalize $A$ as $$A = P^{-1}TP,$$ where $T = \text{diag}(\lambda_1, \ldots, \lambda_n)$ are diagonal eigenvalues matrix.
Hence, $$\text{Tr}(A^2) = \text{Tr}(P^{-1}T^2P) = \text{Tr}(PP^{-1}T^2) = \sum_{i=1}^n \lambda_i^2.$$
By the fact $\lambda_1 = d$ and the definition of $\lambda$, we obtain that \begin{align*} \text{Tr}(A^2) = d^2 + \sum_{i=2}^n \lambda_i^2 \le d^2 + (n-1)\lambda^2. \tag{1} \end{align*} By using the question 1, we have \begin{align*} \text{Tr}(A^2) = \sum_{i=1}^n (A^2)_{ii} \ge \sum_{i=1}^n \dfrac{d^2}{n} = d^2 \tag{2}. \end{align*} Now, I was stuck here. I wonder anyone could give me some hints to deal with the second question.
The diagonal term $(A^2)_{ii}$ is at least $d$: $$ (A^2)_{ii} = \sum_{j = 1}^n a_{ij}^2 \ge \sum_{j = 1}^n a_{ij} = d \hspace{0.25cm} (a_{ij}^2 \ge a_{ij} \ \forall i,j) $$ Thus, by combining the upper bound in your post, we get the following $$ nd \le \text{tr}(A^2) \le d^2 + (n - 1)\lambda^2 $$ or equivalently, $$ \lambda^2 \ge \dfrac{d(n - d)}{n - 1} \ge 0 $$ Therefore, $$ \lambda \ge (1 - \epsilon(n, d))\sqrt{d} $$ where $$ \epsilon(n, d) = 1 - \sqrt{\dfrac{n - d}{n - 1}} \xrightarrow{n \rightarrow \infty} 0 $$