some matrix theorems

Some Matrix Theorems PhL 12.11.04 This is all meat and potatoes matrix stuff, keep this document! It was written while I was reading M&M chapter 10. See separate notes for details of that chapter. A Warm-up Example The eigenvectors of a symmetric matrix are orthogonal (Theorem later). Let's look at a simple example. B = so B-E = and secular says (a-)(c-) -b2 = 0 which we rewrite as 2 - (a+c) + (ac-b2) = 0, therefore = (1/2) [ (a+c) ]. Notice that we can factor this as (-+)(--) = 0 so that tells us +- = ac-b2 and also that (+ + -) = a+c. Aside: Notice that the eigenvalues are the same only if a=c and b=0, so the only possible degenerate 2x2 matrix is a multiple of the identity. This seems a surprising result to me, but it must be true. (See theorem 4S below) The eigenvalue equations written out are these: (two pairs of equations) (a-)x + by = 0 bx + (c-)y = 0 We cannot of course to Cramer's to solve since det=0. Assuming b 0, we can solve second one for x to get x = [(-c)/b] y. When this is put into the first equation, it becomes 0y=0, so any y works. Therefore, our eigenvectors are these: = k = x So if we install our two eigenvalues, we get two eigenvectors and they are different. Are they orthogonal? That is our big question. The answer is YES. We find by direct calculation that x+ x- = 0. ********************************* And now on with the show ********************* Theorem 0: A real matrix A can have complex eigenvalues and complex eigenvectors. An example is A = which has Maple = [a + I b, 1, {[-I, 1]}], [a - I b, 1, {[I, 1]}] where format is eigenvalue, multiplicity, eigenvector. You see the complex eigenvalues and the complex eigenvectors. Later we see that a symmetric real matrix A has everything real. Definition: If Ax=0, the nullity of A is the dimensionality of the nullspace of A, which is in turn the number of distinct non-zero vectors that solve Ax = 0. Definition: The geometric multiplicity of an eigenvalue of the problem Ax=x is the nullity of (A-E), that is, it is the dimensionality of the nullspace of (A-E). It is thus the number of independent non-zero solutions x of the equation (A-E)x = 0. Definition: The algebraic multiplicity of an eigenvalue is the number of times it appears in the factored secular equation. Theorem 1 : Geometric multiplicity m Algebraic multiplicity k. This is not quite as obvious as it looks, so we peek at Stakgold page 157 for a proof. Start with geo = m. You then have m distinct eigenvectors for Ax = 1x. Stakgold tells us to "go to a basis where the matrix A has the form shown", in which form these m eigenvectors are associated with the first m unit vectors, and the matrix A has an upper left corner that is just 1 times Em. How do we know that this is possible to do? I will answer this "constructively" by showing how you would get there from an arbitrary starting point. Apply M&M's Pivot and Twist process from page 320 where you take for your first eigenvalues the m copies of 1, and get the matrix A into the form shown in (10-41) but where the triangular matrix is m x m with all 1, and we have not processed the rest of the matrix. Getting to this point corresponds to some change of basis x' = Qx from the starting basis. If we now consider just this mxm piece of the larger matrix, we can think of the local problem AX = X and we have assumed in the Pivot and Twist process m column vectors for X, these are our m eigenvectors. They are linearly independent (since m = geo) so X is invertible. Thus, we know we can diagonalize in this local region by saying X-1AX = . But this is just another basis change x" = Xx'. Thus, we have arrived at a basis x" where the matrix indeed has the form shown on page 137 of Stakgold. When we enlarge to diag(X,1), the B area gets altered by the diagonalization stage, which is fine, and it ends up being Stakgolds B. Now we can finish Stakgold's proof. With A in the form shown, the secular equation has the form that (-1)m det(C-E) = 0. Since the second factor might have more roots at 1, we conclude the result we need, which is k m. Typically, in fact, there will be more roots in the det(C-E) part. Notice that this proof did not in fact require our final diagonalization step. Once the submatrix is in triangular form, we get the same secular equation just quoted, and we draw the same conclusion. Corollary: For any matrix A of order N, if is an eigenvalue of algebraic multiplicity k, then there can be at most k distinct eigenvectors associated with . Theorem 2: For any NxN matrix A, if is an eigenvalue of algebraic multiplicity k, the number m of distinct eigenvectors associated with is given by m = N - rank(A-E) and 1 m k. Proof: the number m is the nullity of A-E and according to Theorem R6 (way below), m = N - rank(A-E). Although it would seem at first that m could range from 0 to N, it really can only range from 1 to k. The upper limit comes from Theorem 1 above which says m k. The lower limit occurs because, when is an eigenvalue, rank(A-E) < N since det(A-E) = 0, so the largest rank(A-E) can be is N-1, in which case m = 1. Corollary: There is always at least one eigenvector for a given . (just because m 1 ) A matrix always has N eigenvalues, but they can clump in sameness groups, eg, all could be the same. Question: Does a Hermitian NxN matrix always have N eigenvectors? The answer is yes, and this time we go to Stakgold page 160. Again, things are very subtle. For warm up, consider this example of algebraic multiplicity = 2, which is NOT Hermitian, = 1 = . The upper equation says z = 0 so we get = ~ . This is the ONLY eigenvector. Now consider: = = c + 1. This is an example of something important for this theorem. Eigenvalue 1 has a manifold of dimension 1, meaning geo m = 1, even though our alg k = 2. Call this manifold M1 . The perp space M1 clearly has dimension 1. But the perp space is not "closed" under the action of A. We have y = in M1 , but Ay = c + 2 which means the result has a piece in M1 and a piece in M1. This says that M1 is not a linear manifold. If it were, we would consider Ay =2y in this manifold, and we know that there is always one eigenvalue and one eigenvector in a manifold. But this would lead to a contradiction because there IS no other 2 in our secular equation. But since M1 is not a manifold, we have no contradiction. In this example, then, you cannot "partition" the space E2 into two eigenmanifolds of A each of dim = 1. Another way to say this is that you cannot partition E2 into a set of separate nullspaces of (A - E). The nullspace has dim = 1, and the other dim is not a separate nullspace of some other eigenvalue. Now we are ready to move on. Theorem 3: Let A be an NxN complex matrix which has only one eigenvalue and its corresponding single eigenmanifold. Matrix A therefore has algebraic multiplicity k = N. In general, the geometric multiplicity m is m N (another theorem). However, if A is Hermitian, then m =k = N. Proof: Let M1 be the eigenmanifold of 1 and assume some geometric multiplicity m = m1 < N. Consider vector y in M1. When A is Hermitian, Ay is also in M1 (as we shall show below), so we consider the reduced problem Ay=y in Hilbert space M1 which has dimension N - m1. This problem must have at least one eigenvalue and eigenvector. The eigenvalue cannot be 1 because all vectors with 1 are in M1. The eigenvalue cannot be some other value 2 1 because A has no eigenvalue other than 1. Thus, the space M1 must be null, which means m1 = N. The reason Ay is in M1 if y is in M1 is this: (x,Ay) = (Ax,y) = (x',y) = 0 for any x. We are using x and x' as being in M1 and y in M1. Note that A being Hermitian is used in the first step. We have seen in our example earlier that if A is not Hermitian, then Ay need not be in M1 and generally has components in both M1 and in M1. Thus, in that case, M1 is not a closed space under the action of A. That is, A does not have domain = range = some Hilbert space. Theorem 4: The only Hermitian matrix having just one eigenvalue is A = E. Proof: If A is Hermitian with only one 1, then rank(A-1E) = N-m = 0 which means A-1E = 0 so A = 1E. There is another way to see this. Start with any matrix A and apply the M&M Pivot and Rotate process to get it to triangular form. The secular for this matrix is (-1)N = 0. This triangular matrix is equivalent to the starting matrix, just a basis change away. So any matrix with a single eigenvalue can be put into this form. But such a triangular matrix is only Hermitian of all off diagonal elements vanish. Theorem 5: If A is Hermitian, then each eigenmanifold has k = m. That is to say, for each eigenmanifold, the geometric multiplicity has its maximal value and it equal to the algebraic multiplicity. Proof: We just continue the general idea of Theorem 3 above, see also Stakgold page 160. We pick a first manifold and assume it has geo mult = m1 and that is our M1. We then look at our reduced problem in M1 of dim N - m1. We find the next manifold of geo = m2 and that is M2 so we then look at (M1+M2). We continue on and in this way we find that m1 + m2 + .... = N. The key is that each of these perp spaces is closed under A due to the Hermiticity of A. Now, we know that k1 + k2 + ... = N because we are allowing complex roots in our analysis here, and the secular equation is a poly of degree N. But suppose we were doing a "real version" of our proof here, then we would only know that k1 + k2 + .. N, the idea being that we don't count complex roots if there were some. Consider then this collection of information: m1 + m2 + .... = N k1 + k2 + .. N mi ki We then know that N = m1 + m2 + .... k1 + k2 + .... N. It would follow that k1 + k2 + .. = N and we get this result anyway. We can now show that mi = ki for all i, meaning that each manifold is "geometrically maximal". Assume this is not true, and introduce some i 0 such that mi = ki - i. Then since mi = ki = N, we have i = 0. Since all i are 0, we have that i = 0 for all i. Thus, it must be that mi = ki for all i. Theorem 5A. If A is Hermitian, then the nullspaces of (A - E)x=0 partition the whole space. You can then decompose any vector f into components each of which is in one of these nullspaces. These nullspaces are of course the eigenmanifolds of Ax = x. There are no vectors x in the whole space that are not elements of one of the nullspaces. For A non-Hermitian, we showed a 2x2 example earlier where we could find elements that were in non of the nullspaces. Proof: These statements all follow from the comments in the proof of the previous theorem. This partitioning idea I think is a main feature of Hermitian A. Theorem 6: An NxN Hermitian matrix has N distinct eigenvectors. Proof: This follows from the previous theorem. Each manifold has the maximal mi = ki and the total number of distinct eigenvectors is mi = N. Notice that a non-Hermitian matrix can have less than N eigenvectors. Theorem 7: All eigenvalues of a Hermitian matrix are all real. Proof: ( guided by Stakgold page 181). Ax = x is the eigenvalue problem, so line 1: (Ax,x)*= (x,Ax) = (x,x) line 2: (Ax,x)* =[ (x,Ax) ] * = [ (x,x) ] * = *(x,x)* = *(x,x) Comparison shows that = * so is real. From the first line, then (x,Ax) is also real. Theorem 8: For any Hermitian matrix A in complex space, the eigenvectors corresponding to different eigenvalues are orthogonal. [ Comments: If A is not Hermitian, we don't have (x1,A†x2) = (x1,Ax2) and the proof below fails and eigenvectors in different eigenmanifolds are generally NOT orthogonal, even in the case that all eigenvalues are different. In this case the eigenvectors at least are linearly independent, though not orthogonal. ] Proof: Write Ax1 = 1x1 Ax2 = 2x2 . Then (x2,Ax1) = 1(x2, x1) (x1,Ax2) = 2(x1, x2). We now alter the first of these equations as follows: (x2,Ax1)* = 1*(x2, x1)* => (Ax1,x2) = 1* (x1, x2) = (x1,A†x2) If A is Hermitian then (x1,A†x2) = (x1,Ax2) and our two equations are now (x1,Ax2) = 1* (x1, x2) (x1,Ax2) = 2 (x1, x2) Subtract to find that [ 1* - 2 ] (x1, x2) = 0. From a previous theorem we know that all are real, so this becomes [ 1 - 2 ] (x1, x2) = 0 Therefore, if two eigenvalues are different, their eigenvectors must be orthogonal. Theorem 9: A Hermitian NxN matrix A has N eigenvectors which are linearly independent and thus form a basis in EN. It is possible to make the eigenvectors form an orthogonal or orthonormal set. Proof: The mi eigenvectors for each eigenmanifold are linearly independent by assumption, since mi is the geometric multiplicity of that manifold. We know that eigenvectors from different eigenmanifolds are orthogonal to each other from Theorem 8 (below). Thus, the total collection of eigenvectors from all the manifolds is linearly independent. According to theorem 3, this collection contains N eigenvectors because each manifold is geometrically maximal, mi = ki. Thus, our set of N eigenvectors is linearly independent. If put into a matrix, that matrix would be therefore invertible. Within each eigenmanifold, we can do a Gram-Schmidt orthogonalization process if we want to make the local vectors be either orthogonal or orthonormal. Thus, the overall set of eigenvectors can be made orthogonal or orthonormal. It is good to remember that each eigenvector has a scaling degree of freedom for the orthogonal sets. Theorem 10: The components of the eigenvectors of a Hermitian matrix A are in general complex. Consider Ax = x. Even though is known to be real, A can have complex elements, so when we solve the system of N equations in N unknowns, we generally get complex x. Theorem 11: An NxN Hermitian matrix A can be diagonalized by a unitary similarity X, and X is unique only if there are no degenerate eigenmanifolds for A. A can also be diagonalized by a huge set of non-unitary X similarities. Proof: The eigenvalue problem is AX = X. Since the columns of X (the N eigenvalues xi) are linearly independent, detX 0 and we can write X-1AX= . This is true for any choice of how we normalize those eigenvectors. If we choose an orthonormal set for the xi , which is possible by Theorem 9, then we have X†X = 1 and X is then a unitary matrix. The reason is this: orthonormal eigenvectors => k, = (xk, x) = i (xk)i* (x)i = i Xik* Xi = i (X†)ki Xi = (X†X)k => 1 = X†X There are many similarities X we can find to diagonalize A, but at least one of them will be unitary. The unitary X is not unique if there are degenerate manifolds of A. Within each, we are free to orthogonalize in a variety of ways, each giving different X. If there is no degeneracy, then there is only one unitary X that does the job. ******************************** We can now provide real symmetric versions of the above theorems. Every real symmetric matrix is Hermitian, so all the theorems pass through. Since Ax = x and A and real, it does not make much sense to have x be complex. Making it complex just replicates the solutions in the real and imaginary parts. Theorem 1 : Geometric multiplicity m Algebraic multiplicity k. Corollary: For any matrix A of order N, if is an eigenvalue of algebraic multiplicity k, then there can be at most k distinct eigenvectors associated with . Theorem 2: For any matrix A of order N, nullity(A) = N - rank(A) Theorem 2A: For any NxN matrix A, if is an eigenvalue of algebraic multiplicity k, the number m of distinct eigenvectors associated with is given by m = N - rank(A-E) and 1 m k. Theorem 3S: Let A be an NxN real matrix which has only one eigenvalue and its corresponding single eigenmanifold. Matrix A therefore has algebraic multiplicity k = N. In general, the geometric multiplicity m is m N (another theorem). However, if A is real symmetric, then m =k = N. Theorem 4S: The only real symmetric matrix having just one eigenvalue is A = E. Theorem 5S: If A is real symmetric, then each eigenmanifold has k = m. That is to say, for each eigenmanifold, the geometric multiplicity has its maximal value and it equal to the algebraic multiplicity. Theorem 6S: An NxN real symmetric matrix has N distinct real eigenvectors. Theorem 7S: All eigenvalues of a real symmetric matrix are all real. This theorem is not very obvious when you just think of the secular equation. A priori, it could have complex roots. It is not obvious how you would directly prove that there are no complex roots just using the property Aij = Aji in the equation det(A-I)=0. In fact, none of these theorems is very obvious. Theorem 8S: For any real symmetric matrix A , the eigenvectors corresponding to different eigenvalues are orthogonal. Theorem 9S: A real symmetric NxN matrix A has N real eigenvectors which are linearly independent and thus form a basis in EN. It is possible to make the eigenvectors form an orthogonal or orthonormal set. Theorem 10S: The components of the eigenvectors of a real symmetric matrix A can be taken real with no loss of generality. Theorem 11S: An NxN real symmetric matrix A can be diagonalized by a real orthogonal similarity X, and X is unique only if there are no degenerate eigenmanifolds for A. A can also be diagonalized by a huge set of non-orthogonal X similarities. ********************************************* Some Theorems about Rank. Definition: The rank of a matrix is the size of the smallest non-zero sub-determinant. If detA 0, then the smallest non-zero det is the whole NxN, so rank = N. If A has all zeros, then rank = 0. Theorem R1: If the rank of an NxN matrix A is N-k, then there are only k eigenvectors of Ax=0. Theorem R2: If a row in a matrix is linearly dependent on the other rows, then any segment of that row will be linearly dependent on the corresponding segments of the other rows. Proof: If the whole row can be written as a lincom of other rows, this must be true of any piece of the row. If we say that r1 = r2 + r3 as vectors, then this sum must be true for each component and thus for any set of components, meaning for any subvector. And the rows are just such vectors. Theorem R3: If the rank of an NxN matrix A is N-k, then k rows of A are linearly dependent on other rows. Only N-k rows of A are linearly independent. The same is true for the columns. This means that there are k "relations" among the rows, if k are linearly dependent on the others. Suppose an NxN matrix has one row which is linearly dependent on the others. Then detA = 0 and we know that rank < N. Suppose two rows are linearly dependent. Any N-1 size submatrix you pick will have to include N-1 elements from at least one of these two rows. By the previous theorem, the (N-1)-length row segments in this submatrix will be linearly dependent, so detA' = 0 for all N-1 size submatrices. This means rank < N-1. And if 3 rows are linearly dependent, then detA" = 0 for all N-2 size submatrices, and so on. The same discussion can be repeated in terms of columns. Here is another way to make the argument. Suppose all 3x3 sub dets are 0. Since this is true as we move horizontally on a specific set of 3 rows, this means that those 3 rows are not linearly indep. Thus, we cannot find ANY set of 3 rows that are lin indep. Thus, the number of lin indep rows must be < 3, and we say that rank < 3. Theorem R4: dim(RA) = rank [ the dimensionality of the range in Ax=f is equal to the rank of A. ] Proof: The previous theorem says that N-Rank is the number of rows of a matrix that are linearly independent. The equation Ax = f is really a set of N-Rank equations in N unknowns. Suppose we have 2 independent equations in 3 unknowns x,y,z. Then we can just pick x and get (y,z) for that x. This means a solution like [ x, y(x), z(x)] where x is anything. This is a "ray" in E3. The range then has 1 dimension. If we had only 1 equation in 3 unknowns, we could just pick x and y, then we would have [x, y, z(x,y)] and then our range would have 2 dimensions. These would be the axes in RA: [1,0,z(1,0)] and [0, 1, z(0,1)]. In the general case, we have N-Rank equations in N unknowns, so the dimension of RA is going to be Rank. Theorem R5: R(A) = N(A†). The perp-space of the range of A is equal to the nullspace of A† . (Alternative Theorem) See page 153 Stakgold. Proof has two directions: (a) If z is in N(A†) and f is in R(A), then (f,z) = (Ax,z) = (x,A†z) = (x,0) = 0. This says that z must therefore be in R(A), so N(A†) R(A). (b) If z is in R(A) and f in R(A), then 0 = (f,z) = (Ax,z) = (x,A†z). Since x can be ANY point in the space, this means A†z = 0, so z must be in N(A†). Thus, R(A) N(A†). Theorem R6: For any NxN matrix A, rank(A) + nullity(A) = N. Also, nullity(A) = nullity(A†) and rank(A) = rank(A†) See Stakgold page 153-4. The conclusion of the previous theorem is that N(A†) = R(A), so dim[N(A†)] = dim[R(A)]. We certainly know that dim[R(A)] + dim[R(A)] = N, so we know that dim[R(A)] + dim[N(A†)] = N. If we can just show that dim[N(A†)] = dim[N(A)], which seems awfully reasonable, then dim[R(A)] + dim[N(A)] = N. This then says that rank(A) + nullity(A) = N. This missing piece that dim[N(A†)] = dim[N(A)]. Stak shows this on page 154, along with the partner fact. Thus, he shows that nullity(A) = nullity(A†) and rank(A) = rank(A†). I will read this proof later. Comments: This theorem really is very reasonable. Think about what happens as you apply A to all possible x in your space. For x in the nullspace subspace, all vectors map to 0 via Ax = 0. All vectors x in your space that are not in the nullspace must therefore map to some non-zero f in the range space via Ax = f. If the mapping Ax = f were somehow many-to-one, you could imagine that you might "lose" some dimensions through this mapping, and have dim(range) < N - dim(nullspace). But this does not happen and here is why. Suppose the nullspace has basis vectors e1 and e2 and there are two other basis vectors e3 and e4. Then let Ae3 = f3 and Ae4 = f4. If we had f3 =f4, then A(e3 - e4) = 0 and we would have (e3 - e4) in the nullspace, which is impossible. Thus, the mapping from N(A) R(A) does not "lose" any dimensions.