Bounds on extremal eigenvalues of gram matrix with diagonal entries in $[a, b]$ and off-diagonal entries in $[c, d]$ Consider a square $n \times n$ matrix $H = A^T A$ where $A$ is an $m \times n$ with $m \ge n$.
Knowing that $a \le H_{ii} \le b$ for all $i = 1, \ldots, n$ and that $c \le H_{ij} \le d$ for $i \neq j$, what bounds can be given on the smallest and largest eigenvalue?
I'm particularly interested in a lower bound for the smallest eigenvalue and an upper one for the largest eigenvalue.
 A: Concerning bounds on the highest eigenvalue only:
Upper bound on highest eigenvalue: For any symmetric matrix $S$ we have
$$\lambda_\text{max}(S) \le \|S\|_2 \le \sqrt{\|S\|_1 \|S\|_\infty} = \|S\|_\infty = \max_i \sum_j |S_{ij}|$$
Now write $H = \frac{c + d}2 J + S$ where $J$ is the matrix where every entry is $1$.
Then $\lambda_\text{max}(H) \le \frac{c + d}2 + \lambda_\text{max}(S)$ and the entries of $S$ are now $|S_{ij}| \le \frac{d - c}2$ and $a - \frac{c + d}2 \le S_{ii} \le b - \frac{c + d}2$ so that now we can use the above bound to obtain
$$\lambda_\text{max}(S) \le b - \frac{c + d}2 + (n-1) \frac{d - c}2$$
and thus $\lambda_\text{max}(H) \le b + (n-1) \frac{d - c}2$, which is a substantial improvement over a naive application of the above bound.
Lower bound on highest eigenvalue: For a lower bound on the highest eigenvalue one can use the rayleight quotient $r(x) = \frac{x^T S x}{x^T x} \le \lambda_\text{max}(S)$ and thus using $x = (1, 1, \ldots, 1)^T$:
$$\lambda_\text{max}(S) \ge \frac1n \sum_{ij} S_{ij}$$
Applying this directly to $H$ we obtain that $\lambda_\text{max}(H) \ge \frac1n (n a + (n-1)n c) = a + (n-1) c$
