How to show $\|A\|_2 \leq t$ implies $ t^2I-A^TA \succeq 0$?

Question

Let $A \in \mathbb{R}^{n \times n}$ and $\|A\|_2$ be the spectral norm of the matrix defined as the largest singular values of the matrix.

How to show when the maximum singular value is bounded, then $t^2I-A^TA$ is positive semi-definite. Formally,

$\|A\|_2 \leq t$ implies $ t^2I-A^TA \succeq 0$?

Answer 1

Hint: For each $x \in \mathbb R^d$ you have

$$x^T(t^2I-A^TA)x=t^2\|x \|_2^2 - \| Ax \|_2^2 \geq 0$$

Answer 2

The following facts are useful to know:

• $\lambda$ is an eigenvalue of $M$ if and only if $\lambda + c$ is an eigenvalue of $cI + M$. This is true because $Mx = \lambda x \iff (M + cI)x = (\lambda + c)x$.
• The spectral norm of a matrix $A$ with real entries is the square root of the maximum eigenvalue of $A^T A$.
• A real symmetric matrix is positive semidefinite if and only if its eigenvalues are nonnegative.

The eigenvalues of $t^2 I - A^T A$ are given by $t^2-\lambda$, where $\lambda$ is an eigenvalue of $A^T A$. Because $\|A\|_2 \leq t$, we know that the square root of the maximum eigenvalue of $A^T A$ is less than or equal to $t$. It follows that $t^2 I - A^T A$ has nonnegative eigenvalues. In other words, $t^2 I - A^T A$ is positive semidefinite.