Home / Math and Physics Files / Math / Linear Algebra / don allen linear algebra

chapter2

PDF · 62 pages · 414.4 KB

Chapter 2, 'Matrices and Linear Algebra', from a linear algebra course text in a folder labeled 'don allen linear algebra'. It defines matrices, special types (diagonal, triangular, symmetric, Hermitian, skew-symmetric), and covers addition, multiplication, transposes, column and row spaces, and inverses. It then begins linear systems, with the three elementary equation operations and solvability of Ax=b.

AI-written summary; may contain errors.

Extracted text (machine-read; may contain errors)

Chapter 2 Matrices and Linear Algebra 2.1 Basics Deﬁnition 2.1.1. Amatrix is an m×narray of scalars from a given ﬁeld F. The individual values in the matrix are called entries . Examples. A=^ 21 3 −124 B=^ 12 34 Thesizeof the array is–written as m×n,w h e r e m×n cA number of rows number of columns Notation A= a 11a12... a 1n a21a22... a 2n an1an2... a mn A ←− rows t AAc columns A:= uppercase denotes a matrix a:= lower case denotes an entry of a matrix a∈F. Special matrices 33 34 CHAPTER 2. MATRICES AND LINEAR ALGEBRA (1) If m=n, the matrix is called square .I nt h i sc a s ew eh a v e (1a) A matrix Ais said to be diagonal if aij=0 iW=j. (1b) A diagonal matrix Amay be denoted by diag( d1,d2,... ,d n) where aii=diaij=0 jW=i. The diagonal matrix diag(1 ,1,... , 1) is called the identity matrix and is usually denoted by In= 10 ... 0 01 ...... 01  or simply I,w h e n nis assumed to be known. 0 = diag(0 ,... , 0) is called the zero matrix . (1c) A square matrix Lis said to be lower triangular if fij=0 i<j . (1d) A square matrix Uis said to be upper triangular if uij=0 i>j . (1e) A square matrix Ais called symmetric if aij=aji. (1f) A square matrix Ais called Hermitian if aij=¯aji(¯z:= complex conjugate of z). (1g) Eijhas a 1 in the ( i, j) position and zeros in all other positions. (2) A rectangular matrix Ais called nonnegative if aij≥0a l l i, j. It is called positive if aij>0a l l i, j. Each of these matrices has some speci al properties, which we will study during this course. 2.1. BASICS 35 Deﬁnition 2.1.2. The set of all m×nmatrices is denoted by Mm,n(F), where Fis the underlying ﬁeld (usually RorC). In the case where m=n we write Mn(F) to denote the matrices of size n×n. Theorem 2.1.1. Mm,nis a vector space with basis given by Eij,1≤i≤ m,1≤j≤n. Equality, Additi on, Multiplication Deﬁnition 2.1.3. Two matrices AandBare equal if and only if they have t h es a m es i z ea n d aij=bijalli, j. Deﬁnition 2.1.4. IfAis any matrix and α∈Fthen the scalar multipli- cation B=αAis deﬁned by bij=αaijalli, j. Deﬁnition 2.1.5. IfAandBare matrices of the same size then the sum AandBis deﬁned by C=A+B,w h e r e cij=aij+bijalli, j We can also compute the diﬀerence D=A−Bby summing Aand (−1)B D=A−B=A+(−1)B. matrix subtraction. Matrix addition “inherits” many properties from the ﬁeldF. Theorem 2.1.2. IfA, B, C∈Mm,n(F)andα,β∈F,t h e n (1)A+B=B+A commutivity (2)A+(B+C)=(A+B)+C associativity (3)α(A+B)=αA+αB distributivity of a scalar (4) If B=0 (a matrix of all zeros) then A+B=A+0= A (4)(α+β)A=αA+βA 36 CHAPTER 2. MATRICES AND LINEAR ALGEBRA (5)α(βA)=αβA (6)0A=0 (7)α0=0 . Deﬁnition 2.1.6. Ifxandy∈Rn, x=(x1...x n) y=(y1...y n). Then the scalar or dot product of xandyis given by x, yX=n3 i=1xiyi. Remark 2.1.1. (i) Alternate notation for the scalar product: x, yX=x·y. (ii) The dot product is de ﬁned only for vectors of the same length. Example 2.1.1. Letx=( 1,0,3,−1) and y=( 0,2,−1,2) thenx, yX= 1(0) + 0(2) + 3( −1)−1(2) =−5. Deﬁnition 2.1.7. IfAism×nandBisn×p.L e t ri(A) denote the vector with entries given by the ithrow of A,a n dl e t cj(B) denote the vector with entries given by the jthrow of B. The product C=ABis the m×pmatrix deﬁned by cij=ri(A),cj(B)X where ri(A) is the vector in Rnconsisting of the ithrow of Aand similarly cj(B) is the vector formed from the jthcolumn of B. Other notation for C=AB cij=n k=1aikbkj1≤i≤m 1≤j≤p. Example 2.1.2. Let A=}101 321] and B= 21 30 −11 . Then AB=}12 11 4] . 2.1. BASICS 37 Properties of matrix multiplication (1) If ABexists, does it happen that BAexists and AB=BA?T h e answer is usually no. First AB andBA exist if and only if A∈ Mm,n(F)a n d B∈Mn,m(F). Even if this is so the sizes of ABand BAare diﬀerent ( ABism×mandBAisn×n) unless m=n. However even if m=nwe may have ABW=BA.S e e t h e e x a m p l e s below. They may be di ﬀerent sizes and if they are the same size (i.e. AandBa r es q u a r e )t h ee n t r i e sm a yb ed i ﬀerent A=[ 1,2]B=}−1 1] AB=[ 1 ] BA=}−1−2 12] A=}12 34] B=}−11 01] AB=}−13 −37] BA=}22 34] (2) If Ais square we de ﬁne A1=A, A2=AA, A3=A2A=AAA An=An−1A=A···A(nfactors) . (3)I= diag(1 ,... , 1). If A∈Mm,n(F)t h e n AIn=Aand ImA=A. Theorem 2.1.3 (Matrix Multiplication Rules). Assume A, B ,a n d C are matrices for which all products below make sense. Then (1)A(BC)=(AB)C (2)A(B±C)=AB±ACand(A±B)C=AC±BC (3)AI=AandIA=A (4)c(AB)=(cA)B (5)A0=0 and0B=0 38 CHAPTER 2. MATRICES AND LINEAR ALGEBRA (6) For Asquare ArAs=AsArfor all integers r, s≥1. Fact: IfACandBCare equal, it does not follow that A=B. See Exercise 60. Remark 2.1.2. We use an alternate notation for matrix entries. For any matrix Bdenote the ( i, j)-entry by ( B)ij. Deﬁnition 2.1.8. LetA∈Mm,n(F). (i) De ﬁne the transpose ofA, denoted by AT,t ob et h e n×mmatrix with entries (AT)ij=aji. (ii) De ﬁne the adjoint ofA, denoted by A∗,t ob et h e n×mmatrix with entries (A∗)ij=¯ajicomplex conjugate Example 2.1.3. A=}123 541] AT= 15 24 31  In words ...“The rows of Abecome the columns of AT, taken in the same order.” The following results are easy to prove. Theorem 2.1.4 (Laws of transposes). (1)(AT)T=Aand(A∗)∗=A (2)(A±B)T=AT±BT(and for ∗) (3)(cA)T=cAT(cA)∗=¯cA∗ (4)(AB)T=BTAT (5) If Ais symmetric A=AT 2.1. BASICS 39 (6) If Ais Hermitian A=A∗. More facts about symmetry. Proof. (1) We know ( AT)ij=aji.S o( ( AT)T)ij=aij.T h u s( AT)T=A. (2) (A±B)T=aji±bji.S o( A±B)T=AT±BT. Proposition 2.1.1. (1)Ais symmetric if and only if ATis symmetric. (1)∗Ais Hermitian if and only if A∗is Hermitian. (2) If Ais symmetric, then A2is also symmetric. (3) If Ais symmetric, then Anis also symmetric for all n. Deﬁnition 2.1.9. A matrix is called skew-symmetric if AT=−A. Example 2.1.4. The matrix A= 012 −10−3 −23 0  is skew-symmetric. Theorem 2.1.5. (1) If Ais skew symmetric, then Ais a square matrix andaii=0,i=1,... ,n . (2) For any matrix A∈Mn(F) A−AT is skew-symmetric while A+ATis symmetric. (3) Every matrix A∈Mn(F)can be uniquely written as the sum of a skew-symmetric and symmetric matrix. Proof. (1) If A∈Mm,n(F), then AT∈Mn,m(F). So, if AT=−Awe must have m=n.A l s o aii=−aii fori=1,... ,n .S oaii=0f o ra l l i. 40 CHAPTER 2. MATRICES AND LINEAR ALGEBRA (2) Since ( A−AT)T=AT−A=−(A−AT), it follows that A−ATis skew-symmetric. (3) Let A=B+Cbe a second such decomposition. Subtraction gives 1 2(A+AT)−B=C−1 2(A−AT). The left matrix is symmetric while the right matrix is skew-symmetric. Hence both are the zero matrix. A=1 2(A+AT)+1 2(A−AT). Examples. A=J0−1 10o is skew-symmetric. Let B=}12 −14] BT=}1−1 24] B−BT=}03 −30] B+BT=}21 18] . Then B=1 2(B−BT)+1 2(B+BT). An important observation about matri x multiplication is related to ideas from vector spaces. Indeed, two very important vector spaces are associatedwith matrices. Deﬁnition 2.1.10. LetA∈M m,n(C). (i)Denote by cj(A): =jthcolumn of A cj(A)∈Cm. We call the subspace of Cmspanned by the columns of Athe column space ofA.W i t h c1(A),...,c n(A) denoting the columns of A 2.1. BASICS 41 the column space is S(c1(A),...,c n(A)). (ii) Similarly, we call the subspace of Cnspanned by the rows of Atherow space ofA.W i t h r1(A),...,r m(A) denoting the rows of Athe row space is therefore S(r1(A),...,r m(A)). Letx∈Cn,w h i c hw ev i e wa st h e n×1m a t r i x x=[x1...x n]T.T h e product Axis deﬁned and Ax=n3 j=1xjcj(A). That is to say, Ax∈S(c1(A),... ,c n(A)) = column space of A. Deﬁnition 2.1.11. LetA∈Mn(F). The matrix Ais said to be invertible if there is a matrix B∈Mn(F) such that AB=BA=I. In this case Bis called the inverse ofA, and the notation for the inverse is A−1. Examples. (i) Let A=}13 −12] Then A−1=1 5}2−3 11] . (ii) For n=3w eh a v e A= 12−1 −13−1 −23−1  A−1= 01−1 −13−2 −37−5  A square matrix need not have an inverse, as will be discussed in the next section. As examples, the two matrices below do not have inverses A=}1−2 −12] B= 101 021122  42 CHAPTER 2. MATRICES AND LINEAR ALGEBRA 2.2 Linear Systems The solutions of linear systems is likely the single largest application of ma- trix theory. Indeed, most reasonable problems of the sciences and economicsthat have the need to solve problems of several variable almost without ex-ception are reduced to component parts where one of them is the solutionof a linear system. Of course the entire solution process may have the linear system solver as a relatively small component, but an essential one. Even the solution of nonlinear problems, esp ecially, employ linear systems to great and crucial advantage. To be precise, we suppose that the coe ﬃcients a ij,1≤i≤mand 1≤ j≤nand the data bj,1≤j≤ma r ek n o w n . W ed e ﬁne the linear system for the nunknowns x1,...,x nto be a11x1+a12x2+···+a1nxn=b1 a21x1+a22x2+···+a2nxn=b2 (∗) am1x1+am2x2+···+amnxn=bm The solution set is deﬁned to be the subset of Rnof vectors ( x1,...,x n)t h a t satisfy each of the mequations of the system. The question of how to solve a linear system includes a vast literature of theoretical and computation methods. Certain systems form the model of what to do. In the systemsbelow we note that the ﬁrst one has three highly coupled (interrelated) variables. 3x 1−2x2+4x3=7 x1−6x2−2x3=0 −x1+3x2+6x3=−2 The second system is more tractable because there appears even to the untrained eye a clear and direct method of solution. 3x1−2x2−x3=7 x2−2x3=1 2x3=−2 I n d e e d ,w ec a ns e er i g h to ﬀthatx3=−1.Substituting this value into the second equation we obtain x2=1−2=−1.Substituting both x2andx3 into the ﬁrst equation, we obtain 2 x1−2(−1)−(−1) = 7 ,gives x1=2.The 2.2. LINEAR SYSTEMS 43 solution set is the vector (2 ,−1,−1).The virtue of the second system is that the unknowns can be determined on e-by-one, back substituting those already found into the next equation until all unknowns are determined. Soif we can convert the given system of the ﬁrst kind to one of the second kind, we can determine the solution. This procedure for solving linear systems is therefore the applications of operations to e ﬀect the gradual elimination of unknowns from the equations until a new system results that can be solved by direct means. The oper-ations allowed in this process must have precisely one important property:They must not change the solution set by either adding to it or subtracting from it. There are exactly three such operations needed to reduce any set of linear equations so that it can be solved directly. (E1) Interchange two equations.(E2) Multiply any equation by a nonzero constant. (E3) Add a multiple of one equation to another. This can be summarized in the following theorem Theorem 2.2.1. Given the linear system (*). The set of equation opera- tions E1, E2, and E3 on the equations of (*) does not alter the solution setof the system (*). We leave this result to the exercises. Our main intent is to convert these operations into corresponding operations for matrices. Before we do this we clarify which linear systems can have a soltution. First, the system can be converted to matrix form by setting Aequal to the m×nmatrix of coeﬃcients, bequal to the m×1 vector of data, and xequal to the n×1 vector of unknowns. Then the system (*) can be written as Ax=b In this way we see that with c i(A)d e n o t i n gt h e ithcolumn of A,the system is expressible as x1c1(A)+···+xncn(A)=b From this equation it is clear that the system has a solution if and only if the vector bis inS(c1(A),···,cn(A)). This is summarized in the following theorem. 44 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Theorem 2.2.2. An e c e s s a r ya n ds u ﬃcient condition that Ax=bhas a solution is that b∈S(c1(A)...c n(A)). In the general matrix product C=AB, we note that the column space of C⊂column space of A.I nt h ef o l l o w i n gd e ﬁnition we regard the matrix A as a function acting upon vectors in one vector space with range in anothervector space. This is entirely similar to the domain-range idea of function theory. Deﬁnition 2.2.1. Therange ofA={Ax|x∈R n(o rCn)}. It follows directly from our discussion above that the range of Aequals S(c1(A),... ,c n(A)). Row operations: To solve Ax=bwe use a process called Gaussian elimination , which is based on row operations. Type 1: Interchange two rows. (Notation: Ri←→Rj) Type 2: Multiply a row by a nonzero constant. (Notation: cRi→Ri) Type 3: Add a multiple of one row to another row. (Notation: cRi+Rj→ Rj) Gaussian elimination is the process of reducing a matrix to its RREF using these row operations. Each of these operations is the respective analogue of the equation operations described above, and each can be realized by leftmatrix multiplication. We have the following.Type 1 E 1= 1...... 1...... ... ... 0... ... ... 1... ... ... ...1... ......... ...1... ... ... 1... ... ... 0... ... ... ......1 ......... ......1 rowi row j column icolumn j 2.2. LINEAR SYSTEMS 45 Notation: Ri↔Rj Type 2 E2= 1... ...... 1... ... ... ... c ... ... ... ...1 ...... ...1 rowi column i Notation: cR i Type 3 E3= 1... 1... ... ...... ... ... c ... ... ... ... ...1 ...1 rowj column i Notation: cR i+Rj, the abbreviated form of cRi+Rj→Rj Example 2.2.1. The operations  21 0 02 1 −102 R1←→R2 → 02 1 21 0 −102 4R3 → 02 1 21 0 −408  46 CHAPTER 2. MATRICES AND LINEAR ALGEBRA can also be realized as R1←→ R2: 010 100001  21 0 02 1 −102 = 02 1 21 0 −102  4R 3 : 100 010004  02 1 21 0 −102 = 02 1 21 0 −408  The operations  21 0 02 1 −102 −3R 1+R2 → 2R1+R3 21 0 −6−11 32 2  can be realized by the left matrix multiplications  100 010 201  10 0 −310 00 1  21 0 02 1 −102 = 21 0 −6−11 32 2  Note there are two matrix multiplications them, one for each Type 3 ele- mentary operation. Row-reduced echelon form. To each A∈Mm,n(E) there is a canonical form also in Mm,n(E) which may be obtained by row operations. Called the RREF, it has the following properties. (a) Each nonzero row has a 1 as the ﬁrst nonzero entry (:= leading one ). (b) All column entries above and below a leading one are zero. (c) All zero rows are at the bottom. (d) The leading one of one row is to the left of leading ones of all lower rows. Example 2.2.2. B= 1200 −1 0010 30001 00000 0 is in RREF. 2.2. LINEAR SYSTEMS 47 Theorem 2.2.3. LetA∈Mm,n(F). Then the RREF is necessarily unique. We defer the proof of this result. Let A∈Mm,n(F). Recall that the row space ofAis the subspace of Rn(orCn) spanned by the rows of A.I n symbols the row space is S(r1(A),... ,r m(A)). Proposition 2.2.1. ForA∈Mm,n(F)the rows of its RREF span the rows space of A. Proof. First, we know the nonzero rows of the RREF are linearly indepen- dent. And all row operations are linear combinations of the rows. Thereforet h er o ws p a c eg e n e r a t e df r o mt h eR R E Fi sc o n t a i n e di nt h er o ws p a c eo fA. If the containment is proper. That is there is a row of Athat is lin- early independent from the row space of the RREF, this is a contradiction because every row of Acan be obtained by the inverse row operations from the RREF. Proposition 2.2.2. IfA∈Mm,n(F)and a row operation is applied to A, then linearly dependent columns of Aremain linearly dependent and linearly independent columns of Aremain linearly independent. Proposition 2.2.3. The number of linearly independent columns of A∈ Mm,n(F)is the same as the number of leading ones in the RREF of A. Proof. LetS={i1...i k}be the columns of the RREF of Ahaving a lead- ing one. These columns of the RREF are linearly independent Thus these columns were originally linearly independent. If another column is linearlyindependent, this column of the RREF is linearly dependent on the columnswith a leading one. This is a contradiction to the above proposition. Proof of Theorem 2.2.3. By the way the RREF is constructed, left-to-right, and top-to-bottom, it should be apparent that if the right most row of the RREF is removed, there results the RREF of the m×(n−1) matrix formed from Aby deleting the nthcolumn. Similarly, if the bottom row of the RREF is removed there results a new matrix in RREF form, though notsimply related to the original matrix A. To prove that the RREF is unique, we proceed by a double induction, ﬁrst on the number of columns. We take it as given that for an m×1m a t r i x the RREF is unique. It is either the zero m×1 matrix, which would be t h ec a s ei f Awas zero or the matrix with a 1 in the ﬁrst row and zeros in 48 CHAPTER 2. MATRICES AND LINEAR ALGEBRA the other rows. Assume therefore that the RREF is unique if the number o fc o l u m n si sl e s st h a n n. Assume there are two RREF forms, B1and B2forA.N o w t h e R R E F o f Ais therefore unique through the ( n−1)st columns. The only di ﬀerence between the RREF’s B1andB2must occur in the nthcolumn. Now proceed by induction on the number of nonzero rows. Assume that AW=0 . I f Ahas just one row, the RREF of Ais simply thescalar multiple of Athat makes the ﬁrst nonzero column entry a one. Thus it is unique. If A= 0, the RREF is also zero. Assume now that the RREF is unique for matrices with less than mrows. By the comments above that the only di ﬀerence between the RREF’s B1andB2can occur at the (m, n)-entry. That is ( B1)m,nW=(B2)m,n. They are therefore not leading ones. (Why?) There is a leading one in the mthrow, however, because it is a non zero row. Because the row spaces of B1andB2are identical, this results in a contradiction, and therefore the ( m, n)-entries must be equal. Finally, B1=B2.This completes the induction. (Alternatively, the two systems pertaining to the RREF’s must have the same solution set to thesystem Ax=0 . W i t h( B 1)m,nW=(B2)m,n, it is easy to see that the solution sets to B1x=0a n d B2x=0m u s td i ﬀer.) ¤ Deﬁnition 2.2.2. LetA∈Mm,nandb∈Rm(orCn). De ﬁne [A|b]= a11... a 1nb1 a21... a 2nb2 am1... a mnbm  [A|b]i sc a l l e dt h e augmented matrix ofAbyb.[A|b]∈Mm,n+1(F). The augmented matrix is a useful notation for ﬁnding the solution of systems using row operations. Identical to other de ﬁnitions for solutions of equations, the equivalence of two systems is de ﬁned via the idea of equality of the solution set. Deﬁnition 2.2.3. Two linear systems Ax=bandBx=care called equiv- alent if one can be converted to the other by elementary equation opera- tions. It is easy to see that this implies the followingTheorem 2.2.4. Two linear systems Ax=bandBx=care equivalent if and only if both [A|b]and[B|c]have the same row reduced echelon form. We leave the prove to the reader. (See Exercise 23.) Note that the solution set need not be a single vector; it can be null or in ﬁnite. 2.3. RANK 49 2.3 Rank Deﬁnition 2.3.1. Therank of any matrix A,d e n o t eb y r(A), is the di- mension of its column space. Proposition 2.3.1. (i) The rank of Aequals the number of nonzero rows of the RREF of A, i.e. the number of leading ones. (ii)r(A)=r(AT). Proof. (i) Follows from previous results. (ii) The number of linearly independent rows equals the number of lin- early independent columns. The number of linearly independent rows is the number of linearly independent columns of AT–by de ﬁnition. Hence r(A)=r(AT). Proposition 2.3.2. LetA∈Mm,n(C)andb∈Cm.T h e n Ax=bhas a solution if and only if r(A)=r([A|b]),w h e r e [A|b]is the augmented matrix. Remark 2.3.1. Solutions may exist and may not. However, even if a so- lution exists, it may not be unique. Indeed if it is not unique, there is an inﬁnity of solutions. Deﬁnition 2.3.2. When Ax=bhas a solution we say the system is con- sistent . Naturally, in practical applications we want our systems to be consistent. When they are not, this can be an indicator that something is wrong withthe underlying physical model. In mathematics, we also want consistentsystems; they are usually far more interesting and o ﬀer richer environments for study. In addition to the column and row spaces, another space of great impor- tance is the so-called null space, the set of vectors x∈R nfor which Ax=0 . In contrast, when solving the simple single variable linear equation ax=b with aW= 0 we know there is always a unique solution x=b/a.I n s o l v i n g even the simplest higher dimensional systems, the picture is not as clear. Deﬁnition 2.3.3. LetA∈Mm,n(F). The null space ofAis deﬁned to be Null( A)={x∈Rn|Ax=0}. It is a simple consequence of the linearity of matrix multiplication that Null( A) is a linear subspace of Rn. That is to say, Null( A) is closed under vector addition and scalar multiplication. In fact, A(x+y)=Ax+Ay= 0+0=0 , i f x, y∈Null( A). Also, A(αx)=αAx=0 ,i f x∈Null( A). We state this formally as 50 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Theorem 2.3.1. LetA∈Mm,n(F).T h e n N u l l (A)is a subspace of Rn w h i l et h er a n g eo f Ais in Rm. Having such solutions gives valuable information about the solution set of the linear system Ax=b. For, if we have found asolution, x, and have any vector z∈Null( A), then x+zis a solution of the same linear system. Indeed, what is easy to see is that if uandvare both solutions to Ax=b, then A(u−v)=Au−Av= 0, or what is the same x−y∈Null( A). This means that to ﬁndallsolutions to Ax=b, we need only ﬁnd a single solution and the null space. We summarize this as the following theorem. Theorem 2.3.2. LetA∈Mm,n(F)with null space Null (A).L e t xbe any nonzero solution to Ax=b. Then the set x+Null(A)is the entire solution set to Ax=b. Example 2.3.1. Find the null space of A=}13 −3−9] . Solution. Solve Ax=0.The RREF for Ais}13 00] .S o l v i n g x1+3x2=0, take x2=t, a “free” parameter and solve for x1to get x1=−3t.Thus every solution to Ax= 0 can be written in the form x=}−3t t] =t}−3 1] t∈R Expressed this way we see that Null( A)=F t}−3 1] |t∈Rk ,a subspace ofR2of dimension 1. Theorem 2.3.3 (Fundamental theorem on rank). A∈Mm,n(F).T h e following are equivalent (a)r(A)=k. (b) There exist exactly klinearly independent columns of A. (c) There exist exactly klinearly independent rows of A. (d) The dimension of the column space of Aisk(i.e. dim( Range A)=k). (e) There exists a set Sof exactly kvectors in Rmfor which Ax=bhas a solution for each b∈S(S). (f) The null space of Ahas dimension n−k. 2.3. RANK 51 Proof. The equivalence of (a), (b), (c) and (d) follow from previous con- siderations. To establish (e), let S={cf1,cf2,... ,c fk}denote the linearly independent column vectors of A.L e t T={ef1,ef2,... ,e fk}⊂Rnbe the standard vectors. Then Aefj=cfj.I fb∈S(S), then b=a1cf1+a2cf2+ ···+akcfk.As o l u t i o nt o Ax=bis given by x=a1ef1+a2ef2+···+akefk. Conversely, if (e) holds, then the set Smust be linearly independent for otherwise Scould be reduced to k−1 or fewer vectors. Similarly if Ahas k+ 1 linearly independent columns then set Scan be expanded. Therefore, the column space of Amust have exactly kvectors. To prove (f) we assume that S={v1,... ,v k}is a basis for the column space of A.L e t T={w1,... ,w k}⊂Rnfor which Awi=vi,i=1,... ,k . By our extension theorem, we select n−kvectors wk+1,... ,w nsuch that U={w1,... ,w k,wk+1,... ,w n}is a basis of Rn. We must have that Awk+1∈S(S). Hence there are scalars b1,... ,b ksuch that Awk+1=A(b1w1+···+bkwk) and thus wI k+1=wk+1−(b1w1+···+bkwk)i si nt h en u l ls p a c eo f A. Repeat this process for each wk+j,j=1,... ,n−k. We generate a total ofn−kvectors {wI k+1,... ,wI n}in this manner. This set must be linearly independent. (Why?) Therefore, the dimension of the null space must beat least n−k. Now we consider a new basis which consists of the original vectors and the n−kvectors {w I k+1,wI k+2,... ,wI n}for which Aw=0 . W e assert that the dimension of the null space is exactly n−k.F o ri f z∈Rnis av e c t o rf o rw h i c h Az=0 ,t h e n zcan be uniquely written as a component z1fromS(T) and a component z2fromS({wI k+1,... ,wI n}). But Az1W=0 andAz2= 0. Therefore Az= 0 is impossible unless the component z1=0 . Conversely, if (f) holds we take a basis for the null space T={u1,u2,... ,u n−k} a n de x t e n dt h eb a s i s TI=T∪{un−k+1,. . . ,u n} toRn.N e x ta r g u es i m i l a r l yt oa b o v et h a t Aun−k+1,A u n−k+2,... ,A u n must be linearly independent, for otherwise there is yet another linearly independent vector that can be added to its basis, a contradiction. Thereforethe column space must have dimension at least, and hence equal to k. The following corollary assembles many consequences of this theorem. 52 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Corollary 2.3.1. (1)r(A)≤min(m, n). (2)r(AB)≤min(r(A),r(B)). (3)r(A+B)≤r(A)+r(B). (4)r(A)=r(AT)=r(A∗)=r(¯A). (5) If A∈Mm(F)andB∈Mm,n(F),a n di f Ais invertible, then r(AB)=r(B). Similarly, if C∈Mn(F)is invertible and B∈Mm,n(F) r(BC)=r(B). (6)r(A)=r(ATA)=r(A∗A). (7) Let A∈Mm,n(F),w i t h r(A)=k.T h e n A=XBY where X∈Mm,k, Y∈Mk,nandB∈Mkis invertible. (8) In particular, every rank 1 matrix has the form A=xyT,w h e r e x∈ Rmandy∈Rn.H e r e xyT= x1y1x1y2... x 1yn ......... xmy1xmy2... x myn . Proof. (1) The rank of any matrix is the number of linearly independent rows, which is the same as the number of linearly independent columns. The maximum this value can be is therefore the maximum of theminimum of the dimensions of the matrix, or r(A)≤min ( m, n). (2) The product ABc a nb ev i e w e di nt w ow a y s . T h e ﬁr s ti sa sas e t of linear combinations of the rows of B,and the other is as a set of linear combinations of the columns of A.In either case the number of linear independent rows (or columns as the case may be) In otherwords, the rank of the product ABcannot be greater than the number of linearly independent columns of Anor greater than the number of linearly independent rows of B.Another way to express this is as r(AB)≤min(r(A),r(B)) 2.3. RANK 53 (3) Now let S={v1,...v r(A)}andT={w1,...,w r(B)}be basis of the column spaces of AandBrespectively. Then, the dimension of the union S∪T={v1,...v r(A),w1,...,w r(B)}cannot exceed r(A)+r(B). Also, every vector in the column space of A+Bis clearly in the span ofS∪T.The result follows. (4) The rank of Ais the number of linearly independent rows (and columns) ofA,which in turn is the number of linearly independent columns of AT,which in turn is the rank of AT.That is, r(A)=rD ATi .Similar proofs hold for A∗and ¯A. (5) Now suppose that A∈Mm(F) is invertible and B∈Mm,n.As we have emphasized many times the rows of the product ABcan be viewed as a set of linear combinations of the rows of B.Since Ahas rank m any set of linearly independent rows of Bremains linearly independent. To see why, let ri(AB)d e n o t et h e ithrow of the product AB. Then it is easy to see that ri(AB)=m3 j=1aijrj(B) Suppose we can determine constants c1,...,c mnot all zero so that 0=m3 j=1ciri(AB)=m3 i=1cim3 j=1aijrj(B) =m3 j=1rj(B)m3 i=1ciaij This linear combination of the rows of Bhas coeﬃcient given by ATc, where c=[c1,...,c k]T.Because the rank of A(and AT)i sm,we can solve this system for any vector d∈Rm.Suppose that the row vectors rjl(B),f=1,...,r (B),are linearly independent. Arrange that the components of dto be zero for indices not included in the set jl,f=1,...,r (B) and not all zero otherwise. Then the conclusion 0=m j=1rj(B)m i=1ciaij=r(B) l=1rjl(B)djlis impossible. Indeed, the same basis of the row space of Bwill be a basis of the row space ofAB.T h i sp r o v e st h er e s u l t . (6) We postpone the proof of this result until we discuss orthogonality. 54 CHAPTER 2. MATRICES AND LINEAR ALGEBRA (7) Place Ain RREF, say ARREF .S i n c e r(A)=kwe know the top k rows of ARREF are linearly independent and the remaining rows are zero. De ﬁneYto be the k×nmatrix consisting of these top krows. DeﬁneB=Ik.Now the rows of Aare linear combinations of these rows. So, de ﬁne the m×kmatrix Xto have rows as follows: The ﬁrst row of consists of the coe ﬃcients so thatx1jrj(Y)=r1(A). In general, the ithrow of Xis selected so that 3 xijrj(Y)=ri(A) (8) This is an application of (7) noting in this special case that Xis an m×1 matrix that can be interpretted as a vector x∈Rm. Similarly, Yis an 1 ×nmatrix that can be interpretted as a vector y∈Rn. Thus, with I=[ 1 ] ,w eh a v e A=xyT Example 2.3.2. Here is the decomposition of the form given in Lemma 2.3.1 (7). The 3 ×4m a t r i x Ahas rank 2. A= 12 −1 002 −1−23 240 = 1−1 02 −13 20 }10 01]}120 001] =XBY The matrix Yis the RREF of A. Example 2.3.3. Letx=[x1,x2,...,x m]T∈Rmandy=[y1,y2,...y n]T∈ Rn. Then the rank one m×nmatrix xyThas the form xyT= x 1y1x1y2··· x1yn x2y1x2y2 x2yn ......... xmy1xmy2···xmyn  In particular, with x=[ 1,3,5]T,a n d y=[−2,7]T,the rank one 3 ×2m a t r i x xyTis given by xyT= 1 35 [−2,7] = −27 −62 1 −10 35  2.3. RANK 55 Invertible Matrices A subclass matrices A∈Mn(F) that have only the zero kernel is very important in applications and theoretical developments. Deﬁnition 2.3.4. A∈Mnis called nonsingular ifAx= 0 implies that x=0 . In many texts such matrices are introduced though an equivalent alter- nate de ﬁnition involving rank. Deﬁnition 2.3.5. A∈Mnisnonsingular ifr(A)=n. We also say that nonsingular matrices have fullrank. That nonsingular matrices are invertible and conversely together with many other equivalencesis the content of the next theorem. Theorem 2.3.4. [Fundamental theorem on inverses] Let A∈M n(F).T h e n the following statements are equivalent. (a)Ais nonsingular. (b)Ais invertible. (c)r(A)=n. (d) The rows and columns of Aare linearly independent. (e)dim(Range( A)) =n. (f)dim(Null( A)) = 0 . (g)Ax=bis consistent for all b∈Rn(orCn). (h)Ax=bhas a unique solution for every x∈Rn(orCn). (i)Ax=0 has only the zero solution. (j)* 0 is not an eigenvalue of A. (k)* detAW=0. * The statements about eigenvalues and the determinant (det A)o fam a - trix will be clari ﬁed later after they have been properly de ﬁned. They are included now for completeness. 56 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Deﬁnition 2.3.6. Two linear systems Ax=bandBx=care called equiv- alent if one can be converted to the other by elementary equation opera- tions. Equivalently, the systems are equivalent if [ A|b] can be converted to [B|c] by elementary row operations. Alternatively, the systems are equivalent if they have the same solution set which means of course that both can be reduced to the same RREF. Theorem 2.3.5. IfA∈Mn(F)andB∈Mn(F)with AB=I,t h e n Bis unique. Proof. IfAB=Ithen for every e1...e nthere is a solution to the system Abi=eifor all 1 = 1 ,2,... ,n .T h u st h es e t {bi}n i=1is linearly independent (because the set {ei}is) and moreover a basis. Similarly if AC=Ithen A(C−B) = 0, and there are ci∈Rn(orCn),i=1, ..., n such that Aci=ei. Suppose for example that c1−b1W=0 . S i n c et h e {bi}n i=1is a basis it follows that c1−b1=Σαjbj, where not all αjare zero. Therefore, A(c1−b1)=ΣαjAbj=ΣαjejW=0. and this is a contradiction. Theorem 2.3.6. LetA∈Mn(F).I fBis a right inverse, AB=I,t h e n B is a left inverse. Proof. DeﬁneC=BA−I+B,a n da s s u m e CW=Bor what is the same thing that Bis not a left inverse. Then AC=ABA−A+AB=(AB)(A)−A+AB =A−A+AB=I This implies that Cis another right inverse of A, contradicting Theorem 2.3.5. 2.4 Orthogonality Let V be a vector space over C.W ed e ﬁne an inner product ·,·XonV×V to be a function from VtoCthat satis ﬁes the following properties: 1.av, wX=av,wXandv,awX=av,wX(ais the complex conjugate ofa) 2.v,wX=w,vX 2.4. ORTHOGONALITY 57 3.u+v,wX=u, wX+v,wX(linearity) 4.u, v+wX=u, vX+u, wX 5.v,vX≥ 0w i t hv,vX=0i fa n do n l yi f v=0. For inner products over real vector spaces, we neglect the complex con- jugate operation. In addition, we want our inner products to de ﬁne anorm as follows: 6. For any v∈V,,v,2=v,vX We assume thoughout the text that all vector spaces with inner products have norms de ﬁned exactly in this way. With the norm and vector vcan benormalized by dilating it to have length 1, say vn=v1 ,v,. The simplest type of inner product on Cnis given by v,wX=n3 i=1xi¯yi We call this the standard inner product. Using any inner product, we can de ﬁne an angle between vectors. Deﬁnition 2.4.1. Theangleθxybetween vectors xandyinRnis deﬁned by cosθxy=x, yX ,x,,y, =x, yX (x, xX)1/2(y,yX)1/2. This comes from the well known result in R2 x·y=,x,,y,cosθ which can be proved using the law of cosines. With angle comes the notion of orthogonality. Deﬁnition 2.4.2. Two vectors uandvare said to be orthogonal if the angle between them ifπ 2or what is the same thing u, vX=0 . I nt h i sc a s e we commonly write x⊥y. W ee x t e n dt h i sn o t a t i o nt os e t s Uwriting x⊥U to mean that x⊥ufor every u∈U. Similarly two sets UandVare called orthogonal if u⊥vfor every u∈Uandv∈V. 58 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Remark 2.4.1. It is important to note that the notion of orthogonality depends completely on the inner product. For example, the weighted inner product deﬁned byv,wX=n i=1wixi¯yiwhere the wi>0g i v e sv e r yd i ﬀerent orthogonal vectors from the standard inner product. Example 2.4.1. InRnorCnthe standard unit vectors are orthogonal with respect to the standard inner product. Example 2.4.2. In the R3the vectors u=( 1,2,−1) and v=( 1,1,3) are orthogonal because x, yX=1( 1 )+2( 2 ) −1( 3 )=0 Note that in R3the complex conjugate is not written. The set of vectors (x1,x2,x3)∈R3orthogonal to u=( 1,2,−1) satis ﬁes the equation x1+ 2x2−x3= 0 is recognizable as the plane with normal vector u. Deﬁnition 2.4.3. We de ﬁne the projection Puvof one vector vin the di- rection of an other vector uto be Puv=u, vX ,u,2u A sy o uc a ns e e ,w eh a v em e r e l yw r i t t e na ne x p r e s s i o nf o rt h em o r ei n - tuitive version of the projection in question given by ,v,cosθuvu ,u,.I n t h e ﬁgure below, we show the fundamental diagram for the projection of one vector in the direction of another. /c113uv Pvu If the vectors uandvare orthogonal, it is easy to see that Puv=0. (Why?) Example 2.4.3. Find the projection of the vector v=( 1,2,1) on the vector u=(−2,1,3) 2.4. ORTHOGONALITY 59 Solution. We have Puv=u, vX ,u,2u=(1,2,1),(−2,1,3)X ,(−2,1,3),2(−2,1,3) =1(−2) + 2 (1) + 1 (3) 14(−2,1,3) =5 14(−2,1,3) We are now ready to ﬁndorthogonal sets of vectors and orthogonal bases. First we make an important de ﬁnition. Deﬁnition 2.4.4. LetVbe a vector space with an inner product. A set of vectors S={x1,... ,x n}inVis said to be orthogonal ifxi,xjX=0f o r iW=j.I ti sc a l l e d orthonormal if alsoxi,xiX= 1. If, in addition, Sis a basis it is called an orthogonal basis or orthonomal basis. Note: Sometimes the conditions for orthonormality are written as xi,xjX=δij whereδijis the “Dirac” delta: δij=0 ,iW=j,δii=1 . Theorem 2.4.1. Suppose Uis a subspace of the (inner product) vector space Vand that Uhas the basis S={x1...x k},t h e n Uhas an orthogonal basis. Proof. Deﬁney1=x1 ,|x,|.T h u s y1is the “normalized” x1.N o w d e ﬁne the new orthonormal basis recursively by yI j+1=xj+1−j3 i=1yi,xj+1Xyi yj+1=yI j+1 ,yI j+1, forj=1,2,...,k−1. Then (1)yj+1is orthogonal to y1,. . .,y j (2)yj+1W=0 . In the language above we have yi,yjX=δij. 60 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Basically, what the proof accomplishes is to take the di ﬀerences of the vector from the projections to the others. Referring to the ﬁgure above we compute v−Puva sn o t e di nt h e ﬁgure below. The process of orthogonal- ization described above is called the Gram—Schmidt process. /c113uv v PvPv uu- Representation of vectors One of the great advantages of orthonormal bases is that they make the representation of vectors particularl y easy. It is as simple as computing an inner product. Let Vbe a vector space with inner product ·,·Xand with subspace Uhaving basis S={u1,u2,...,u k}. Then for every u∈Uwe know there are constants a1,a2,...,a ksuch that x=a1u1+a2u2+···+akuk. Taking the inner product of both sides with ujand applying the orthogo- nality relations x, u jX=a1u1+a2u2+···+akuk.,ujX =k3 j=1aiui.,ujX=aj Thus aj=x, u jX,j=1,2, ..., k ,a n d x=k3 j=1u.,ujXuj Example 2.4.4. One basis of R2is given by the orthonormal vectors S= {u1,u2},w h e r e u1= 1√ 2,1√ 2=T and u2= 1√ 2,−1√ 2=T . The representa- tion of x=[ 3,2]Tis given by x=23 j=1u.,ujXuj=5 2√ 2}1√ 2,1√ 2]T +1 2√ 2}1√ 2,−1√ 2]T 2.4. ORTHOGONALITY 61 Orthogonal subspaces Deﬁnition 2.4.5. For any set of vectors Swe de ﬁne S⊥={v∈V|v⊥S} That is, S⊥is the set of vectors orthogonal to S.O f t e n , S⊥is called the orthogonal complement ororthocomplement ofS. For example the orthocomplement of any vector v=[v1,v2,v3]T∈R3is the (unique) plane passing through the origin that is orthogonal to v.I ti se a s y to see that the equation of the plane is x1v1+x2v2+x3v3=0 . For any set of vectors Sthe orthocomplement S⊥has the remarkable property of being a subspace of V, and therefore it is must have an orthog- onal basis. Proposition 2.4.1. Suppose that Vis a vector space with an inner product, andS⊂V.T h e n S⊥is a subspace of V. Proof. Ify1,. . .,y m∈S⊥thenΣaiyi∈S⊥for every set of coe ﬃcients a1,. . .,a minR(orC). Corollary 2.4.1. Suppose that Vi sav e c t o rs p a c ew i t ha ni n n e rp r o d u c t , andS⊂V. (i) If Sis a basis of V,S⊥={0}. (ii) If U=S(S),t h e n U⊥=S⊥. The proofs of these facts are elementary consequences of the proposition. An important decomposition result is based on orthogonality of subspaces.For example, suppose that Vis aﬁnite dimensional inner product space and that Uis a subspace of V.L e t U ⊥be the orthocomplement of U,and let S={u1,u2,...,u k}be an orthonormal basis of U.L e t x∈V.D e ﬁne x1=k j=1x, u jXuj,a n d x2=x−x1. Then it follows that x1∈Uand x2∈U⊥.M o r e o v e r , x=x1+x2. We summarize this in the following. Proposition 2.4.2. LetVis a vector space with inner product ·,·Xand with subspace U. Then every vector x∈Vc a nb ew r i t t e na sas u mo ft w o orthogonal vectors x=x1+x2,w h e r e x1∈Uandx2∈U⊥. 62 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Geometrically what this results asserts is that for a given subspace of an inner product space, every vector has an orthogonal decomposition astwo unique sum of a vector from the subspace and its orthocomplement.We write the vector components as the respective projections of the givenvector to the orthogonal subspaces x 1=PUx x2=PU⊥x Such decompositions are important in the analysis of vector spaces and matrices. In the case of vector spaces, of course, the representation ofvectors is of great value. In the case of matrices, this type of decompositionserves to allow reductions of the matrices while preserving the informationthey carry. 2.4.1 An important equality for matrix multiplication and the inner product LetA∈Mmn(C). Then we know that both A∗AandAA∗(Alternatively, ATAandAATexist) exist, and we can surely inquire about the rank of these matrices. The main result of this section is on the rank of ATA,n a m e l y that r(A)=r(A∗A)=r(AA∗). The proof is quite simple but requires an important equality. Let A∈Mmn(C)a n d v∈Cnandw∈Cm.Then Av, wX=rm3 i=1(Av)i,wiS =m3 i=1n3 j=1aijvj¯wi =n3 j=1vjm3 i=1aij¯wi =n3 j=1vjm3 i=1¯aijwi =n3 j=1vj(A∗w)j =v,A∗wX 2.4. ORTHOGONALITY 63 As a consequence we have A∗Av, wX=Av, AwXif both v, w∈Cn.T h i s important equality allows the adjoint or transpose matrices to be used oneither side of the inner product, as needed. Indeed we shall use this below. Proposition 2.4.3. LetA∈M mn(C)have rank r(A).Then r(A)=r(A∗A)=r(AA∗) Proof. Assume that r(A)=k.Then there are kstandard vectors ej1,..., e jk such that for each l=1,2,...k, the vectors Aejlis one of the linearly independent columns of A.Moreover, it also follows that for every set of constants a1,...,a kthe vector ADalelji W=0.Now A∗ADalelji W=0 follows because ? A∗Ap3 aleljQ ,p3 aleljQ# =? Ap3 aleljQ ,Ap3 aleljQ# =EEEAp3 a leljQEEE2 W=0 This in turn establishes that A∗Acannot be zero on a linear space of di- mension kexcept for the zero element of course, and since the rank of A∗A cannot be larger than kthe result is proved. Remark 2.4.2. This establishes (6) of the Corollary 2.3.1 above. Also, it is easy to see that the result is also true for real matrices. 2.4.2 The Legendre Polynomials When a vector space has an inner product, it is possible to construct anorthogonal basis from any given basis. We do this now for the polynomial space P n(−1,1) and a particular basis. Consider the space the polynomials of degree ndeﬁn e do nt h ei n t e r v a l [−1,1] over the reals .Recall that this is a vector space and has as a basis themonomials\ 1,x ,x2,...,xn .We can de ﬁne an assortment of inner products on this space, but the most common inner product is given by p, qX=81 −1p(x)q(x)dx Verifying the inner product properties is fairly straight forward and we leave it as an exercise. This inner product also de ﬁnes a norm ,p,2=81 −1|p(x)|2dx 64 CHAPTER 2. MATRICES AND LINEAR ALGEBRA This norm satis ﬁes the triangle inequality requires an integral version of the Cauchy-Schwartz inequality. Now that we have an inner product and norm, we could proceed to ﬁnd an othogonal basis of Pn(−1,1) by applying the Gram-Schmidt procedure to the basis\ 1,x ,x2,...,xn . This procedure can be clumsy and tedious. It is easier to build an orthogonal basis from scratch. Following traditionwe will use capital letters P 0,P1,... to denote our orthogonal polynomials. Toward this end take P0= 1. Note we are numbering from 0 onwards so that the polynomial degree will agree with the index. Now let P1=ax+b. For orthogonality, we need 81 −1P0(x)P1(x)dx=81 −11·(ax+b)dx=2b=0 Thus b=0a n d acan be arbitrary. We take a=1.This gives y1=x.Now we assume the model for the next orthogonal function to be y2=ax2+bx+c. This time there are two orthogonality conditions to satisfy. 81 −1P0(x)P2(x)dx=81 −11·D ax2+bx+ci dx=2 3a+2c=0 81 −1P1(x)P2(x)dx=81 −1x·D ax2+bx+ci dx=2 3b=0 We conclude that b=0.From the equation2 3a+2c= 0, we can assign one of the variables and solve for the other one. Following tradition we takec=− 1 2and solve for ato get a=3 2. The next polynomial will be modeled as P3(x)=ax3+bx2+cx+d. Three orthogonality relations need to be satis ﬁed. 81 −1P0(x)P3(x)dx=81 −11·D ax3+bx2+cx+di dx=2 3b+2d=0 81 −1P1(x)P3(x)dx=81 −1x·D ax3+bx2+cx+di dx=2 5a+2 3c=0 81 −1P2(x)P3(x)dx=81 −11 2(3x−1)D ax3+bx2+cx+di dx =3 5a−1 3b+c−d=0 It is easy to see that b=d=0( w h y ? ) a n df r o m2 5a+2 3c=0,we select 2.4. ORTHOGONALITY 65 c=−3 2anda=5 2.Our table of orthogonal polynomials so far is k Pk(x) 0 1 1 x 21 2(3x−1) 31 2D 5x3−3xi Continue in this fashion, generating polynomials of increasing order each orthogonal to all of the lower order ones. P0(x)=1 P1(x)= x P2(x)=3 /2x2−1/2 P3,x)=5 /2x3−3/2x P4(x)=35 8x4−15 4x2+3/8 P5(x)=63 8x5−35 4x3+15 8x P6(x)=231 16x6−315 16x4+105 16x2−5 16 P7(x)=429 16x7−693 16x5+315 16x3−35 16x P8(x)=6435 128x8−3003 32x6+3465 64x4−315 32x2+35 128 P9(x)=12155 128x9−6435 32x7+9009 64x5−1155 32x3+315 128x P10(x)=46189 256x10−109395 256x8+45045 128x6−15015 128x4+3465 256x2−63 256 2.4.3 Orthogonal matrices Besides sets of vectors being orthogonal, there is also a de ﬁnition of orthog- onal matrices. The two notions are closely linked. Deﬁnition 2.4.6. We say a matrix A∈Mn(C)i sorthogonal ifA∗A=I. The same de ﬁnition applies to matrices A∈Mn(R)w i t h A∗replaced by AT. 66 CHAPTER 2. MATRICES AND LINEAR ALGEBRA For example, the rotation matrices (Exercise ??)Bθ=}cosθ−sinθ sinθcosθ] are all orthogonal. A simple consequence of this de ﬁnition is that the rows and the columns ofAareorthonormal . We see for example that when Ais orthogonal then (A∗)2=(A−1)2=A−1A−1=(A2)−1. Such a de ﬁnition applies, as well to higher powers. For instance, if Ais orthogonal then Amis orthogonal for every positive integer m. One way to generate orthogonal matrices in Cn(orRn)i st ob e g i nw i t h an orthonormal basis and arrange it into an n×nmatrix either as its columns or rows. Theorem 2.4.2. (i) Let {xi},i=1,...,n be an orthonormal basis of Cn or(Rn). Then the matrices U= x1···xn ↓···↓ ··  and V= x1−→ · ...... xn−→ ·  formed by arranging the vectors xias its respective columns or rows are orthogonal. (ii) Conversely, Uis an orthogonal matrix, the sets of its rows and columns are each orthonormal, an d moreover each forms a basis of Cnor (Rn). The proofs are entirely trivial. We shall consider these types of results in more detail later in Chapter 4. In the meantime there are a few moreinteresting results that are direct consequences of the de ﬁnition and facts about the transpose (adjoint). Theorem 2.4.3. LetA, B∈M n(C)(orMn(R))be orthogonal matrices. Then(a)Ais invertible and A −1=A∗. (b) For each integer k=0,±1,±2,...,b o t h Akand−Akare orthogonal. (c)AB is orthogonal. 2.5 Determinants This section is about determinants that can be regarded as a measure of singularity of a matrix. More generally, in many applied situations that deal with complex objects, a single number is sought that will in some way 2.5. DETERMINANTS 67 classify an aspect of those objects. The determinant is such a measure for singularity of the matrix. The determinant is di ﬃcult to calculate and of not much practical use. However, it has considerable theoretical value andcertainly has a place of historical interest. Deﬁnition 2.5.1. LetA∈M n(F). De ﬁne the determinant ofAto be the value in F detA=3 σXn i=1aiσ(i)~ ·sgnσ whereσis a permutation of the integers {1,2,... ,n }and (1) σdenotes the sum over all permutations (2) sgnσ=s i g no f σ=±1 Atransposition is the exchange of two elements of an ordered list with all others staying the same. With respect to permutations, a transposition of one permutation is another permutation formed by the exchange of twovalues. For example a transposition of {1,4,3,2}is{1,3,4,2}.T h e sign of a given permutation σis (a) +1 ,if the number of transpositions required to bring σto{1,2,... ,n } is even. (b)−1,if the number of transpositions required to bring σto{1,2,... ,n } is odd. Alternatively, and what is the same thing, we may count the number mof transpositions required to bring σto{1,2,... ,n }and to compute the sign is (−1) m. Example 2.5.1. σ1={2,1,3}1↔2−−→ {1,2,3} odd σ2={2,3,1}3↔1−−→ {2,1,3}1↔2−−→ {1,2,3}even sgnσ1=−1s g n σ2=+ 1 Proposition 2.5.1. LetA∈Mn. 68 CHAPTER 2. MATRICES AND LINEAR ALGEBRA (i) If two rows of Aare interchanged to obtain B,t h e n detB=−detA. (ii) Given A∈Mn(F). If any row is multiplied by a scalar c,t h er e s u l t i n g matrix Bhas determinant detB=cdetA. (iii) If any two rows of A∈Mn(F)are equal, detA=0. Proof. (i) Suppose rows i1andi2are interchanged. Now for the given permutations σapply the transposition i1↔i2to getσ1.T h e n n i=1ai1σ(i)=n i=1bi2σ1(i) because ai1σ(i1)=bi2σ1(i2) as bi2j=ai1jandσ1(i2)=σ2(i1) and similarly ai2σ(i2)=bi1σ1(i1). All other terms are equal. In the computation of the full determinant with signs of the permutations, we see that the change is caused only by the fact sgn( σ1)=−sgn(σ). Thus, detB=−detA. (ii) Is trivial. (iii) If two rows are equal then by part (i) detA=−detA and this implies det A=0 . 2.5. DETERMINANTS 69 Corollary 2.5.1. LetA∈Mn.I fAhas two rows equal up to a multiplica- tive constant, it has has determinant zero. What happens to the determinant when two matrices are added. The result is too complicated to write down is not very important. However,when a single vector is added to a row or a column of a matrix, then theresult can be simply stated. Proposition 2.5.2. Suppose A∈M n(F).S u p p o s e Bis obtained from A by adding a vector vto a given row (resp. column) and Cis obtained from Aby replacing the given row (resp. column) by the vector v.T h e n detB=d e t A+d e t C. Proof. Assume the jthrow is altered. Using the de ﬁnition of the determi- nant, detA=3 σsgn(σ) ibiσ(i)=3 σsgn(σ)  iW=jbiσ(i) bjσ(j) =3 σsgn(σ)  iW=jaiσ(i) (a+v)jσ(j) =3 σsgn(σ)  iW=jaiσ(i) ajσ(j)+3 σsgn(σ)  iW=jaiσ(i) vjσ(j) detA+d e t C For column replacement the proof is similar, particularly using the alternate representation of the determinant given in Exercise 15. Corollary 2.5.2. Suppose A∈Mn(F)andBis obtained by multiplying a given row (resp. column) of Aby a scalar and adding it to another row (resp. column), then detB=d e t A. Proof. First note that in applying Proposition 2.5.2 Chas two rows equal up to a multiplicative constant. Thus det C=0 . Computing determinants is usually di ﬃcult and many techniques have been devised to compute them out. As is evident from counting, computing 70 CHAPTER 2. MATRICES AND LINEAR ALGEBRA the determinant of an n×nmatrix using the de ﬁnition above would require the expression of all n! permutations of the integers {1,2,..., n }and the determination of their signs together with all the concommitant productsand summation. This method is prohibitively costly. Using elementaryrow operations and Gaussian elimination, the evaluation of the determinant becomes more manageable. First we need the result below. Theorem 2.5.1. For the elementary matrices the following results hold. (a) for Type 1 (row interchange) E 1 detE1=−1 (b) for Type 2 (multiply a row by a constant c)E2 detE2=c (c) for Type 3 (add a multiple of one row to another row) E3 detE3=1. Note that (c) is a consequence of Corollary 2.5.2. Proof of parts (a) and (b) are left as exercises. Thus for any matrix A∈Mn(F)w eh a v e det(E1A)=−detA=d e t E1detA det(E2A)=cdetA =d e t E2detA det(E3A)=d e t A =d e t E3detA. Suppose F1...F kis a sequence of row operations to reduce Ato its RREF. Then FkFk−1...F 1A=B. Now we see that detB=d e t ( FkFk−1...F 1A) =d e t ( Fk)d e t ( Fk−1...F 1A) =... =d e t ( Fk)d e t ( Fk−1)...det(F1)d e tA. ForBin RREF andB∈Mn(F), we have that Bis upper triangular. The next result establishes Theorem 2.3.4( k) about the determinant of singular and non singular matrices. Moreover, the determinant of triangular matrices is computed simply as the product of its diagonal elements. 2.5. DETERMINANTS 71 Proposition 2.5.3. LetA∈Mn.T h e n (i) If r(A)<n,t h e n detA=0. (ii) If Ais triangular then detA= aii (iii) If r(A)=n,t h e n detAW=0. Proof. (i) If r(A)<n, then its RREF has a row of zeros, and det A=0b y Theorem 2.5.1. (ii) If Ais triangular the only product without possible zero entries isaii.H e n c e d e t A=aii. (iii) If If r(A)=n, then its RREF has no nonzero rows. Since it is square and has a leading one in each column, it follows that the RREF is the identity matrix. Therefore det AW=0 . Now let A, B∈Mn.I fAis singular the RREF must have a zero row. It follows that det A=0 . I f Ais singular it follows that ABis singular. Therefore 0=d e t AB=d e t AdetB. The same reasoning applies if Bis singular. If AandBare not singular both AandBcan be row reduced to the identity. Let F1...F k1be the row operations that reduce AtoI,a n d G1...G kBbe the row operations that reduce BtoI.T h e n detA=[ d e t ( F1)...det(FkA)]−1 detB=[ d e t ( G1)...det(GkB)]−1. Also I=(GkB...G 1)(FkB...F 1)AB and we have detI=( d e t A)−1(detB)−1detAB. This proves the Theorem 2.5.2. IfA, B∈Mn(F),detAB=d e t AdetB. 72 CHAPTER 2. MATRICES AND LINEAR ALGEBRA 2.5.1 Minors and Determinants The method of row reduction is one of the simplest methods to compute the determinant of a matrix. Indeed, it is not necessary to use Type 2 el- ementary transformation. This results in the computing the determinantas the product of the diagonal elements of the resulting triangular matrixpossibly multiplied by a minus sign. An alternate approach to computingdeterminants using minors is both interesting and useful. However, unless the matrix has some special form, it does not provide a computational al- ternative to row reduction. Deﬁnition 2.5.2. LetA∈M n(C).For any row iand column jdeﬁne the (ij)-minor ofAby Mij=d e t A ithrow removed jthcolumn removed The notation A ithrow removed jthcolumn removed denotes the ( n−1)×(n−1) matrix formed from Aby removing the ithrow andjthcolumn. With minors an alternative formulation of the determinant can be given. This method, while not of great value computationally, hassome theoretical importance. For example, the inverse of a matrix can beexpressed using minors. We begin by consideration the determinant. Theorem 2.5.3. LetA∈M n(C).(i) Fix any row, say row k.The de- terminant of Ais given by detA=n3 j=1akj(−1)k+jMkj (ii) Fix any column, say column m. The determinant of Ais given by detA=n3 j=1ajm(−1)m+jMjm Proof. (i) Suppose that k=1.Consider the quantity a11M11 2.5. DETERMINANTS 73 We observe that this is equivalent to all the products of the form sgn(σ)a11·a2σ(2)····· anσ(n) where only permutations that ﬁx the integer (i.e. position) 1 are taken. Thusσ(1) = 1 .Since this position is ﬁxed the signs taken in the determi- nant M11for permutations of n−1 integers are respectively the same as the signs for the new permutation of nintegers. Now consider all permutations that ﬁx the integer 2 in the sense that σ(1) = 2. The quantity a12(−1)1+2M12consists of all the products of the form sgn(σ)a12·a2σ(1)a3σ(3)····· anσ(n) We need here the extra sign change because if the part of the permutation σof the integers {1,3,4,...,n }is of one sign, which is the sign used in the computation of det Mij, then the permutation of σof the integers {1,2,3,4,...,n }is of the other sign, and that sign is sgn(σ). When we proceed to the kthcomponent, we consider permutations that ﬁxt h ei n t e g e r k.T h a t i s , σ(1) = k. In this case the quantity a1k(−1)1+kM1k consists of all products of the form sgn(σ)a1ka2σ(1)····ak−1σ(k−1)ak+1σ(k+1)····· anσ(n) Continuing in this way we exhaust all possible products a1σ(1)·a2σ(2)····· anσ(n)over all possible permutations of the integers {1,2,...,n }.T h i s proves the assertion. The proof for expanding from any row is similar, with only a possible change of sign needed, which is a prescribed. (ii) The proof is similar. Example 2.5.2. Find the determinant of A= 32−1 01 3 12−1  expanding across the ﬁrst row and then expanding down the second column. Solution. Expanding across the ﬁrst row gives detA=a11M11−a12M12+a13M12 =3 d e t}13 2−1] −2d e t}03 1−1] −1d e t}01 12] =3 (−7)−2(−3)−(−1) =−14 74 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Expanding across the second column gives detA=−2d e t}03 1−1] +1d e t}3−1 1−1] −2d e t}3−1 03] =−2(−3) + (−2)−2( 9 )=−14 The inverse of the matrix can be formulated in terms of minors, which is formulated below. Deﬁnition 2.5.3. LetA∈Mn(C)( o r Mn(R)). De ﬁne the adjugate (or adjoint )m a t r i x ˆAby ˆAij=(−1)i+jMji where Mjiis the jiminor. The adjugate has traditionally been call ed the “adjoint”, but that terminol- ogy is somewhat ambiguous in light of the previous de ﬁnition as complex conjugate transpose. Note that it is de ﬁned for all square matrices; when restricted to invertible matrices the inverse appears. Theorem 2.5.4. LetA∈Mn(C)(orMn(R)) be invertible. Then A−1= 1 detAˆA Proof. A quick examination of the ij-entry of the product AˆAyields the following sum n3 j=1aijˆAjk=1 det (A)n3 j=1aij(−1)k+jMkj There are two possibilities. (1) If i=k,then the summation above is the summation to form the determinant as described in Theorem 2.5.3. (2) IfiW=k,the summation is the computation of the determinant of the matrix Awith the k throw replaced by the ithrow. Thus the determinant of a matrix with two identical rows is represented above and this must be zero. We conclude thatp AˆAQ ij=δij,the usual Kronecker ‘delta,’ and the result is proved. Example 2.5.1. Find the adjugate and inverse of A=}24 21] 2.5. DETERMINANTS 75 It is easy to see that ˆA=}1−4 −22] Also det A=−6. Therefore, the inverse A−1=−1 6}1−4 −22] Remark 2.5.1. The notation for cofactors of a square matrix Ais often used ˆaij=(−1)i+jMji Note the reversed order of the subscripts ijand then jiabove. Cramer’s Rule We know now that the solution to the system Ax=bis given by x=A−1b. Moreover, the inverse A−1is given by A−1=ˆA detA,w h e r e ˆAis the adjugate matrix. The the ithcomponent of the solution vector is therefore xi=1 detAn3 j=1ˆaijbj =1 detAn3 j=1(−1)i+jMjibj =detAi detA w h e r ew ed e ﬁne the matrix Aito be the modi ﬁcation to Aby replacing its ithcolumn by the vector b. In this way we obtain a very compact formula for the solution of a linear system. Called Cramer’s rule we state thisconclusion as Theorem 2.5.1. (Cramer’s Rule.) Let A∈M n(C)be invertible and b∈ Cn.F o re a c h i=1,, n , deﬁne the matrix Aito be the modi ﬁcation of A by replacing its ithcolumn by the vector b. Then the solution to the linear system Ax=bis given by components xi=detAi detA,i=1,, n. 76 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Example 2.5.2. Given the matrix A=}24 21] , and the vector b= }2 −1] .Solve the system Ax=bby Cramer’s rule. We have A1=}24 −11] and A2=}22 2−1] and det A1=6,detA2=−6,detA=−6. Therefore x1=−1a n d x2=1 A curious formula The useful formula using cofactors given below will have some consequence when we study positive de ﬁnite operators in Chapter ??. Proposition 2.5.1. Consider the matrix B= 0x 1x2··· xn x1a11a12···a1n x2a21a22···a2n ............... x nan1an2 ann  Then detB=−3 ˆa ijxixj where ˆaijis the ij-cofactor of A. Proof. Expand by minors along the top row to get detB=3 (−1)jxjM1j(B) Now expand the matrix of M1j(B)d o w nt h e ﬁrst column. This gives M1j(B)=3 (−1)i−1xiMij(A) 2.6. PARTITIONED MATRICES 77 Combining we obtain detB=3 (−1)jxjM1j(B) =3 (−1)jxj3 (−1)i−1xiMij(A)= =33 (−1)i+j−1xjxiMij(A) =−33 ˆaijxjxi The reader may note that in the last line of the equation above, we should have used ˆ aij. However, the formulation given is correct, as well. (Why?) 2.6 Partitioned Matrices It is convenient to study partitioned or “blocked” matrices, or more graph- ically said, matrices whose entries are themselves matrices. For example,with I 2denoting the 2 ×2i d e n t i t ym a t r i xw ec a nc r e a t et h e4 ×4m a t r i x w r i t t e ni np a r t i t i o n e df o r ma n de x p a n d e df o r m . A=}aI2cI2 cI2dI2] = a0b0 0a0b c0d0 0c0d  Partitioning matrices allows our attention to focus on certain structural properties. In many applications part ititioned matrices appear in a natural way, with the particular blocks having some system context. Many similarsubclasses and processes apply to partitioned matrices. In speci ﬁcs i t u a t i o n s they can be added, multiplied, and inverted, just like regular matrices. It iseven possible to perform “blocked” version of Gaussian elimination. In the few results here, we touch on some of these possibilities. Deﬁnition 2.6.1. For each 1 ≤i≤mand 1≤j≤n,letA ijbe an mi×nj matrices where . Then the matrix A= A 11A12··· A1n A21A2n··· A2n ............ Am1Am2···Amn  78 CHAPTER 2. MATRICES AND LINEAR ALGEBRA is a partitioned matrix of order (m)i×(nj). The usual operations of addition and multiplication of partitioned ma- trices can be performed provided each of the operations makes sense. Foraddition of two partitioned matrices AandBit is necessary to have the same numbers of blocks of the respective same sizes. Then A+B= A 11A12··· A1n A21A2n··· A2n ............ Am1Am2···Amn + B11B12··· B1n B21B2n··· B2n ............ Bm1Bm2···Bmn  = A 11+B11 A12+B12··· A1n+B1n A21+B21 A2n+B2n··· A2n+B2n ............ Am1+Bm1Am2+Bm2···Amn+Bmn  For multiplication, the situation is a bit more complicated. For de ﬁniteness, suppose that Bis a partitioned matrix with block sizes s i×tj,w h e r e1 ≤ i≤pand 1≤j≤qThe usual operations to construct C=AB, n3 j=1AijBjk then make sense provided p=nandnj=sj,1≤j≤n. A special category of partitioned matrices are the so-called quasi-triangular matrices, wherein Aij=0i f i>j for the “lower” triangular version. The special subclass of quasi-triangular matrices wherein Aij=0i f iW=jare called quasi-diagonal. In the case of the multiplication of partitioned matrices ( C=AB) with the left multiplicand Aa quasi-diagonal matrix, we have Cik=AiiBik. Thus the multiplication is similar in form to the usual multiplication of matrices where the left multiplicand is a diagonal matrix.In the case of the multiplication of partitioned matrices ( C=AB)w i t ht h e right multiplicand Ba quasi-diagonal matrix, we have C ik=AikBkk.F o r quasi-triangular matrices with square diagonal blocks, there is an interestingresult about the determinant. Theorem 2.6.1. LetAbe a quasi-triangular matrix, where the diagonal blocks A iiare square. Then detA= idetAii 2.7. LINEAR TRANSFORMATIONS 79 Proof. Apply row operations on each vertical block without row interchanges between blocks, without any Type 2 operations. The resulting matrix ineach diagonal block position ( i, i) is triangular. Be sure to multiply one of the diagonal entries by ±1,reﬂecting the number of row interchanges within a block. The resulting matrix c an still be regarded as partitioned, though the diagonal blocks are now actually upper triangular. Now apply Proposition 2.5.3, noting that the product of each of the diagonal entriespertaining to the i thblock is in fact det Aii. A simple consequence of this result, proved al´ a Gaussian elimination, is contained in the following corollary. Corollary 2.6.1. Consider the partitioned matrix A=}A11A12 A21A22] with square diagonal blocks and with A11invertible. Then the rank of Ais the same as the rank of A11if and only if A22=A21A−1 11A12. Proof. Multiplication of Aby the elementary partitioned matrix E=}I 0 −A21A−1 11I] yields EA =}I 0 −A21A−1 11I]}A11A12 A21A22] =}A11 A12 0A22−A21A−1 11A12] Since Ehas full rank, it follows that rank( EA)=r a n k A.S i n c e EAis quasi-triangular, it follows that the rank of Ai st h es a m ea st h er a n ko f A11 if and only if A22−A21A−1 11A12=0. 2.7 Linear Transformations Deﬁnition 2.7.1. A mapping Tfrom RntoRmis called a linear trans- formation if T(x+y)=Tx+Ty∀x, y∈Rn T(ax)=aTx ∀a∈F. 80 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Note: We normally write Txinstead of T(x). Example 2.7.1. T:Rn→Rm.L e t a∈Rmandy∈Rn.T h e n f o r e a c h x∈Rn,Tx=x, yXais a linear transformation. Let S={v1...v n}be a basis of Rn, and de ﬁne the m×nmatrix with columns given by the coordinates of Tv1,Tv 2,... ,Tv n. Then this matrix A=^ Tv1Tv2 Tvn ↓↓ ···↓ is the matrix representation of Twith respect to the basis S.T h u s , i f x=Σaivi, whence [ x]S=(a1...a n), we have [Tx]S=A[x]S TThere is a duality between all linear transformations from RntoRm and the set Mm,n(F). Note that Mm,n(F) is itself a vector space over F. Hence L(Fn,Fm), the set of linear transformations from FntoFmis likewise. As such it has subspaces. Example 2.7.2. (1) Let ¯ x∈Fn.D eﬁniteJ={T∈L|T¯x=0}.T h e n Jis a subspace of L(Fn,Fm). (2) Let U={T∈L(Rn,Rn)|Tx≥0i fx≥0},w h e r e {x≥0}means the positive orthant of Rn.Uisnota linear subspace of L(Rn,Rn), though it is a convex set. (3) De ﬁneT:Pn→PnbyTp=d dxp.Tis a linear transformation. Example 2.7.3. Express the linear transformation D:P3→P3given by Dp=d dxp(x) as a matrix with respect to the basis. S={1,x ,x2,x3}.W e have D1=0=0+0 x+0x2+0x3.A l s o [D1]S=[ 0,0,0,0]T similarly [Dx]S=[ 1,0,0,0]T [Dx2]S=[ 0,2,0,0]T [Dx3]S=[ 0,0,3,0]T. 2.7. LINEAR TRANSFORMATIONS 81 Hence [D]S= 0100 0020 00030000 . In this context the di ﬀerentiation operator is rather simple. Example 2.7.4. Consider the linear transformation Tdeﬁned by Tq= 3x d dxq+x2qforq∈P2.Find the matrix representation of T. Solution. First o ﬀwe notice that this transformation has range in P4.Let’s use the standard bases for this problem. We then determine the coordinates of Tfor vectors in the P2basis {1,x ,x2}in the P4basis {1,x ,x2,x3,x4}.Compute T(1) = x2 T(x)=3 x+x3 TD x2i =6 x2+x4 The coordinates of the input vectors we know are [1 ,0,0]T,[0,1,0]T,and [0,0,1]T.For the output vectors the coordinates are [0 ,0,1,0,0]T,[0,3,0,1,0]T, and [0 ,0,6,0,1]T.So, with respect to these two bases, the matrix of the transformation is A= 000 030 106 010001  Observe that the dimensionality corresponds with the dimentionality of the respective spaces. Example 2.7.5. LetV=R 2,w i t h S0={v1,v2}={[1 0],[1 1]},S1= {w1,w2}=\ [1 2],J−2 1o ,a n d T=Ithe identity. The vectors above are expressed in the standard E={e1,e2},Tvj=Ivj=vj.T o ﬁnd [vj]S1we solve vj=ajw1+βjw2 82 CHAPTER 2. MATRICES AND LINEAR ALGEBRA v1:}1−2 21]}α1 β1] =}1 0] −→}α1 β1] =}1 5 −2 5] v2:}1−2 21]}α2 β2] =}1 1] −→}α2 β2] =}3 5 −1 5]A tsolve linear systems Therefore S1[I]S0=}1 53 5 −2 5−1 5] ←change of basis matrix If [x]S0=}−1 2] [x]S1=S1[I]S0}−1 2] =1 5}13 −2−1]}−1 2] =1 5}5 0] =}1 0] . Note the necessity of using the standard basis to express the vectors in both bases S0andS1. 2.8 Change of Basis LetVbe a vector space with bases S0={v1...v n}andS1={w1...w n}, and suppose T:V→Vis a linear transformation. We want to ﬁnd the representation of Tas a matrix that takes a vector xg i v e ni nt e r m so fi t s S0 coordinates and produces the vector Txg i v e ni nt e r m so fi t s S1coordinates. We know that x→[x]S0is well de ﬁned. The action of Tis known if the nvector [ x]S0=}c1...cn] and the vectors Tv1,Tv 2,... ,Tv nare known, for if x=Σcjvj,t h e n Tx=ΣcjTvj,b yl i n e a r i t y . To determine [ Tx]S1we need to convert the Tvj,j=1,...,n to coor- dinates in the other S1basis, This is done as follows. Find [Tvj]S1= t 1j t2j ... tnj j=1,2,... ,n . 2.8. CHANGE OF BASIS 83 Then if x∈V [Tx]S1=[ΣcjTvj]S1=Σcj[Tvj]S1 = 3 jtijcj  = t11... t 1n tn1 tnn  c1 ... cn . This n×narray [ tij] depends on T,S 0andS1but not on x.W ed e ﬁne the S0→S1basis representation of Tto be [ tij], and we write this as S1[T]S0= t11... t 1n ......... tn1... t nn . In the special case that Tis the identity operator the matrix S1[I]S0converts the coordinates of a vector in the basis S0to coordinates in the basis S1.I t is easy to see that S0[I]S1must be the inverse of S1[I]S0and thus S0[I]S1·S1[I]S0=I. We can also establish the equality S1[T]S1=S1[I]S0S0[T]S0S0[I]S1. In this way we see that the matrix representation of Tdepends on the bases involved. If Xi sa n yi n v e r t i b l em a t r i xi n Mn(F)w ec a nw r i t e B=X−1AX. The interpretation in this context is clear X: change of coordinate from one basis to another S0→S1 X−1: change of coordinate S1→S0 A: matrix of the linear transformation in the basis S0 B: matrix of the same linear transformation in the basis S1. With this in mind it seems prudent to study linear transformations in the basis that makes their matrix representation as simple as possible. 84 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Example 2.8.1. LetA=}13 −11] be the matrix representation of a lin- ear transformation given with respect to the standard basis S0={e1,e2}= {(1,0),(0,1)}Find the matrix representation of this transformation with resepect to the basis S1={v1,v2}={(2,1),(1,1)}. Solution. According to the analysis above we need to determine S0[I]S1and S1[I]S0.Of course S1[I]S0=S0[I]−1 S1.Since the coordinates of the vectors inS1are expressed in terms of the basis vectors S0we obtain directly S0[I]S1=}21 11] Its inverse is given by S0[I]−1 S1=}1−1 −12] Assembling these matrices we have the ﬁnal matrix converted to the new basis. S1[A]S1= S1[I]S0AS0[I]S1 =}1−1 −12]}13 −11]}21 11] =}64 −7−4] Example 2.8.2. Consider the same problem as above except that the ma- trixAi sg i v e ni nt h eb a s i s S1. Find matrix representation of this transfor- mation with resepect to the basis S0. Solution. To solve this problem we need to determine S0[A]S0=S0[I]S1AS1[I]S0. As we already have these matrices, we determine that S0[A]S0= S0[I]S1AS1[I]S0. =}21 11]}13 −11]}1−1 −12] =}−61 3 −48] 2.9. APPENDIX A – SOLVING LINEAR SYSTEMS 85 2.9 Appendix A – Solving linear systems The key to solving linear systems is to reduce the augmented system to RREF and solve the resulting equations. While this may be so, there is anintermediate step that occurs about half way through the computation ofthe RREF where the reduced matrix achieves an upper triangular form. Atthis point the solution can be determined directly by back substitution. To clarify the rules on back substitution, suppose that we have the triangular form  a 11a12···a1n 0a22···a2n ......... 0··· 0anneeeeeeeeeb 1 b2 ... bn  Assuming that the diagonal part consists of all nonzero terms, we can solve this system by back substitution. First solve for x n=bn ann. Now inductively solve for the remaining solution coordinates using the formula xn−j=1 bn−j,n−j^j−13 k=0an−j,n−kxn−k ,j =1,2,..., n−1 This inconvenient looking formula can be replaced by xj=1 bjj n3 k=j+1ajkxk ,j =n−1,n−2,..., 1 where the index runs from j=n−1u pt o j=1.The upshot is that the row reduction process can be halted when a triangular-like form has beenattained. The applies as well to nonsingular and non square systems, wherethe the process is stopped when all the leading ones have been identi ﬁed, entries below them have been zeroed out, and all the zero rows are present. The principle reason for using back substitution is to reduce the number of computations required, an important consideration in numerical linearalgebra. In the example below we solve a 3 ×3 nonsingular system. Example 2.9.1. Solve Ax=bwhere A= 120 22−1 −13 2 b= 3 6 −2  86 CHAPTER 2. MATRICES AND LINEAR ALGEBRA Solution. Find the RREF of [ A|b]. Then solve Ax=b.  120 22−1 −13 2eeeeee3 6 −2 −2R 1+R2 → R1+R3 12 0 0−2−1 05 2eeeeee3 0 1  − 1 2R2 → 120 011 2 052eeeeee3 0 1  −5R 2+R3 → 12 0 011 2 00−1 2eeeeee3 01  (∗) − 1 2R3+R2 → 120 010001eeeeee3 1 −2  −2R 3 → 120 011 2 001eeeeee3 0 −2  −2R 2+R1 → 100 010001eeeeee1 1 −2  Hence solving we obtain x 3=−2,x 2=1,andx1=1 . T h i si s ﬁne, but there is a faster way to solve this system. Stop the reduction when the system attains a triangular form at ( ∗).From this point solve to obtain x3=−2.Now back substitute x3= 2 into the second row (equation) to solve for x2.T h u s x2=−1 2(−2) = 1 .Finally, back substitute x3=2 a n d x2= 1 into the ﬁrst row (equation) to solve for x1.T h u s x1=3−2( 1 )=1 . Sometimes the form ( ∗) is called the row reduced form. Example 2.9.2. Given the augmented system for Ax=bis in RREF.  12000 0 00120 −1 00001 300000 0eeeeeeee4 110  2.9. APPENDIX A – SOLVING LINEAR SYSTEMS 87 Find the solution. Solution. The leading ones occur in columns 1, 3, and 5. The values in columns 2, 4, and 6 can be taken as free parameters. So, take x2=r, x 4=s, andx6=t. Now solving for the other varables we have x1=4−2r x3=1−2s+t x5=1−3t The solution set is comprised of the vectorx=[ 4−2r, r,1−2s+t, s, 1−t, t] T =[ 4 ,0,1,0,1,0]T+r[−2,1,0,0,0,0]T+s[0,0,−2,1,0,0]T+t[0,0,1,0−3,1]T for all r, s, andt.We can rewrite this as the set S=   4 0 1010 +r −2 1 0000 +s 0 0 −2 100 +t 0 0 10 −3 1 eeeeeeeeeeeer, s, t∈RorC   This representation shows better the connection between the free constants and the component vectors that make up the solution. Note this expressionalso reveals the solution of the homogeneous solution Ax=0a st h es e t + r[−2,1,0,0,0,0] T+s[0,0,−2,1,0,0]T+t[0,0,1,0−3,1]Teeer, s, t∈RorC Indeed, this is a full subspace. Example 2.9.3. The RREF can be used to determine the inverse, as well. Given the matrix A∈M n,the inverse is given by the matrix Xfor which AX =I. I nt u r nw i t h x1, ..., x nrepresenting the columns of Xande1, ..., e nrepresenting the standard vectors we see that Axj= ej,j=1,2,...,n . To solve for these vectors, form the augmented matrix [A|ej],j=1,2,..., n and row reduce as above. A massive short cut to this process is to augment all the standard vectors at one and row reduce the 88 CHAPTER 2. MATRICES AND LINEAR ALGEBRA resulting n×2nmatrix [ A|I]. If Ais invertible, its RREF is the identity. Therefore, [A|I]row → operations[I|X] and, of course, A−1=X.T h u s , f o r A= −21 0 1123−2−1  we row reduce [ A|I]a sf o l l o w s [A|I]= −21 0 1123−2−1eeeeee100 010001  row → operations 100 010001eeeeee312 724 −5−1−3  2.10 Exercises 1. Consider the di ﬀerential operator T=2xd dx(·)−4 acting on the vector space of cubic polynomials, P3.Show that Tis a linear transformation andﬁnd a matrix representation of it. Assume the basis is given by {1,x ,x2,x3}. 2. (i) Find matrices AandB, each with positive rank, for which r(A+ B)=r(A)+r(B). (ii) Find matrices AandB,e a c hw i t hp o s i t i v e rank, for which r(A+B) = 0. (iii) Give a method to ﬁnd two nonzero matrices AandBfor which the sum has any preassigned rank. Of course, the matrix sizes may depend on this value. 3. Find square matrices AandBfor which r(A)=r(B)=2a n df o r which r(AB)=0 . 4. Suppose that A is an m×nmatrix and that xis a solution of Ax=b over the prescribed ﬁeld. Show that every solution of Ax=bhave the form x+x0,w h e r e x0is a solution of Ax0=0 . 2.10. EXERCISES 89 5. Find a matrix A∈Mnof rank n−1f o rw h i c h r(Ak)=n−kfork≤n. Is it possible to begin this process with a matrix A∈Mnof rank n and for which r(Ak)=n−k+1 f o r k≤n? 6. Show that Ax=bhas a solution if and only if yTb=0i fa n do n l yi f yTA= 0 for some column vector. 7. In R2the linear transformation that rotates any vector by θradians counter clockwise Thas matrix representation with respect to the standard basis given by A=}cosθ−sinθ sinθcosθ] What is the matrix representation with respect to the standard basis of the transformation that rotates any vector by θradians clockwise? What is the relation between the matrices? 8. Show that if B,C∈Mn(F), where Bis symmetric and Cis skew- symmetric, then B=Cimplies that B=C=0 . 9. Prove the general formula for the inverse of the 2 ×2m a t r i x A=}ab cd] isA−1=1 detA}d−b −ca] . 10. Prove Theorem 2.5.1(a). 11. Prove Theorem 2.5.1(b). 12. Prove that every permutation σmust have an inverse σ−1(i . e .σ−1(σ(j)) = j), and the signs of σ−1andσare the same. 13. Show that the sign of every transposition is −1. 14. Prove that det A= σ(−1)sgn(σ)w iaσ(i)iW 15. Prove Proposition 2.5.2 using minors. 16. Suppose that the n×nmatrix Ais singular. Show that each column of the adjugate matrix ˆAis a solution of Ax=0 . ( M c D u ﬀee, Chapter 3, Theorem 29.) 90 CHAPTER 2. MATRICES AND LINEAR ALGEBRA 17. Suppose that Ais an ( n−1)×nmatrix, and consider the homogeneous system Ax=0f o r x∈Rn.D e ﬁnehito be the determinant of the (n−1)×(n−1) matrix formed by removing the ithcolumn of A. Show that the vector h=(h1, ..., h n)Tis a solution to Ax=0 . ( M c D u ﬀee, Chapter 3, Corollary 29.) 18. Show that A=J1−1 −11o has no inverse by trying to solve AB=IThat is, assume the form B=}ab cd] multiply the matrices ( AandB) together, and then solve for the un- knowns a, b, c, andd. (This is not a very e ﬃcient way to determine inverses of matrices. Try the same thing for any 3 ×3m a t r i x . ) 19. Prove that the elementary equation operations do not change the so- lution set of a linear system. 20. Find the inverses of E1,E2,a n d E3. 21. Find the matrix representation of linear transformation Tthat rotates any vector by θradians counter clockwise (ccw) with respect to the basis S={(2,1),(1,1)}. 22. Consider R3.Suppose that we have angles {θi}3 i=1and pairs of co- ordinate vectors {(e1,e2),(e1,e3),(e2,e3)}.LetTbe the linear trans- formation that successively rotates a vector in the respective planes {(ei1,ei2)}k i=1through the respective angles {θi}k i=1.Find the matrix representation of Twith respect to the standard basis .Prove that it is invertible. 23. Prove Theorem 2.2.4.24. Prove or disprove the equivalence of the linear systems. 2x−3y=−1 x+4y=5−x+4y=3 x+2y=3 25. Find basis for the orthoc omplement of the subspace of R 3spanned by the vectors {[2,1,1]T,[1,1,2]T}. 26. Find basis for the orthoc omplement of the subspace of R3spanned by the vector [1 ,1,1]T. 2.10. EXERCISES 91 27. Consider planar rotations in Rnwith respect to the standard bases elements .Prove that there must ben(n−1) 2of them – discounting the particular angle. Display the general representation of any of them. Prove or disprove that any two of them are commutative. Thatis for two angles {θ i}2 i=1and pairs of coordinate vectors {(ei1,ei2)}k i=1 the respective counter clockwise rotations are commutative. 28. Suppose that A∈Mmk,B∈Mknand both have rank k.Show that the rank of ABisk. 29. Suppose that A∈Mmkhas rank k.P r o v e t h a t ARREF =}Ik 0] where Ikis the identity matrix of size kand 0 is the m−k×kzero matrix. 30. Suppose that B∈Mknhas rank k.P r o v e t h a t BRREF =J Ik0o where Ikis the identity matrix of size kand 0 is the k×n−kzero matrix. 31. Determine and prove a version of Corollary 2.6.1 for 3 ×3b l o c k e d matrices, where we assume the diagonal blocks A11is invertible and wish to conclude the result that the rank of Ais the equal to the rank ofA11. 32. Suppose that we have angles {θi}k i=1and pairs of coordinate vectors {(ei1,ei2)}k i=1.LetTbe the linear transformation that successively rotates a vector in the respective planes {(ei1,ei2)}k i=1through the respective angles {θi}k i=1.Prove that the matrix representation of the linear transformation with respect to any basis must be invertible. 33. The super-diagonal of a matrix is the set of elements ai,i+1.The subdi- agonal of a matrix is the set of elements ai−1,i.A tri-banded matrix is one for which the entries are zero above the super-diagonal and belowthe subdiagonal. Suppose that for an n×ntri-banded matrix T,w e have a i−1,i=a, a ii=0,andai,i+1=c.Prove the following facts: (a) If nis odd det A=0. (b) If n=2mis even det T=(−1)mamcm. 34. For the banded matrix of the previous example, prove the following for the powers TpofT. 92 CHAPTER 2. MATRICES AND LINEAR ALGEBRA (a) If pis odd, prove that ( Tp)ij=0i f i+jis even. (b) If pis even, prove that ( Tp)ij=0i f i+jis odd. 35. Consider the vector space P2(1,2) with inner product de ﬁned byp, qX=$2 1p(x)q(x)dx.Find an orthogonal basis of P2(1,2).(Hint. Begin with the standard basis {1,x ,x2}.Apply the Gram-Schmidt procedure.) 36. For what values of aandbis the matrix below singular A= a21 21 b 1a−2  37. The Vandermonde matrix, de ﬁned for a sequence of numbers {x1,...x n}, is given by the n×nmatrix Vn= 1x 1x2 1···xn−1 1 1x2x2 2···xn−1 2 ............... 1xnx2 n···xn−1 n  Prove that the determinant is given by detV n=n i>j=1(xi−xj) 38. In the case the x-values are the integers {1,...,n },p r o v et h a td e t Vn is divisible byn i=1(i−1)!.(These numbers are called superfactorials.) 39. Prove that for the weighted functional de ﬁned in Remark 2.4.1, it is necessary and su ﬃcient that the weights be strictly positive for it to be an inner product. 40. For what values of aandbis the matrix below singular A= b0a0 00 ba 0a0b ba 00  2.10. EXERCISES 93 41. Find an orthogonal basis for R2from the vectors {(1,2),(2,1)}. 42. Find an orthogonal basis of the subspace of R3spanned by {(1,0,1),(0,1,−1)} 43. Suppose that Vis a vector space with an inner product, and S⊂V. Show that if Sis a basis of V,S⊥={0}. 44. Suppose that Vis a vector space with an inner product, and S⊂V. Show that if U=S(S), then U⊥=S⊥. 45. Let A∈Mmn(F). Show it may not be true that r(A)=r(ATA)= r(AAT) unless F=R, in which case it is true. 46. If A∈Mn(C) is orthogonal, show that the rows and columns of Aare orthogonal. 47. If Ais orthogonal then Amis orthogonal for every positive integer m. (This is a part of Theorem 2.4.3(b).) 48. Consider the polynomial space Pn[−1,1] with the inner product p, qX=$1 −1p(t)q(t)dt.Show that every polynomial p∈Pnfor which p(1) = p(−1) = 0 is orthogonal to its derivative. 49. Consider the polynomial space Pn[−1,1] with the inner product p, qX=$1 −1p(t)q(t)dt.Show that the subspace of polynomials in even pow- ers (e.g. p(t)=t2−5t6) is orthogonal to the subspace of polynomials in odd powers. 50. Let A=}13 −11] be the matrix representation of a linear trans- formation given with respect to the standard basis S0={e1,e2}= {(1,0),(0,1)}Find the matrix representation of this transformation with resepect to the basis S1={v1,v2}={(2,−3),(1,−2)}. 51. Show that the sign of every transposition from the set {1,2, ..., n }is −1. 52. What are the signs of the permutations {7, 6, 5, 4, 3, 2, 1 }and {7,1, 6, 4, 3, 5, 2 }of the integers {1, 2, 3, 4, 5, 6, 7 }? 53. Prove that the sign of the permutation {m, m−1,..., 2,1}is (−1)m. 54. Suppose A, B∈Mn(F). IfAis singular, use a row space argument to show that det AB=0 . 94 CHAPTER 2. MATRICES AND LINEAR ALGEBRA 55. Show that if A∈Mm,nandB∈Mm,nand both r(A)=r(B)=m.I f r(AB)=m−k, what can be said about n? 56. Prove that deteeeeeeeex 1x2x3x4 −x2x1−x4x3 −x3x4x1−x2 −x4−x3−x2x1eeeeeeee=D x 2 1+x2 2+x2 3+x2 4i2 57. Prove that there is no invertible 3 ×3 matrix that has all the same cofactors. What similar statement can be made for n×nmatrices? 58. Show by example that there are matrices AandBfor which lim n→∞An and lim n→∞Bnboth exist, but for which lim n→∞(AB)ndoes not ex- ist. 59. Let A∈M2(C). Show that there is no matrix solution B∈M2(C) toAB−BA=I. What can you say about the same problem with A, B∈Mn(C)? 60. Show by example that if AC=BCthen it does not follow that A=B. However, show that if Cis inveritble the conclusion A=Bis valid.