chapter5

Chapter 5 Hermitian Theory Hermitian matrices form one of the most useful classes of square matri- ces. They occur naturally in a variety of applications from the solution ofpartial di fferential equations to signal and image processing. Fortunately, they possess the most desirable of matrix properties and present the user with a relative ease of computation. There are several very powerful factsabout Hermitian matrices that have found universal application. First thespectrum of Hermitian matrices is real. Second, Hermitian matrices have acomplete set of orthogonal eigenvectors, which makes them diagonalizable.Third, these facts give a spectral repre sentation for Hermitian matrices and a corresponding method to approximate them by matrices of less rank. 5.1 Diagonalizability of Hermitian Matrices Let’s begin by recalling the basic de finition. Definition 5.1.1. LetA∈Mn(C). We say that AisHermitian ifA=A∗, where A∗=¯AT.A∗is called the adjoint of A. This, of course, is in con flict with the other de finition of adjoint, which is given in terms of minors. Recall the following facts and de finitions about subspaces of Cn: •IfU, V are subspaces of Cn,w ed e fine the direct sum ofUandVby U⊕V={u+v|u∈U, v∈V}. •IfU, V are subspaces of Cn,w es a y UandVare orthogonal if hu, vi=0 for every u∈Uandv∈V.I nt h i sc a s ew ew r i t e U⊥V. For example, a natural way to obtain orthogonal subspaces is from ortho- normal bases. Suppose that {u1,...,u n}is an orthonormal basis of Cn.Let 181 182 CHAPTER 5. HERMITIAN THEORY the integers {1,...,n }be divided into two (disjoint) subsets J1andJ2.Now define U1=S{ui|i∈J1} U2=S{ui|i∈J2} Then U1andU2are orthogonal, i.e. U1⊥U2,and U1⊕U2=Cn hAu, x i=hu, Ax i=λhu, xi=0 Our main result is that Hermitian matrices are diagonalizable. To prove it, we reveal other interesting and importa nt properties of Hermitian matrices. F o re x a m p l e ,c o n s i d e rt h ef o l l o w i n g . Theorem 5.1.1. LetA∈Mn(C)be Hermitian. Then the spectrum of A,σ(A),i sr e a l . Proof. Letλ∈σ(A) with corresponding eigenvector x∈Cn.T h e n hAx, x i=hx, Ax i=hx,λxi=¯λhx, xi k hλx, xi k λhx, xi. Since we know kxk2=hx, xi6= 0, it follows that λ=¯λ, which is to say that λis real. Theorem 5.1.2. LetA∈Mn(C)be Hermitian and suppose that λandµ are different eigenvalues with corresponding eigenvectors xandy.T h e n x⊥y(i.e. hx, yi=0). Proof. We know Ax=λxandAy=µy. Now compute hAx, y i=hx, A∗yi=hx, Ay i=µhx, yi k λhx, yi. Ifhx, yi6= 0, the equality above yields a contradiction and the result is proved. 5.1. DIAGONALIZABILITY OF HERMITIAN MATRICES 183 Remark 5.1.1. This result also follows from the previously proved result about the orthogonality of left and right eigenvectors pertaining to di fferent eigenvalues. Theorem 5.1.3. LetA∈Mn(C)be Hermitian, and let λbe an eigenvalue ofA. Then the algebraic and geometric multiplicities of λare equal. In symbols, ma(λ)=mg(λ). Proof. We prove this result by reconsideration of our main result on triangu- larization of Aby a similarity transformation. Let x∈Cnbe an eigenvector ofApertaining to λ.S o , Ax=λx.L e t u2,... ,u n⊂Cnbe a set of vectors orthogonal to x,s ot h a t {x, u 2,... ,u n}is a basis of Cn. Indeed, it is an orthogonal basis, and by normalizing the vectors it becomes an orthonor- mal basis. We claim that U2=S(u2,... ,u n), the span of {u2,... ,u n}is invariant under A. To see this, suppose u=nX j=2cjuj∈U2 and Au=v+ax where v∈U2anda6= 0. Then, on the one hand hAu, x i=hu, Ax i=λhu, xi=0 On the other hand hAu, x i=hv+ax, x i=ahx, xi=akxk26=0 This contraction establishes that the span of {u2,... ,u n}is invariant under A. LetU⊕V=Cnbe invariant subspaces with U⊥V. Suppose that UB and VBare orthonormal bases of the orthogonal subspaces UandV.Define the matrix P∈Mn(C) by taking for its columns first the basis vectors UB and and then the basis vectors VB.L e t u s w r i t e P=[UB,VB]( w i t ho n l y a small abuse of notation). Then, since Ais Hermitian, B=P−1AP =·Au0.......... 0Av¸ 184 CHAPTER 5. HERMITIAN THEORY The whole process can be carried out exactly ma(λ)t i m e s ,e a c ht i m e generating a new orthogonal eigenvector pertaining to λ.T h i s e s t a b l i s h e s thatmg(λ)=ma(λ). A formal induction could have been given. Remark 5.1.2. Note how we applied orthogonality and invariance to force the triangular matrix of the previous result to become diagonal. This is what permitted the successive extracti on of eigenvectors. Indeed, if for any eigenvector xthe subspace of Cnorthogonal to xis invariant, we could have carried out the same steps as above. We are now in a position to state our main result, whose proof is implicit in the three lemmas above. Theorem 5.1.4. LetA∈Mn(C)be Hermitian. Then Ais diagonalizable. The matrix Pfor which P−1AP is diagonal can be taken to be orthogonal. Finally, if {λ1,...,λn}and {u1,...,u n}denote eigenvalues and pertaining orthonormal eigenvectors for A,t h e n Aadmits the spectral representation A=Pn j=1λjujuT j. Corollary 5.1.1. LetA∈Mn(C)be Hermitian. (i)Ahasnlinearly independent and orthogonal eigenvectors. (ii)Ais unitarily equivalent to a diagonal matrix. (iii) If A, B∈Mnare unitarily equivalent, then Ais Hermitian if and only ifBis Hermitian. Note that in part (iii) above, the condition of unitary equivalence cannot be replaced by just similarity. (Why?) Theorem 5.1.5. IfA, B∈Mn(C)andA∼Bwith Sas the similarity transformation matrix, B=S−1AS.I f Ax=λxandy=S−1x,t h e n By=λy. If matrices are similar so also are their eigenstructures. It should establish the very closeness that similarity implies. Later as we consider decomposi- tion theorems, we will see even more remarkable consequences. Though we have as yet no method of determining the eigenvalues of a matrix beyond factoring the characteristic polynomial, it is instructive tosee how their existence impacts the fundamental problem of solving Ax=b. Suppose that Ais Hermitian with eigenvalues λ 1,...,λn,c o u n t e da c c o r d i n g to multiplicity and with o rthonormal eigenvectors {u1,...,u n}.C o n s i d e r 5.1. DIAGONALIZABILITY OF HERMITIAN MATRICES 185 the following solution method for the system Ax=b.Since the span of the eigenvectors is Cnthen b=nX i=1biui where as we know by the orthonormality of the vectors {u1,...,u n}that bi=hb, uii. We can also write x=Pn i=1xiui.Then, the system becomes Ax =AÃnX i=1xiui! =nX i=1xiλiui=nX i=1biui Therefore, the solution is xi=bi λi,i=1,...,n Expanding the data vector bin the basis of eigenvectors yields a rapid method to find the solution to the system. Nonetheless, this is not the preferred method for solving linear systems when the coe fficient matrix is Hermitian. Finding all the eigenvectors is usually costly, and other waysare available that are more e fficient. We will discuss a few of them in in the section and in later chapters. Approximating Hermitian matrices With the spectral representation available, we have a tool to approximate thematrix, keeping the “important” part and discarding the less important part.Suppose the eigenvalues are arranged in decending order |λ 1|≥···≥|λn|. Now approximate Aby Ak=kX j=1λjujuT j (1) This is an n×nmatrix. The di fference A−Ak=Pn j=k+1λjujuT j.We can approximate the norm of the di fference by (A−Ak)x= nX j=k+1λjujuT j x=nX j=k+1λjxjuj 186 CHAPTER 5. HERMITIAN THEORY where x=Pn j=1xjuj.Assume kxk= 1. By the Cauchy-Schwartz inequality k(A−Ak)xk2=°°°°°°nX j=k+1λjxjuj°°°°°°2 ≤nX j=k+1|λj|2 Therefore, k(A−Ak)k≤³Pn j=k+1|λj|2´1/2 . From this we can conclude that if the smaller eigenvalues are su fficiently small, the matrix can be ac- curately approximated by a matrix of lesser rank. Example 5.1.1. The matrix A= 0.5745−0.5005 0 .1005 0 .0000 −0.5005 1 .176−0.5756 0 .1005 0.1005−0.5756 1 .176−0.5005 0.0000 0 .1005−0.5005 0 .5745  has eigenvalues eigenvectors {2.004,0.9877,0.3219,0.1872 }with pertaining eigenvectors u1= 0.2740 −0.6519 0.6519 −0.2740 ,u2= 0.4918 −0.5080 −0.5080 0.4918 ,u3= 0.6519 0.2740 −0.2740 −0.6519 ,u 4= 0.5080 0.4918 0.4918 0.5080  respectively. Neglecting the eigenvec tors pertaining to the two smaller eigenvalues Ais approximated according as 1 the formula above by A2=2X j=1λjujuT j=λ1u1uT 1+λ2u2uT 2 =2 .004 0.274 −0.6519 0.6519 −0.274  0.274 −0.6519 0.6519 −0.274 T +0.9877 0.4918 −0.508 −0.508 0.4918  0.4918 −0.508 −0.508 0.4918 T A2= 0.3893−0.6047 0 .1112 0 .0884 −0.6047 1 .107−0.5968 0 .1112 0.1112−0.5968 1 .107−0.6047 0.0884 0 .1112−0.6047 0 .3893  5.2. FINDING EIGENVECTORS 187 The difference A−A2= 0.1852 0 .1042−0.0107−0.0884 0.1042 0 .069 0 .0212−0.0107 −0.0107 0 .0212 0 .069 0 .1042 −0.0884−0.0107 0 .1042 0 .1852  has 2-norm kA−A2k2=0.3218, while the 2-norm kAk2=2.004. The relative error of approximation iskA−A2k2 kAk2=0.3218 2.004=0.1606. To illustrate how this may be used, let us attempt to use A2to approx- imate the solution of Ax=b,w h e r e b=[ 2.606,−4.087,1.113,0.346 4]T. First of all the exact solution is x=[ 2.223,−2.688,−0.162 9,0.931 2]T. Since the matrix A2has rank two, it is not solvable for every vector b. We therefore project the vector binto the span of the range of A2,n a m e l y u1andu2.T h u s b2=hb, u1iu1+hb, u2iu2=[ 2.555,−4.118,1.109,0.358 4]T Now solve A2x2=b2,t oo b t a i n x2=[ 2.023,−2.828,−0.220 2,0.927 4]T. The 2-norm of the di fference is kx−x2k2=0.250 8. This error, though not extremely small, can be accounted for by the fact that the data vector bhas sizable u3andu4components. That is°°projS(u3,u4)b°°=0.250 8. 5.2 Finding eigenvectors Recall that a zero of a polynomial is called simple if its multiplicity is one. If the eigenvalues of A∈Mn(C) are distinct and the largest, λn, in modulus is simple, then there is an iterative method to find it. Assume (1) |λn|=ρ(A) (2) ma(λn)=1 . Moreover, without loss of generality we assume eigenvalues to be ordered |λ1|≤···≤|λn−1|<|λn|=ρn. Select x(0)∈C(n).D efine x(k+1)=1 kx(k)kAx(k). By scaling we can assume that λn=1 ,a n dt h a t y(1),... ,y(n)are linearly independent eigenvectors of A.S oAy(n)=y(n).W ec a nw r i t e x(0)=c1y(1)+···+cny(n). 188 CHAPTER 5. HERMITIAN THEORY Then, except for a scale factor (i.e. the factor kx(k)k−1) x(k)=c1λk 1y(1)+···+cnλk ny(n). Since |λj|<1,j=1,2,... ,n−1, we have that |λk j|→0i fj=1,2,... ,n−1. Therefore, the limit of x(k)approaches a multiple of y(n). This gives the following result. Theorem 5.2.1. LetA∈Mn(C)have ndistinct eigenvalues and assume the eigenvalue λnwith modulus ρ(A)is simple. If x(0)is not orthogonal to the eigenvector y(n)pertaining to λn, then the sequence of vectors de fined by x(k+1)=1 kx(k)kAx(k) converges to a multiple of y(n).T h i si sc a l l e dt h e Power Method . The rate of convergence is controlled by |λn−1|. The closer to 1 this number is the slower the iterates converge. Also, if we know only that λn (for which |λn|=ρ(A) is simple we can determine what it is by considering theRayleigh quotient. Take ρk=hAx(k),x(k)i hx(k),x(k)i. Then lim k→∞ρk=λn. Thus the multiple of y(n)is indeed λn. Tofind intermediate eigenvalues and eigenvectors we apply an adaptation of the power method called the orthogonalization method . However, in order to adapt the power method to determine λn−1,our underlying assumption is that is also simple and morover |λn−2|<|λn−1|. Assume y(n)andλna r ek n o w n . T h e nw er e s t a r tt h ei t e r a t i o n ,t a k i n g the starting value ˆx(0)=x(0)−hx(0),y(n)i ky(n)k2y(n). We know that the eigenvector y(n−1)pertaining to λn−1is orthogonal to y(n). Thus, in theory all of the iterates ˆx(k+1)=1 kˆx(k)kTˆx(k) 5.2. FINDING EIGENVECTORS 189 will remain orthogonal to y(n). Therefore, lim k→∞ˆx(k)=y(n−1). –in theory. In practice, however, we must accept that y(n)has not been determined exactly. This means ˆ x(0)has not been purged of all of y(n).B y our previous reasoning, since λnis the dominant eigenvalue, the presence of y(n)willcreep back into the iterates ˆ x(k). To reduce the contamination it is best to purify the iterates ˆ x(k)periodically by the reduction (?)ˆ x(k)−→ˆx(k)−hˆx(k),y(n)i ky(n)ky(n) before computing ˆ x(k+1). The previous argument can be applied to prove that (2) lim k→∞x(k)=y(n−1) (2) lim k→∞hAx(k),x(k)i kx(k)k2=λn−1. Additionally, even if we know y(n)exactly, round-o fferror would reinstate ay(n)component in our iterative computations. Thus the puri fication step above, ( ?), should be applied in allcircumstances. Finally, subsequent eigenvalues and eigenvectors may be determined by successive orthogonalizations. Again th e eigenvalue simplicity and strict inequality is needed for convergence. Speci fically, all eigenvectors can be determined if we assume that eigenvalues to be strictly ordered |λ1|<···< |λn−1|<|λn|=ρn. For example, we begin the iterations to determine y(n−j) with ˆx(0)=x(0)−j−1X i=0hx(0),y(n−i)i ky(n−i)k2y(n−i). Don’t forget the re-orthogonalizations periodically throughout the iterative process. W h a tc a nb ed o n et o find intermediate eigenvalues and eigenvectors in the case Ais not symmetric? The method above fails, but a variation of it works. What must be done is to generate the left and right eigenvectors, w(n) andy(n),f o r A. Use the same process. To compute y(n−1)andw(n−1)we 190 CHAPTER 5. HERMITIAN THEORY orthogonalize thusly: ˆx(0)=x(0)−hx(0),w(n)i kw(n)k2w(n) ˆz(0)=z(0)−hz(0),y(n)i ky(n)k2y(n) where z(0)is the original starting value used to determine the left eigenvector w(n).S i n c ew ek n o wt h a t lim k→∞x(k)=αy(n) it is easy to see that lim k→∞Ax(k)=αλny(n). Therefore, lim k→∞hAx(k),x(k)i hx(k),x(k)i=λn. Example 5.2.1. LetTbe the transformation of R2→R2that rotates a vector by θradians. Then it is clear that no matter what nonzero vector x(0)is selected the iterations x(k+1)=Tx(k)will never converge. (Assume kx(0)k= 1.) Now the matrix representation of Tis AT=·cosθ−sinθ sinθcosθ¸ rotates counterclockwise we have pAT(λ)=d e t·λ−cosθ sinθ −sinθλ−cosθ¸ =(λ−cosθ)2+s i n2θ. The spectrum of ATis therefore λ=c o sθ±isinθ. Notice that the eigenvalues are discrete, but there are twoeigenvalues with modulus ρ(AT) = 1. The above results therefore do not apply. 5.3. POSITIVE DEFINITE MATRICES 191 Example 5.2.2. Although the previous example is not based on a symmet- ric matrix, it certainly illustrates non convergence of the power iterations. The even simpler Householder matrix·10 0−1¸ furnishes us with a sym- metric matrix for which the iterations also do not converge. In this case, there are two eigenvalues with modulus equal to the spectral radius ( ±1). With arbitrary starting vector x(0)=[a, b]T,i ti so b v i o u st h a tt h ee v e n iterations are x(2i)=[a, b]Ta n dt h eo d di t e r a t i o n sa r e x(2i−1)=[a,−b]T. Assuming again that the eigenvalues are distinct and even stronger, as- suming that |λ1|<|λ2|<···<|λn| we can apply the process above to extract all the eigenvalues (Rayleigh quotient) and the eigenvectors, one-by-one, when AAAis symmetric . First of all, considering the matrix A−σIwe can shift the eigenvalues to either the left or the right. Depending on the location of λnas ufficiently large |σ|may be chosen so that |λ1−σ|=ρ(A−σI). The power method can be applied to determine λ1−σand hence λ1. 5.3 Positive de finite matrices Of the many important subclasses of Hermitian matrices, there is one class that stands out. Definition 5.3.1. We say that A∈Mn(C)i spositive de finiteifhAx, x i> 0 for every nonzero x∈Cn. Similarly, we say that A∈Mn(C)i spositive semide finiteifhAx, x i≥0 for every nonzero x∈Cn. It is easy to see that for positive de finite matrices all of the results are true Theorem 5.3.1. LetA, B∈Mn(C).T h e n 1. If Ais positive de finite, then σ(A)⊂R+ n 2. If Ais positive de finite, then Ais invertible. 3.B∗Bis positive semide finite. 4. If Bis invertible then B∗Bis positive de finite. 192 CHAPTER 5. HERMITIAN THEORY 5. If B∈Mn(C)is positive semide finite, then diag (B)is nonnegative, and diag (B)is strictly positive when Bis postive de finite. The proofs are all routine. Of course, every diagonal matrix with non- negative entries is positive semide finite. Square roots Given a real matrix A∈Mn. It is sometimes desired to determine a square root of A.B y t h i s w e m e a n a n y m a t r i x Bfor which B2=A.Moreover, if possible, it is desired that the square root be real. Our experience withnumbers indicates that in order that a number have a positive square root,it must be positive. The analogue for matrices is the condition of beingpositive de finite. Theorem 5.3.2. LetA∈M nbe positive [semi-]de finite. Then Ahas a real square root. Moreover, the square r oot can taken to be positive //[semi- ]definite. Proof. We can write the diagonal matrix of the eigenvalues of Ain the equa- tionA=P−1DP. E x t r a c tt h ep o s i t i v es q u a r er o o to f DasD1 2=diag(λ1/2 1,...,λ1/2 n). Obviously D1 2D1 2=D.N o w d e fineA1 2byA1 2=P−1D1 2P.T h i s m a t r i x i s real. It is simple to check that A1 2A1 2=A,and that this particular square root is positive de finite. Clearly any real diagonalizable matrix with nonnegative eigenvectors has a real square root as well. However, bey ond that conditions for determin- ing existence let alone determination of square roots take us into a very specialized subject. 5.4 Singular Value Decomposition Definition 5.4.1. For any A∈Mmn,t h e n×nHermitian matrix A∗Ais positive semi-de finite. Denoting its eigenvalues by λjwe called the valuesp λjthesingular values ofA. Because r(A∗A)≤min ( r(A∗),r(A))≤min(m, n)t h e r ea r ea tm o s t min ( m, n) nonzero singular values. Lemma 5.4.1. LetA∈Mmn.There is an orthonormal basis {u1,...,u n}of Cnsuch that {Au1,...,A u n}is orthogonal. 5.4. SINGULAR VALUE DECOMPOSITION 193 Proof. Proof. Consider the n×nHermitian matrix A∗A, and denote an orthonormal basis of its eigenvectors by {u1,...,u n}.T h e ni ti se a s yt os e e that {Au1,...,A u n}is an orthogonal set. For hAuj,A u ki=hA∗Auj,uki= λjhuj,uki=0. Lemma 5.4.2. Lemma 2 Let A∈Mmnand an orthonormal basis {u1,...,u n}of Cn.D efine vj=( 1 kAujkAujifkAujk6=0 0 ifkAujk=0 LetS=diag(kAu1k,..., kAunk),t h e n×nmatrix Uhaving rows given by the basis {u1,...,u n}and ˆVthem×nmatrix given by the columns {v1,...,v n}.T h e n A=ˆVS U . Proof. Proof. Consider ˆVS Uu j= v1v2 vn ↓↓ ↓  kAu1k 0 ··· 0 0 kAu2k00 ......... 00 ··· k Aunk  u1−→ u2−→ un−→ uj = v1v2 vn ↓↓ ↓  kAu 1k 0 ··· 0 0 kAu2k00 ......... 00 ··· k Aunk e j = v1v2 vn ↓↓ ↓ kAujkej=kAujkvj=Auj Thus both ˆVS U andAhave the same action on a basis. Therefore they are equal. It is easy to see that kAujk=p λj, that is the singular values. While A=ˆVS U could be called the singular value decomposition (SVD), what is usually o ffered at the SVD is small modi fication of it. Rede fine the matrix Uso that the firstrcolumns pertain to the nonzero singularvalues. De fine Dto be the m×nmatrix consisting of the non zero singular values in the 194 CHAPTER 5. HERMITIAN THEORY djjpositions, and filled in with zeros else where. De fine the matrix Vto be thefirstrof the columns of ˆVand if r<m construct an additional m−r orthonormal columns so that Vis an orthonormal basis of Cn.The resulting product VD U ,c a l l e dt h e singular value decomposition ofA,i se q u a lt o A,and moreover it follows that Vism×m, D ism×n,andUisn×n. This gives the following theorem Theorem 5.4.1. LetA∈Mmn.Then there is an m×morthogonal matrix V,ann×northogonal matrix U,a n da n m×nmatrix Dwith only diagonal entries such that A=VD U . The diagonal entries of Dare the singular values of Aand the rows of Uare the eigenvectors of A∗A. Example 5.4.1. The singular value decomposition can be used for image compression. Here is the idea. Consider all the eigenvalues of A∗Aand order them greatest to least. Zero the matrix Sfor all eigenvalues less than some threshold. Then in the reconstruc tion and transmission of the matrix, it is not necessary to include the vectors pertaining to these eigenvalues. Inthe example below, we have considered a 164 ×193 pixel image of C. F. Gauss (1777-1855) on the postage stamp issued by Germany on Feb. 23, 1955, to commemorate the centenary of death. Therefore its spectrum has164 eigenvalues. The eigenvalues range from 26,603.0 to 1.895. A plotof the eigenvalues shown below. Now compress the image, retaining only afraction of the eigenvalues by e ffectively zeroing the smaller eigenvalues. 5.4. SINGULAR VALUE DECOMPOSITION 195 Note that the original image of the stamp has been enlarged and resampled for more accurate comparisons. This image (stored at 221 dpi) is displayed at effective 80 dpi with the enlargement. Below we show two plots where we have retained respectively 30% and 10% of the eigenvalues. There is anapparent drastic decline in the image quality at roughly 10:1 compression. In this image all eigenvalues smaller than λ= 860 have been zeroed. Using 48 of 164 eigenvalues Using 16 of 164 eigenvalues 196 CHAPTER 5. HERMITIAN THEORY 5.5 Exercises 1. Prove Theorem 5.3.1 (i). 2. Prove Theorem 5.3.1 (ii). 3. Suppose that A, B∈Mn(C) are Hermitian. We will say A<0i fA is non-negative de finite. Also, we say A<BifA−B<0. Is “ <” an equivalence relation? If A<BandB<Cprove or disprove that A<C. 4. Describe all Hermitian matrices of rank one. 5. Suppose that A, B∈Mn(C) are Hermitian and positive de finite. Find necessary and su fficient conditions for ABto be Hermitian and also positive de finite. 6. For any matrix A∈Mn(C) with eigenvalues λi,i=1,...,n .P r o v e thatPn i=1|λi|2=Pn i,j=1|aij|2.