Operator Norm of a matrix that is the sum of outer product of the columns

Question

For a $n \times m$ matrix with $m \geq n$, I would like to know why $$ \left\|\sum a_i a_i^T \right\| \leq \|A\|^2 $$ where $a_i$ are the columns of $A$ and $\| \cdot \|$ denotes the operator norm.

Answer 1

Hint: $ \sum a_i a_i^T = A A^T $.

Answer 2

In fact it is an equality : Let $B = \sum a_ia_i^T$, then $$\left\| A\right\|^2 = \max_{\left\|x\right\| = 1}\left\|Ax \right\|^2= \max_{\left\|x\right\| = 1}\sum x^Ta_ia_i^Tx = \max_{\left\|x\right\| = 1} x^TBx \le \max_{\left\|x\right\| = 1} \left\|x\right\|\left\|Bx\right\| = \max_{\left\|x\right\| = 1} \left\|Bx\right\| = \left\|B\right\|$$ We use Cauchy-Schwarz inequality to obtain the inequality.

On the other hand $B$ is a positive symmetric matrix then $\left\|Bx\right\| \le \lambda_m \left\|x\right\|$, where $\lambda_m$ is the largest eigen value of $B$. Let $y$ be a unit vector such that $By = \lambda_m y$, then $y^TBy = \lambda_m \left\|y\right\|^2 \ge \left\| B\right\|$. This prove that $\max_{\left\|x\right\| = 1} x^TBx \ge \left\|B \right\|$ and we can conclude from that.

Answer 3

Following up on my hint: Let $ A = U \Sigma V^T $ equal the SVD of $ A $.

Then $$\| A A^T \|_2 = \| U \Sigma V^T ( U \Sigma V^T )^T \|_2 = \| U \Sigma^2 U^T \|_2 = \| \Sigma^2 \|_2 = \sigma_0^2 = \| A \|_2^2 $$ where $ \sigma_0 $ equals the largest singular value of $ A $.

So, indeed, it is an equality.