Show, for a real, symmetric matrix, that $\| A\|_2^2 \leq \frac{n-1}{n} \|A\|_F^2$.

Question

I recently had an exam with the following question that I just couldn't get a start on:

Suppose $A \in \mathbb{R}^{n \times n}$ is symmetric and such that $\mbox{tr}(A)=0$. Show that $$\| A \|_2^2 \leq \frac{n-1}{n} \| A \|_F^2$$ Is the assumption that $\mbox{tr}(A)=0$ necessary? Provide an example or counter-example.

Could anyone get me started on the right way to think on this?

Answer 1

First of all observe that $trA = 0$ is necessary. If $A$ has only one nonzero element $\alpha$ that is placed on diagonal then $||A||_2 = ||A||_F = |\alpha|$ and inequality doesn't hold.

Now suppose that $trA = 0$. Let $|\lambda_1| \ge |\lambda_2| \ge \dots \ge |\lambda_n|$ be eigenvalues of $A$. Then $||A||_2^2 = \lambda_1^2$ and $||A||_F^2 = \sum_{i = 1}^n \lambda_i^2$. But $trA = \sum_{i = 1}^n \lambda_i = 0$. Therefore by Cauchy-Schwarz inequality $$\lambda_1^2 = \left(\sum_{i = 2}^n \lambda_i\right)^2 \le \left(\sum_{i = 2}^n \lambda_i^2\right)\left(\sum_{i =2}^n 1\right) = (n-1)\left(\sum_{i = 2}^n \lambda_i^2\right)$$ which then gives the inequality $$ n||A||_2^2 = n \lambda_1^2 \le (n-1)\left(\sum_{i = 1}^n \lambda_i^2\right) = (n-1)||A||_F^2 $$

Answer 2

$\mathrm{tr}(A) = 0$ is necessary, otherwise we could have $A = \mathrm{diag}(1,0,\dots, 0)$ in which case $\|A\|_2 = \|A\|_F = 1$.

Recall that trace is the sum of eigenvalues. Similarly, operator norm is the max of the abs values of the eigenvalues, and $\|A\|_F = \sqrt{\mathrm{tr}(A^TA)} = \sqrt{\mathrm{tr}(A^2)}$ is the 2-norm of the vector of eigenvalues.

So let $A$ have eigenvalues $(v_1, \dots, v_n)$ with $\sum v_i = 0$. We want to argue that $\max v_i^2 \le \frac{n-1}{n} \sum v_i^2.$

Wlog, we can asume that $\arg\max v_i^2 = n.$ Now consider the convex program $$ \min_{v_1, \dots, v_{n-1}} v_n^2 + \sum v_i^2 \quad \textrm{s.t. } v_n + \sum v_i = 0, |v_i| \le |v_n|.$$ This can be analysed easily - if we didn't have the box conditions, the optimal solution would be $(v_1, \dots, v_{n-1}) = -\frac{1}{n-1} (v_n, v_n, \dots v_n).$ This is also feasible for the box solution for $n \ge 2$, so it is also the optimum there, giving the minimum value $\frac{n}{n-1} |v_n|^2 = \frac{n}{n-1} \|A\|_2^2.$