chapter4

Chapter 4 Unitary Matrices 4.1 Basics This chapter considers a very important class of matrices that are quite use- ful in proving a number of structure theorems about all matrices. Calledunitary matrices, they comprise a class of matrices that have the remarkable properties that as transformations they preserve length, and preserve the an- gle between vectors. This is of course true for the identity transformation.Therefore it is helpful to regard unitary matrices as “generalized identities,”though we will see that they form quite a large class. An important exam-ple of these matrices, the rotations, have already been considered. In this chapter, the underlying field is usually C, the underlying vector space is C n, and almost without exception the underlying norm is k·k 2.W e b e g i n b y recalling a few important facts. Recall that a set of vectors x1,...,x k∈Cnis called orthogonal if x∗ jxm=hxm,xji=0f o r1 ≤j6=m≤k.T h es e ti s orthonormal if x∗ jxm=δmj=½1j=m 0j6=m. An orthogonal set of vectors can be made orthonormal by scaling: xj−→1 (x∗ jxj)1/2xj. Theorem 4.1.1. Every set of orthonormal vecto rs is linearly independent. Proof. The proof is routine, using a common technique. Suppose S= {xj}k j=1is orthonormal and linearly dependent. Then, without loss of gen- 157 158 CHAPTER 4. UNITARY MATRICES erality (by relabeling if needed), we can assume uk=k−1X j=1cjuj. Compute u∗ kukas 1=u∗ kuk=u∗ k k−1X j=1cjuj  =k−1X j=1cju∗ kuj=0. This contradiction proves the result. Corollary 4.1.1. IfS={u1...u k}⊂Cnis orthonormal then k≤n. Corollary 4.1.2. Every k-dimensional subspace of Cnhas an orthonormal basis. Proof. Apply the Gram—Schmidt process to any basis to orthonormalize it. Definition 4.1.1. Am a t r i x U∈Mnis said to be unitary ifU∗U=I.[ I f U∈Mn(R)a n d UTU=I,t h e n Uis called real orthogonal .] Note: A linear transformation T:Cn→Cnis called an isometry if kTxk=kxkfor all x∈Cn. Proposition 4.1.1. Suppose that U∈Mnis unitary. (i) Then the columns ofUform an orthonormal basis of Cn,o rRn,i fUis real. (ii) The spectrum σ(u)⊂{z||z|=1}. (iii) |detU|=1. Proof. The proof of (i) is a consequence of the de finition. To prove (ii), first denote the columns of Ubyui,i=1,...,n .I fλis an eigenvalue of Uwith pertaining eigenvector x,t h e n kUxk=kPxiuik=(P|xi|2)1/2=kxk= |λ|kxk.H e n c e |λ|= 1. Finally, (iii) follows directly because det U=Qλi. Thus |detU|=Q|λi|=1 . This important result is just one of many equivalent results about unitary matrices. In the result below, a number of equivalences are established. Theorem 4.1.2. LetU∈Mn. The following are equivalent. 4.1. BASICS 159 (a)Uis unitary. (b)Uis nonsingular and U∗=U−1. (c)UU∗=I. (d)U∗is unitary. (e) The columns of Uform an orthonormal set. (f) The rows of Uform an orthonormal set. (g)Uis an isometry. (h)Ucarries every set of orthonormal vectors to a set of orthonormal vectors. Proof. (a)⇒(b) follows from the de finition of unitary and the fact that the inverse is unique. (b)⇒(c) follows from the fact that a left inverse is also a right inverse. (a)⇒(d)UU∗=(U∗)∗U∗=I. (d)⇒(e) (e) ≡(b)⇒ u∗ jukδjk,w h e r e u1...u nare the columns of U. Similarly (b) ⇒(e). (d)≡(f) same reasoning. (e)⇒(g) We know the columns of Uare orthonormal. Denoting the columns byu1...u n,w eh a v e Ux=nX 1xiui where x=(x1,... ,x n)T. It is an easy matter to see that kUxk2=nX 1|xi|2=kxk2. (g)⇒(e). Consider x=ej.T h e n Ux=uj.H e n c e 1 = kejk=kUejk= kujk.T h e c o l u m n s o f Uhave norm one. Now let x=αei+βejbe chosen 160 CHAPTER 4. UNITARY MATRICES such that kxk=kαei+βejk=q |α|2+|β|2=1 . T h e n 1= kUxk2 =kU(αei+βej)k2 =hU(αei+βej),U(αei+βej)i =|α|2hUei,Ue ii+|β|2hUej,Ue ji+α¯βhUei,Ue ji+¯αβhUej,Ue ii =|α|2hui,uii+|β|2huj,uji+α¯βhui,uji+¯αβhuj,uii =|α|2+|β|2+2<¡ α¯βhui,uji¢ =1 + 2 <¡ α¯βhui,uji¢ Thus <¡ α¯βhui,uji¢ =0.Now suppose hui,uji=s+it. Selecting α= β=1√ 2we obtain that <hui,uji= 0, and selecting α=iβ=1√ 2we obtain that =hui,uji=0 . T h u s hui,uji= 0. Since the coordinates iandjare arbitrary, it follows that the columns of Uare orthogonal. (g)⇒(h) Suppose {v1,...,v n}is orthogonal. For any two of them kU(vj+ vk)k2=kvj+vkk2. Hence hUvj,U v ki=0 . (h)⇒(e) The orthormal set of the standard unit vectors ej,j=1,...,n is carried to the columns of U.T h a t i s Uej=uj,t h e jthcolumn of U. Therefore the columns of Uare orthonormal. Corollary 4.1.3. IfU∈Mn(C)is unitary, then the transformation de fined byUpreserves angles. Proof. We have for any vectors x, y∈Cnthat the angle θis completely determined from the inner product via cos θ=hx,yi kxkkyk.S i n c e Uis unitary (and thus an isometry) it follows that hUx,Uy i=hU∗Ux,y i=hx, yi This proves the result. Example 4.1.1. LetT(θ)=£cosθ−sinθ sinθcosθ¤ whereθis any real. Then T(θ)i s realorthogonal. Proposition 4.1.1. IfU∈M2(R)is real orthogonal, then Uhas the form T(θ)for some θor the form U=·10 0−1¸ T(θ)=·cosθsinθ sinθ−cosθ¸ Finally, we can easily establish the di agonalizability of unitary matrices. 4.1. BASICS 161 Theorem 4.1.3. IfU∈Mnis unitary, then it is diagonalizable. Proof. To prove this we need to revisit the proof of Theorem 3.5.2. As before, select the first vector to be a normalized eigenvector u1pertaining toλ1.Now choose the remaining vectors to be orthonormal to u1.T h i s makes the matrix P1with all these vectors as columns a unitary matrix. Therefore B1=P−1UPis also unitary. However it has the form B1= λα 1...αn−1 0 ... A2 0 where A 2is (n−1)×(n−1) Since it is unitary, it must have orthogonal columns by Theorem 4.1.2. It follows then that α1=α2=···=αn=0 a n d B1= λ0... 0 0 ... A2 0  At this point one may apply and inductive hypothesis to conclude that A2 is similar to a diagonal matrix. Thus by the manner in which the full similarity was constructed, we see that Amust also be similar to a diagonal matrix. Corollary 4.1.1. LetU∈Mnbe unitary. Then (i) Then Uhas a set of northogonal eigenvectors. (ii) Let {λ1,...,λn}and{v1,...,v n}denote respectively the eigenvalues and their pertaining orthonormal eigenvectors of U.Then Uhas the representation as the sum of rank one matrices given by U=nX j=1λjvjvT j This representation is often called the spectral respresentation or spectral decomposition of U. 162 CHAPTER 4. UNITARY MATRICES 4.1.1 Groups of matrices Invertible and unitary matrices have a fundamental structure that makes possible a great many general statements about their nature and the waythey act upon vectors other vectors matrices. A group is a set with a math-ematical operation, product, that obeys some minimal set of properties so as to resemble the nonzero numbers under multiplication. Definition 4.1.2. Agroup Gi sas e tw i t hab i n a r yo p e r a t i o n G×G→G which assigns to every pair a, bof elements of Ga unique element abinG. The operation, called the product ,s a t i s fies four properties: 1. Closure. If a, b∈G,t h e n ab∈G. 2. Associativity. If a, b, c∈G,t h e n a(bc)=(ab)c. 3. Identity. There exists an element e∈Gsuch that ae=ea=afor every a∈G.eis called the identity ofG. 4. Inverse. For each a∈G, there exists an element ˆ a∈Gsuch that aˆa=ˆaa=e.ˆais called the inverse of aand is often denoted by a −1. A subset of Gthat is itself a group under the same product is called a subgroup ofG. It may be interesting to note that removal of any of the properties 2-4 leads to other categories of sets that have interest, and in fact applications, in their own right. Moreover, many groups have additional properties such ascommutativity, i.e. ab=bafor all a, b∈G.B e l o w a r e a f e w e x a m p l e s o f matrix groups. Note matrix addition is not involved in these de finitions. Example 4.1.2. As usual M nis the vector space of n×nmatrices. The product in these examples is the usual matrix product. •The group GL(n, F) is the group of invertible n×nmatrices. This is the so-called general linear group. The subset of Mnof invertible lower (resp. upper) triangular matrices is a subgroup of GL(n, F). •Theunitary group Unof unitary matrices in Mn(C). •Theorthogonal group Onorthogonal matrices in Mn(R). The sub- group of Ondenoted by SOnconsists of orthogonal matrices with determinant 1. 4.1. BASICS 163 Because element inverses are required, it is obvious that the only subsets of invertible matrices in Mnwill be groups. Clearly, GL(n, F) is a group because the properties follow from those matrix of multiplication. We havealready established that invertible lo wer triangular matrices have lower tri- angular inverses. Therefore, they form a subgroup of GL(n, F). We consider the unitary and orthogonal groups below. Proposition 4.1.2. For any integer n=1,2,... the set of unitary matrices U n(resp. real orthogonal) forms a group. Similarly Onis a group, with subgroup SOn. Proof. The result follows if we can show that unitary matrices are closed under multiplication. Let UandVbe unitary. Then (UV)∗(UV)=V∗U∗UV =V∗V=I For orthogonal matrices the proof is essentially identical. That SOnis a group follows from the determinant equality det( AB)=d e t AdetB.T h e r e - fore it is a subgroup of On. 4.1.2 Permutation matrices Another example of matrix groups comes from the idea of permutations of integers. Definition 4.1.3. The matrix P∈Mn(C)i sc a l l e da permutation matrix if each row and each column has exactly one 1, the rest of the entries being zero. Example 4.1.3. Let P= 100 001010  Q= 0001 01001000 0010  PandQare permutation matrices. Another way to view a permutation matrix is with the game of chess. On an n×nchess board place nrooks in positions where none of them attack one another. Viewing the board as an n×nmatrix with ones where the rooks are and zeros elsewhere, this matrix will be a permutation matrix. 164 CHAPTER 4. UNITARY MATRICES Of course there are n! such placements, exactly the number of permutations of the integers {1,2,...,n }. Permutation matrices are closely linked with permutations as discussed in Chapter 2.5. Let σbe a permutation of the integers {1,2,...,n }.Define the matrix Aby aij=½1i f j=σ(i) 0i fo t h e r w i s e Then Ais a permutation matrix. We could also use the Dirac notation to express the same matrix, that is to say aij=δiσ(j).The product of permutation matrices is again a permutation matrix. This is apparent bystraight multiplication. Let PandQbe two n×npermutation matrices with pertaining permutations σ PandσQof the integers {1,2,...,n }.Then theithrow of PiseσP(i)and the ithrow of QiseσQ(i). (Recall the eiare the usual standard vectors.) Now the ithrow of the product PQcan be computed by nX j=1pijeσQ(j)=nX j=1δiσ(j)eσQ(j)=eσQ(σP(i)) Thus the multiplication ithrow of PQis a standard vector. Since the σP(i) ranges over the integers {1,2,...,n },i ti st r u ea l s ot h a t σQ(σP(i)) does likewise. Therefore the “product” σQ(σP(i)) is also a permutation. We conclude that the standard vectors constitute the rows of PQ.T h u s p e r m u - tation matrices are orthogonal under multiplication. Moreover the inverse ofevery permutation is permutation matrix, with the inverse describe throughthe inverse of the pertaining permutation of {1,2,...,n }. Therefore, we have the following result. Proposition 4.1.3. Permutation matrices are orthogonal. Permutation matrices form a subgroup of O n. 4.1.3 Unitary equivalence Definition 4.1.4. Am a t r i x B∈Mnis said to be unitarily equivalent toA if there is a unitary matrix U∈Mnsuch that B=U∗AU. ( I nt h er e a lc a s ew es a y Bis orthogonally equivalent to A.) 4.1. BASICS 165 Theorem 4.1.4. IfBandAare unitarily equivalent. Then nX i,j=1|bij|2=nX i,j=1|aij|2. Proof. We havenP i,j=1|aij|2=t rA∗A,a n d Σ|bij|2=t rB∗B=t r( U∗AU)∗U∗AU=t rU∗A∗AU =t rA∗A, since the trace is invariant under similarity transformations. Alternatively, we have BU∗=U∗A.S i n c e U(and U∗) are isometries we have each column of U∗Ahas the same norm as the norm of the same column of A. The same holds for the rows of BU∗, whence the result. Example 4.1.4. B=£31 −20¤ andA=[11 02] are similar but not unitarily equivalent. AandBare similar because (1) they have the same spectrum, σ(A)=σ(B)={1,2}and (2) they have two linearly independent eigenvec- tors. They are not unitarily equivalent because the conditions of the above theorem are not met. Remark 4.1.1. Unitary equivalence is a finer classi fication than similarity. Indeed, consider the two sets S(A)={B|Bis similar to A}andU(A)= {B|Bis unitarily equivalent to A},t h e n U(A)⊂S(A). (Can you show that U(A)$S(A) for some large class of A∈Mn?) 4.1.4 Householder transformations An important class of unitary transformations are elementary re flections. These can be realized as transformations that re flect one vector to its neg- a t i v ea n dl e a v ei n v a r i a n tt h eo r t h o c o m p l e m e n to fv e c t o r s . Definition 4.1.5. Simple Householder transformation.) Suppose w∈Cn, kwk=1 . D e fine the Householder transformation Hwby Hw=I−2ww∗ 166 CHAPTER 4. UNITARY MATRICES Computing HwH∗ w=(I−2ww∗)(I−2ww∗)∗ =I−2ww∗−2ww∗+4ww∗ww∗ =I−4ww∗+4hw,wiww∗=I it follows that Hwis unitary. Example 4.1.5. Consider the vector w=·cosθ sinθ¸ and the Householder transformation Hw=I−2wwT=·1−2c o s2θ−2c o sθsinθ −2c o sθsinθ1−2s i n2θ¸ =·−cos 2θ−sin 2θ −sin 2θcos 2θ¸ The transformation properties for the standard vectors are Hwe1=·−cos 2θ −sin 2θ¸ and Hwe2=·cos 2θ −sin 2θ¸ This is shown below. It is evident that this unitary transformation is not a rotation. Though, it can be imagined as a “rotation with a one dimensionalreflection.” ww wH e H eee2 1 θ2θ2θ Householder transformation Example 4.1.6. Letθbe real. For any n≥2a n d1≤i, j≤nwith i6=j 4.1. BASICS 167 define Un(θ,i ,j)i j 10 ......0 ......... 01...... ........... c o s θ............ −sinθ........... ...1 ... 1... ........... s i n θ............ c o s θ.................1... ......0...0 0.........1  ij Then U n(θ;i, j) is a rotation and is unitary. Proposition 4.1.4 (Limit theorems). (i) Show that the unitary matri- ces are closed with respect to any norm. That is, if the sequence {Un}⊂ Mn(C)are all unitary and the limn→∞Un=U in the k·k2norm, then U is also unitary. (ii) The unitary matrices are closed under pointwise convergence. That is, if the sequence {Un}⊂Mn(C)are all unitary and limn→∞Un=Ufor each ( ij)entry, then Uis also unitary. Householder transformations can als ob eu s e dt ot r i a n g u l a r i z eam a t r i x . The procedure successively removes the lower triangular portion of a matrixcolumn by column in a way similar to Gaussian elimination. The elemen- tary row operations are replaced by elementary re flectors. The result is a triangular matrix T=H vn···Hv2Hv1A.Since these re flectors are unitary, the factorization yields an e ffective method for solving linear systems. The actual process is rather straightforward. Construct the vector vsuch that ¡ I−2vvT¢ A=¡ I−2vvT¢ a 11a12···a1n a21a22···a2n ............ an1an2···ann = ˆa 11ˆa12··· ˆa1n 0ˆa22··· ˆa2n ............ 0ˆan2··· ˆann  168 CHAPTER 4. UNITARY MATRICES This is accomplished as follows. This means we wish to find a vector v such that ¡ I−2vvT¢ [a11,a21,···,an1]T=[ ˆa11,0,···,0]T For notational convenience and to emphasize the construction is vector based, relabel the column vector [ a11,a21,···,an1]Tas [x1,x2,...,x n]T vj=xj 2hv,xi forj=2,3,...,n .D e fine v1=x1+α 2hv,xi Then hv,xi=hx, xi 2hv,xi+αx1 2hv,xi=kxk2 2hv,xi+αx1 2hv,xi 4hv,xi2=2 kxk2+2αx1 where k·kdenotes the Euclidean norm. Also, for Hvto be unitary we need 1= hv,vi=1 4hv,xi2³ kxk2+2αx1+α2´ 4hv,xi2=kxk2+2αx1+α2 Equating the two expressions for 4 hv,xi2gives 2kxk2+2αx1=kxk2+2αx1+α2 α2=kxk2 α=±kxk We now have that 4hv,xi2=2 kxk2±2kxkx1 hv,xi=µ1 2³ kxk2±kxkx1´¶1 2 This makes v1=x1±kxk (1 2(kxk2±kxkx1))1 2.With the construction of Hvto “elim- inate” the first column of A, we relabel the vector vasv1(with the small 4.1. BASICS 169 possibility of notational confusion) and move to describe Hv2using a trans- formation of the same kind with a vector of the type v=( 0,x2,x3,...,x n). Such a selection will not a ffect the structure of the first column. Continue this until the matrix is triangularized. The upshot is that every matrix canbe factored as A=UT, where Uis unitary and Tis upper triangular. The main result for this section is the factorization theorem. As it turns out, every Unitary matrix can be written as a product of elementary re flectors. The proof requires a slightly more general notion of re flector. Definition 4.1.6. The general form of the Householder matrix, also called anelementary re flector , has the form H v=I−τvv∗ where the vector v∈Cn. In order for Hvto be unitary, it must be true that HvH∗ v=(I−τvv∗)(I−τvv∗)∗ =(I−τvv∗)(I−¯τvv∗) =I−τvv∗−¯τvv∗+|τ|2(v∗v)vv∗ =I−2Re (τ)vv∗+|τ|2|v|2vv∗ =I Therefore, for v6=0w em u s th a v e −2Re (τ)vv∗+|τ|2|v|2vv∗=³ −2Re (τ)+|τ|2|v|2´ vv∗ =0 or −2Re (τ)+|τ|2|v|2=0 Now suppose that Q∈Mn(R) is orthogonal and that the spectrum σ(Q)⊂ {−1,1}.Suppose Qhas a complete set of normalized orthogonal eigen- vectors1, it can be expressed as Q=nP i=1λivivT iwhere the set v1,...,v nare the eigenvectors and λi⊂σ(Q). Now assume the eigenvectors have been arranged so that this simpli fies to Q=−kX i=1vivT i+nX i=k+1vivT i 1This is in fact a theorem that will be established in Chapter 4.2. It follows as a consequence of Schur’s theorem 170 CHAPTER 4. UNITARY MATRICES Here we have just arrange the eigenvectors with eigenvalue −1t oc o m e first. Define Hj=I−2vjvT j,j =1,...,k It follows that Q=kY j=1Hj=kY j=1¡ I−2vjvT j¢ for it is easy to check that Uvm=kY j=1Hj=½−vmifm≤k vm ifm>k Since we have agreement with Qon a basis, the equality follows. In words we may say that an orthogonal matrix Uwith spectrum σ(Q)⊂{−1,1}with can be written as a product of re flectors. With this simple case out of t h ew a y ,w ec o n s i d e rm o r eg e n e r a lc a s ew ew r i t e Q=nP i=1λivivT i.where the setv1,...,v nare the eigenvectors and λi⊂σ(Q). We wish to represent Q similar to the above formula as a product of elementary re flectors. Q=kY j=1Hj=kY j=1¡ I−τjwjw∗ j¢ where wi=αivifor some scalars αi. On the one hand it must be true that−2Re (τi)+|τi|2|wi|2=0f o re a c h i=1,...n , and on the other hand it must follow that (I−τiwiw∗ i)vm=½λiviifm=i vmifm6=i The second of these relations is automatically satis fied by the orthogonality of the eigenvectors. The second relation can needs to be solved. This simpli fies to ( I−τiwiw∗ i)vi=³ 1−τi|αi|2´ vi=λivi.T h e r e f o r e , i t i s necessary to solve the system −2Re (τi)+|τi|2|vi|2=0 1−τi|αi|2=λi Having done so there results the factorization. 4.2. SCHUR’S THEOREM 171 Theorem 4.1.5. LetQ∈Mnbe real orthogonal or unitary. Then Qcan be factored as the product of elementary re flectors Q=nQ j=1³ I−τjwjw∗ j´ , where the wjare the eigenvectors of Q. Note that the product written here is up to nwhereas the earlier product was just up to k. The difference here is slight, for by taking the scalar ( α) equal zero when necessary, it is possible to equate the second form to thefirst form when the spectrum is contained in the set {−1,1}. 4.2 Schur’s theorem It has already been established in Theorem 3.5.2 that every matrix is similar to a triangular matrix. A far stronger result is possible. Called Schur’stheorem, this result proves that the similarity is actually unitary similarity. Theorem 4.2.1 (Schur’s Theorem). Every matrix A∈M n(C)is uni- tarily equivalent to a triangular matrix. Proof. We proceed by induction on the size of the matrix n. First suppose theAis 2×2.Then for a given eigenvalue λand normalized eigenvector vform the matrix Pwith its first column vand second column any vector orthogonal to vwith norm one. Then Pis an unitary matrix and P∗AP=·λ∗ 0∗¸ . This is the desired triangular form. Now assume the Schur factorization is possible for matrices up to size ( n−1)×(n−1). For the given n×nmatrix Aselect any eigenvalue λ. With its pertaining normalized eigenvector vconstruct the matrix Pwith vin the first column and an orthonormal complementary basis in the remaining n−1 columns. Then P∗AP= λˆa 12··· ˆa1n 0ˆa22··· ˆa2n ............ 0ˆan2··· ˆann = λˆa 12··· ˆa1n 0 ... A2 0  The eigenvalues of A 2together with λconstitute the eigenvalues of A.B y the inductive hypothesis there is an ( n−1)×(n−1) unitary matrix ˆQsuch that ˆQ∗A2ˆQ=T2,where T2is triangular. Now embed ˆQin an n×nmatrix 172 CHAPTER 4. UNITARY MATRICES Qas shown below Q= λ0··· 0 0 ... ˆQ 0  It follows that Q ∗P∗APQ = λ0··· 0 0 ... T 2 0 =T is triangular, as indicated. Therefore the factorization is complete upon defining the similarity transformation U=PQ. Of course, the eigenvalues ofA 2together with λconstitute the eigenvalues of A, and therefore by similarity the diagonal of Tcontains only eigenvalues of A. The triangular matrix above is not unique as is easy to see by mixing or permuting the eigenvalues. An import ant consequence of Schur’s theorem pertains to unitary matrices. Suppose that Bis unitary and we apply the Schur factorization to write B=U∗TU.T h e n T=UBU∗. It follows that the upper triangular matrix is itself unitary, which is to say T∗T=I.It is a simple fact to prove this implies that Tis in fact a diagonal matrix. Thus, the following result is proved. Corollary 4.2.1. Every unitary matrix is diagon alizable. Moreover, every unitary matrix has northogonal eigenvectors. Proposition 4.2.1. IfB,A∈M2are similar and tr (B∗B)=tr(A∗A),t h e n BandAare unitarily equivalent. This result higher dimensions. Theorem 4.2.2. Suppose that A∈Mn(C)has distinct eigenvalues λ1...λk with multiplicities n1,n2,... ,n krespectively. Then Ais similar to a matrix of the form  T 1 0 T2 0... Tk  4.2. SCHUR’S THEOREM 173 where Ti∈Mniis upper triangular with diagonal entries λi. Proof. LetE1be eigenspace of λ1. Assume dim E1=m1.L e t u1...u m1be an orthogonal basis of E1, and suppose v1...v n−m1is an orthonormal basis ofCn−E1.T h e n w i t h P=[u1...u m1,v1...v n−m1]w eh a v e P−1APhas the block structure ·T10 0A2¸ . Continue this way, as we have done before. However, if dim Ei<m iwe must proceed a di fferent way. First apply Schur’s Theorem to triangularize. Arrange the firstm1eigenvalues to the firstm1diagonal entries of T,t h e similar triangular matrix. Let Er,sb et h em a t r i xw i t ha1i nt h e r, sposition and 0’s elsewhere. We assume throughout that r6=s. Then, it is easy to see that I+αEr,sis invertible and that ( I+αErs)−1=I−αErs.N o w i f we de fine (I+αErs)−1T(I+αErs) we see that trs→trs+α(trr−tss). We know trr−tss6=0i f randspertain to values with di fferent eigenvalues. Now this value is changed, but so also are the values above and to the right of trs.This is illustrated below. columns → s row r ↑ ∗↑ ∗→ →  To see how to use these similarity transformation to zero out the upper blocks, consider the special case with just two blocks A= T 1 T12 0 T2  We will give a procedure to use elementary matrices αE ijto zero-out each of the entries in T12.The matrix T12hasm1·m2entries and we will need 174 CHAPTER 4. UNITARY MATRICES to use exactly that many of the matrices αEij.In the diagram below we illustrate the order of removal (zeroing-out) of upper entries  T 1m12m1···m1·m2 ......... 2... 1m1+1 ··· ··· 0 T2  W h e np e r f o r m e di nt h i sw a yw ed e v e l o p m 1·m2constants αij.We proceed in the upper right block ( T12) in the left-most column and bottom entry, that is position ( m1,m1+1 ).For the ( m1,m1+ 1) position we use the elementary matrixαEm1,m1+1to zero out this position. This is possible because the diagonal entries of T1andT2are different. Now use the elementary matrix αEm1−1,m1+1to zero-out the position ( m1−1,m1+ 1). Proceed up this column to the first row each time using a new α.W e a r e finished when all the entries in column m1+1 f r o m r o w m1to row 1 are zero. Now focus on the next column to the right, column m1+ 2. Proceed in the same way from the ( m1,m1+ 2) position to the (1 ,m1+ 1) position, using elementary matrices αEk,m 1+2zeroing out the entries ( k,m 1+ 2) positions, k=m1,..., 1. Ultimately, we can zero out every entry in the upper right block with this marching left-to-right, bottom-to-top procedure. In the general scheme with k×kblocks, next use the matrices T2and T3to zero-out the block matrix T23.(See below.) T= T 10T13 T2T23 T3... ... 0... Tk−1Tk−1,k Tk  After that it is possible using blocks T 1andT3to zero-out the block T13. This is the general scheme for the entire triangular structure, moving downthe super-diagonal ( j.j+ 1) blocks and then up the (block) columns. In this way we can zero-out any value not in the square diagonal blocks pertaining to the eigenvalues λ 1...λk. 4.2. SCHUR’S THEOREM 175 Remark 4.2.1. IfA∈Mn(R)a n dσ(A)⊂R, then all operations can be carried out with real numbers. Lemma 4.2.1. LetJ⊂Mnbe a commuting family. Then there is a vector x∈Cnfor which xis an eigenvector for every A∈J. Proof. LetW⊂Cnbe a subspace of minimal dimension that is invariant under J.S i n c e Cnis invariant, we know Wexists. Since Cnis invariant, we know Wexists. Suppose there is an A∈Jfor which there is a vector inWwhich is not an eigenvector of A.D e fineW0={y∈W|Ay= λyfor some λ}.T h a t i s , W0is a set of eigenvectors of A.S i n c e Wis invariant under A, it follows that W06=φ. Also, by assumption. W0$W. For any x∈W0 ABx =(AB)x=B(Ax)=λBx and so Bx∈W0. It follows that W0isJinvariant, and W0has lower positive dimension than W. As a consequence we have the following result. Theorem 4.2.3. LetJbe a commuting family in Mn.I fA∈Jis diago- nalizable, then Jis simultaneously diagonalizable. Proof. Since Ais diagonalizable there are nlinearly independent eigenvec- tors of Aand if Sis in Mnand consists of those eigenvectors the matrix S−1ASis diagonal. Since eigenvectors of Aare the same as eigenvectors of B∈J, it follows that S−1BSis also diagonal. Thus S−1JS=D:= all diagonal matrices. Theorem 4.2.4. LetJ⊂Mnbe a commuting family. There is a unitary matrix U∈Mnsuch that U∗AU is upper triangular for each A∈J. Proof. From the proof of Schur’s Theorem we have that the eigenvectors chosen for Uare the same for all A∈J. This follows because after the first step we have reduced AandBto ·A11A12 0A22¸ and·B11B12 0B22¸ respectively. Commutativity is preserved under simultaneous similarity and therefore A22andB22commutes. Therefore at the second step the same eigenvector can be selected for allB22⊂J2, a commuting family. 176 CHAPTER 4. UNITARY MATRICES Theorem 4.2.5. IfA∈Mn(R), there is a real orthogonal matrix Q∈ Mn(R)such that (?) QTAQ= A1 A2? 0... Ak 1≤k≤n where each Aiis a real 1×1matrix or a real 2×2matrix with a non real pair of complex conjugate eigenvalues. Theorem 4.2.6. LetJ⊂Mn(R)be a commuting family. There is a real orthogonal matrix Q∈Mn(R)for which QTAQ has the form (?)for every A∈J. Theorem 4.2.7. Suppose A, B∈Mn(C)have eigenvalues α1,... ,αnand β1,... ,βnrespectively. If AandBcommute then there is a permutation i1...i nof the integers 1,... ,n for which the eigenvalues of A+Bareαj+ βij,j=1,... ,n .T h u sσ(A+B)⊂σ(A)+σ(B). Proof. Since J={A, B}f o r m sac o m m u t i n gf a m i l yw eh a v et h a te v e r y eigenvector of Ais an eigenvector of B, and conversely. Thus if Ax=αjx we must have that Bx=Bijx. But how do we get the permutation? The answer is to simultaneously triangularize with U∈Mn.W eh a v e U∗AU=Tand U∗BU=R. Since U∗(A+B)U=T+R we have that the eigenvalues pair up as described. Note: We don’t necessarily need AandBto commute. We need only the hypothesis that AandBare simultaneously diagonalizable. IfAandBdo not c o m m u t el i t t l ec a nb es a i do f σ(A+B). In particular σ(A+B)$σ(A)+σ(B). Indeed, by summing upper triangular and lower triangular matrices we can exhibit a range of possibilities. Let A=[01 00], B=[00 10],σ(A+B)={−1,1}butσ(A)=σ(B)={0}. Corollary 4.2.1. Suppose A, B∈Mnare commuting matrices with eigen- valuesα 1,... ,αnandβ1,... ,βnrespectively. If αi6=−βjfor all 1≤i, j≤n, thenA+Bis nonsingular. 4.3. EXERCISES 177 Note: Giving conditions for the nonsingularity of A+Bin terms of various conditions on AandBis a very di fferent problem. It has many possible answers. 4.3 Exercises 1. Characterize all diagonal unitary matrices and all diagonal orthogonal matrices in Mn. 2. Let T(θ)=£cosθ−sinθ sinθcosθ¤ whereθis any real. Then T(θ)i srealorthog- onal. Prove that if U∈M2(R) is real orthogonal, then Uhas the form T(θ)f o rs o m e θor U=·10 0−1¸ T(θ), and conversely. 3. Let us de fine the n×nmatrix Pto be a w-permutation matrix if for every vector x∈Rn, the vector Px has the same components asxin value and number, though possibly permuted. Show that w-permutation matrices are permutation matrices. 4. In R2identify all Householder transformations that are rotations. 5. Given any unit vector win the plane formed by eiandej.E x p r e s s the Householder matrix for this vector. 6. Show that the set of unitary matrices on Cnforms a subgroup of the subset of GL(n,C). 7. In R2,prove that the product of two (Householder) re flections is a rotation. (Hint. If the re flection angles are θ1andθ2,then the rotation angle is 2 ( θ1−θ2).) 8. Prove that the unitary matrices are closed the norm. That is, if the sequence {Un}⊂Mn(C) are all unitary and lim n→∞Un=Uin the k·k2norm, then Uis also unitary. 9. Let A∈Mnbe invertible. De fineG=Ak,(A−1)k,k=1,2,.... Show thatGis a subgroup of Mn. Here the group multiplication is matrix multiplication. 178 CHAPTER 4. UNITARY MATRICES 10. Prove that the unitary matrices are closed under pointwise conver- gence. That is, if the sequence {Un}⊂Mn(C) are all unitary and limn→∞Un=Ufor each ( ij)entry, then Uis also unitary. 11. Suppose that A∈Mnand that AB=BAfor all B∈Mn.Show that Ais a multiple of the identity. 12. Prove that a unitary matrix Ucan be written as V−1W−1VW for unitary V,W if and only if det U= 1. (Bellman, 1970) 13. Prove that the only triangular unitary matrices are diagonal matrices. 14. We know that given any bounded sequence of numbers, there is a convergent subsequence. (Bolzano-Weierstrass Theorem). Show that the same is true for matrices for any given matrix norm. In particular,show that if U nis any sequence of unitary matrices, then there is a convergent subsequence. 15. The Hadamard Gate (from quantum computing) is de fined by the matrix H=1√ 2·11 1−1¸ . Show that this transformation is a House- holder matrix. What are its eigenvalues and eigenvectors? 16. Show that the unitary matrices do not form a subspace Mn(C). 17. Prove that if a matrix A∈Mn(C) preserves the orthonormality of one orthonormal basis, then it must be unitary. 18. Call the matrix Aacheckerboard matrix if either (I)aij=0 ifi+jis even or (II) aij=0ifi+jis odd We call the matrices of type I even checkerboard and type II odd checkerboard .D efineCH(n)t ob ea l l n×ninvertible checkerboard matrices. The questions below all pertain to square matrices. (a) Show that if nis odd there are no invertible even checkerboard matrices. (b) Prove that every unitary matrix Uhas determinant with modulus one. (That is, |detU|=1.) (c) Prove that nis odd the product of odd checkerboard matrices is odd. 4.3. EXERCISES 179 (d) Prove that if nis even then the product of an even and an odd checkerboard matrix is odd, while the product of two even (orodd) checkerboard matrices is even. (e) Prove that if nis even then the inverse of any checkerboard matrix is a checkerboard matrix of the same type. However, in light of(a), it is only true that if nis an invertible odd checkerboard matrix, its inverse is odd. (f) Suppose that n=2m. Characterize all the odd checkerboard invertible matrices. (g) Prove that CH(n) is a subgroup of GL(n). (h) Prove that the invertible odd checkerboard matrices of any size nforms a subgroup of CH(n). In connection with chess, checkerboard matrices give the type of chess board on which the maximum number of mutually non-attacking knightscan be placed on the even ( i+jis even) or odd ( i+jis odd) positions. 19. Prove that every unitary matrix can be written as the product of a unitary diagonal matrix and another unitary matrix whose first column has nonnegative entries. 180 CHAPTER 4. UNITARY MATRICES