Computing an induced matrix norm 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?
 A: 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$.  
A: 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^*\|$.
