33
$\begingroup$

This may be a trivial question yet I was unable to find an answer:

$$\left \| A \right \| _2=\sqrt{\lambda_{\text{max}}(A^{^*}A)}=\sigma_{\text{max}}(A)$$

where the spectral norm $\left \| A \right \| _2$ of a complex matrix $A$ is defined as $$\text{max} \left\{ \|Ax\|_2 : \|x\| = 1 \right\}$$

How does one prove the first and the second equality?

$\endgroup$
  • $\begingroup$ What are your thoughts on the second equality? $\endgroup$ – Git Gud Nov 30 '13 at 11:35
  • $\begingroup$ @GitGud Oh, does that mean singular values are defined in this way, i.e., the second equality is a definition? $\endgroup$ – mathemage Nov 30 '13 at 12:23
  • $\begingroup$ It's not a definition. It's a direct consequence of the definition. Can you see this? $\endgroup$ – Git Gud Nov 30 '13 at 12:26
  • $\begingroup$ @GitGud One normally can't if one does not know about the Courant-Fischer's characterisation. $\endgroup$ – Algebraic Pavel Dec 1 '13 at 2:37
30
$\begingroup$

Put $B=A^*A$ which is a Hermitian matrix.

As a linear transformation of Euclidean vector space $E$ is Hermite iff there exists an orthonormal basis of E consisting of all the eigenvectors of $B$

Let $\lambda_1,...,\lambda_n$ be the eigenvalues of $B$ and $\left \{ e_1,...e_n \right \}$ be an orthonormal basis of $E$

Let $x=a_1e_1+...+a_ne_n$

we have $\left \| x \right \|=\left \langle \sum_{i=1}^{n}a_ie_i,\sum_{i=1}^{n}a_ie_i \right \rangle^{1/2} =\sqrt{\sum_{i=1}^{n}a_i^{2}}$,

$Bx=B\left ( \sum_{i=1}^{n}a_ie_i \right )=\sum_{i=1}^{n}a_iB(e_i)=\sum_{i=1}^{n}\lambda_ia_ie_i$

Denote $\lambda_{j_{0}}$ to be the largest eigenvalue of $B$.

Therefore,

$\left \| Ax \right \|=\sqrt{\left \langle Ax,Ax \right \rangle}=\sqrt{\left \langle x,A^*Ax \right \rangle}=\sqrt{\left \langle x,Bx \right \rangle}=\sqrt{\left \langle \sum_{i=1}^{n}a_ie_i,\sum_{i=1}^{n}\lambda_ia_ie_i \right \rangle}=\sqrt{\sum_{i=1}^{n}a_i\overline{\lambda_ia_i}} \leq \underset{1\leq j\leq n}{\max}\sqrt{\left |\lambda_j \right |} \times (\left \| x \right \|)$

So, if $\left \| A \right \|$ = $\max \left\{ \|Ax\| : \|x\| = 1 \right\}$ then $\left \| A \right \|\leq \underset{1\leq j\leq n}\max\sqrt{\left |\lambda_j \right |}$ (1)

Consider: $x_0=e_{j_{0}}$ $\Rightarrow \left \| x_0 \right \|=1$ so that $\left \| A \right \|^2 \geq \left \langle x_0,Bx_0 \right \rangle=\left \langle e_{j_0},B(e_{j_0}) \right \rangle=\left \langle e_{j_0},\lambda_{j_0} e_{j_0} \right \rangle = \lambda_{j_0}$ (2)

Combining (1) and (2) gives us $\left \| A \right \|= \underset{1\leq j\leq n}{\max}\sqrt{\left | \lambda_{j} \right |}$ where $\lambda_j$ is the eigenvalue of $B=A^*A$

Conclusion: $$\left \| A \right \| _2=\sqrt{\lambda_{\text{max}}(A^{^*}A)}=\sigma_{\text{max}}(A)$$

$\endgroup$
  • $\begingroup$ Why is $A^*A$ a unitary matrix? For $A$ as a zero matrix or a general real diagonal matrix, this doesn't have to be unitary, right? $\endgroup$ – mathemage Nov 30 '13 at 16:29
  • 2
    $\begingroup$ That's my mistake. That should be Hermite. Got fixed! $\endgroup$ – An Khuong Doan Nov 30 '13 at 16:58
  • $\begingroup$ I think I understood the proof except for one part: in the "iff" statement, why does the reverse implication hold? For any unitary $U$ and diagonal non-Hermitian $\Lambda$ the matrix $B = U^\dagger \Lambda U$ has eigenvectors forming orthonormal basis (namely, columns of $U$). However, $B$ is not Hermitian since $\Lambda$ is not. This is a counterexample, right? $\endgroup$ – mathemage Dec 1 '13 at 19:09
  • 2
    $\begingroup$ And (2) is still blur to me: how can we say $$\left \| A \right \| \geq \left \langle x,Bx \right \rangle=\left \langle e_{j_0},B(e_{j_0}) \right \rangle$$ $\endgroup$ – sleeve chen Jan 21 '15 at 0:01
  • 1
    $\begingroup$ @sleevechen for (1) we can say it because $\left \| A \right \|$ is the maximum of all the elements in the set, and it was just shown that each element is $\leq $ the largest singular value times $\left \| x \right \| = 1$. For (2), since $\left \| A \right \|$ is the maximum, it must be $\geq$ than any particular element, namely $\left \| A {e_j}_0 \right \|=\left \| A{e_j}_0\right \|=\left \langle A{e_j}_0,A{e_j}_0 \right \rangle=\left \langle {e_j}_0,A^*A{e_j}_0 \right \rangle=\left \langle {e_j}_0,B{e_j}_0 \right \rangle$ $\endgroup$ – ignoramus Jun 8 '16 at 11:40
19
$\begingroup$

First of all, $$\begin{align*}\sup_{\|x\|_2 =1}\|Ax\|_2 & = \sup_{\|x\|_2 =1}\|U\Sigma V^Tx\|_2 = \sup_{\|x\|_2 =1}\|\Sigma V^Tx\|_2\end{align*}$$ since $U$ is unitary, that is, $\|Ux_0\|_2^2 = x_0^TU^TUx_0 = x_0^Tx_0 = \|x_0\|_2^2$, for some vector $x_0$.

Then let $y = V^Tx$. By the same argument above, $\|y\|_2 = \|V^Tx\|_2 = \|x\|_2 = 1$ since $V$ is unitary. $$\sup_{\|x\|_2 =1}\|\Sigma V^Tx\|_2 = \sup_{\|y\|_2 =1}\|\Sigma y\|_2$$ Since $\Sigma = \mbox{diag}(\sigma_1, \cdots, \sigma_n)$, where $\sigma_1$ is the largest singular value. The max for the above, $\sigma_1$, is attained when $y = (1,\cdots,0)^T$. You can find the max by, for example, solving the above using a Lagrange Multiplier.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.