1
$\begingroup$

I am studying following theorem from Numerical linear Algebra book by Trefethen and Bau.

Theorem : If $A = A^{*}$, then the singular values of A are the absolute values of the eigenvalues of A.

Proof: A Hermitian matrix has a complete set of eigenvectors, and all the eigenvalues are real.

$$(1)\quad A = X \Lambda X^{-1}$$

An equivalent statement that (1) holds with $X$ equal to some unitary matrix $Q$ and $\Lambda$ a real diagonal matrix. But we can write

$$ (2) \quad A = Q \Lambda Q^{*}= Q|\Lambda|sign(\Lambda)Q^{*}$$

where $|\Lambda|$ and $sign(\Lambda)$ denote the diagonal matrix whose entries are the number $|\lambda_{j}|$ and $sign(\lambda_{j})$, respectively. (We could equally well have put the factor $sign(\Lambda)$ on the left of $|\Lambda|$ instead of right). Since sign($\Lambda)Q^{*}$ is unitary whenever Q is unitary, (2) is an SVD of A, with the singular values equal to the diagonal entries of $|\Lambda|$, $|\lambda_{j}|$. If desired, these numbers can be put into non-increasing order by inserting suitable permutation matrices as factors in the left hand unitary matrix of (2), Q , and the right-hand unitary matrix sign$(\Lambda)Q^{*}$.

I cannot follow the logic in this proof after equation (2). Can any one give an insight on this? Thanks in advance.

$\endgroup$
  • $\begingroup$ What is the first statement in the proof that you can't follow? Do you understand the notations $| \Lambda |$, $\mbox{sign}(\Lambda)$, the term "unitary", and the acronym SVD? $\endgroup$ – Brian Borchers Aug 9 '16 at 2:25
  • $\begingroup$ @ Brian Borchers I understood that part, but I do not understand why it is necessary for the proof. $\endgroup$ – Crimson Aug 9 '16 at 2:31
  • $\begingroup$ "I understood that part" Which part did you understand? Which part did you not understand? Is there a sentence that you think could be removed from the proof and still leave a valid proof? If so, are you asking why that sentence was included? $\endgroup$ – Brian Borchers Aug 9 '16 at 2:34
  • $\begingroup$ I understood what are the the notation $ | \Lambda |$ and $sign( \Lambda )$ standing for. More specifically, I don't understand this part " Since sign($\Lambda)Q^{*}$ is unitary whenever Q is unitary, (2) is an SVD of A, with the singular values equal to the diagonal entries of $|\Lambda|$, $|\lambda_{j}|$. " $\endgroup$ – Crimson Aug 9 '16 at 2:40
3
$\begingroup$

The OP has clarified that he doesn't understand the statement "Since sign(Λ)Q∗ is unitary whenever Q is unitary, (2) is an SVD of A, with the singular values equal to the diagonal entries of |Λ|, |λj|. "

To clarify a small technical point, use the convention that $\mbox{sign}(0)=1$ for this proof. If you instead use $\mbox{sign}(0)=0$, then the resulting matrices don't turn out to be orthogonal if there are some $0$ eigenvalues of $A$.

Starting from (2), let

$W^{*}=\mbox{sign}(\Lambda)Q^{*}$.

So, $W$ is a copy of $Q$, possibly with the signs of some columns multiplied by -1. $Q$ is a unitary matrix, that is each pair of columns in $Q$ are orthogonal. Furthermore, each column of $Q$ has length one. Multiplying some subset of the columns of $Q$ by -1 won't change the orthogonality of the columns. Furthermore, each column of $W$ has length one. Thus $W$ is also a unitary matrix.

The Hermitian of any unitary matrix is also unitary, so $W^{*}$ is a unitary matrix too.

Then

$(3)\; A=Q | \Lambda | W^{*}$

where $Q$ and $W$ are unitary matrices and $| \Lambda |$ is a diagonal matrix with nonnegative entries. This is an SVD of the matrix $A$, with $|\Lambda|$ taking the familiar place of $\Sigma$, $Q$ taking the familiar place of $U$ and $W^{*}$ taking the familiar place of $V^{*}$.

