Computing an induced matrix norm

Question

Assume I have a $n \times n$ matrix and a norm defined as $\|A\| = \max \limits_{x \not = 0}\frac{\|Ax\|}{\|x\|}$, where $\|x\| = \sqrt{\sum x_i^2}$. How can I compute this norm?

Answer 1

Since $\|Ax\|^2 = \langle x , A^* A x \rangle $, and $A^* A \ge 0$ and is Hermitian, we have $\|Ax\|^2 =\langle x , A^* A x \rangle \le \lambda_\max \|x\|^2$ and the maximum is attained for an eigenvector corresponding to the maximum eigenvalue. That is, $\|Ax\| \le \sqrt{\lambda_\max} \|x\|$, or ${ \|Ax\| \over \|x\| } \le \sqrt{\lambda_\max}$ if $x \neq 0$.

Hence $\|A\|_2 = \sqrt{\lambda_\max(A^*A)}$.

Since the non-zero eigenvalues of $A^*A $ and $A A^*$ are the same, we have $\|A\| = \|A^*\|$.

Answer 2

First note that for any matrix $A$, the matrix $A^*A$ is self-adjoint and hence it is diagonalizable. Let $diag(\lambda_1, …., \lambda_n)$ be the diagonal matrix where $\lambda_j$ is the $j$-th eigenvalue of $A^*A$. Then we can let $\sqrt{A^*A} = diag(\sqrt{\lambda_1}, …, \sqrt{\lambda_n})$. Now these values, $\sqrt{\lambda_j}$ are real and are known as the "singular values" of the matrix $A$. You should try to prove for yourself that the largest singular value is equal to the operator norm of $A$.