The diagonal elements of $| \Lambda |$ are the singular values in this SVD of $A$.

$\endgroup$
  • $\begingroup$ Thanks for your detail explanation. Sorry if my questions sounded stupid but I don't really understand why we need to separate the sign from the value. why couldn't we consider $Q^{*}$ as $V^{*}$? $\endgroup$ – Crimson Aug 9 '16 at 3:11
  • $\begingroup$ Is that because Singular values are needed to be positive? $\endgroup$ – Crimson Aug 9 '16 at 3:14
  • 1
    $\begingroup$ Yes- the singular value decomposition is defined to have nonnegative singular values. $\endgroup$ – Brian Borchers Aug 9 '16 at 3:16
  • 1
    $\begingroup$ There was nothing stupid about your question, but the way in which you initially phrased it was unclear. You'll find that being more precise about exactly what step in a proof you don't understand will make it easier for people to answer your question. $\endgroup$ – Brian Borchers Aug 9 '16 at 3:17
  • $\begingroup$ Thanks for the answer. Is the proof same if A were normal instead of hermitian? $\endgroup$ – milez Nov 21 '18 at 11:58
2
$\begingroup$

Here is a much more complicated proof:

The singular values can be defined as follows:

$\sigma_1(A) = \max_{ \|x\| = 1} \|Ax\|$. Choose $v_1 \in \operatorname{argmax}_{ \|x\| = 1} \|Ax\|$. ($v_1 $ is a singular vector corresponding to $\sigma_1(A)$.)

Suppose we have $\sigma_1(A),...,\sigma_k(A)$ and an orthogonal set of corresponding singular vectors $v_1,...,v_k$, then define $\sigma_{k+1}(A) = \max_{ \|x\| = 1, x \bot v_1,...,x \bot v_k} \|Ax\|$ and choose $v_{k+1} = \operatorname{argmax}_{ \|x\| = 1, x \bot v_1,...,x \bot v_k} \|Ax\|$.

Now let $A=Q \Lambda Q^*$, where $Q$ is orthogonal and $\Lambda$ is ordered by absolute value. Note that $\|Ax\| = \|\Lambda Q^* x\|$. Note that if $v_1,...,v_k$ are an orthonormal collection, then so are $Q^*v_1,...,Q^*v_k$.

Then we see that $\sigma_1(A) = |\lambda_1|$ and we can choose $v_1 = Q e_1$. Now suppose we have $\sigma_1(A) = |\lambda_1|,...,\sigma_k(A) = |\lambda_k|$ and corresponding singular vectors $Qe_1,...,Qe_k$, then $\sigma_{k+1}(A) = \max_{ \|x\| = 1, x \bot Q e_1,...,x \bot Q e_k} \|\Lambda Q^* x\|$. Since $\{x | \|x\| = 1, x \bot Q e_1,...,x \bot Q e_k \} = \{ x \in \operatorname{sp} \{ Q e_{k+1},...,Q e_n\} | \|x\| =1 \}$, we see that the value is $|\lambda_{k+1}|$ and that this is attained with $v_{k+1} = Q e_{k+1}$.

$\endgroup$
  • $\begingroup$ Thanks for sharing this proof. It sounds interesting but not easy to understand. Last night I was working on a problem that needs the definition $\sigma_{1}(A) = max_{||x||=1} ||Ax||$ , .. $ \sigma_{n}(A) = inf_{||x|=1}||Ax||$. It seems in the proof that you posted similar definitions are used. I searched the internet and I have found a blog's post[1] on this topic : I wonder if there is a book or source that explains these definitions more in details.[1]terrytao.wordpress.com/tag/least-singular-value $\endgroup$ – Crimson Aug 9 '16 at 13:51
  • 1
    $\begingroup$ @Zereshki: I am away from my library, but I think Golub & Van Loan's "Matrix Computations" shows equivalence with the above. $\endgroup$ – copper.hat Aug 9 '16 at 15:07
  • $\begingroup$ Thank you. You are right chapter 2 has mentioned it. $\endgroup$ – Crimson Aug 9 '16 at 15:16

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.