theorems on rank

Linear Algebra and Matrices Notes from Charles A. Rohde Fall 2003 Contents 1 Linear Vector Spaces 1 1.1 Definition and Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Linear Independence and Bases . . . . . . . . . . . . . . . . . . . . . . . 3 2 Linear Transformations 7 2.1 Sums and Scalar Products . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Matrices 9 3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Sums and Products of Matrices . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Conjugate Transpose and Transpose Operations . . . . . . . . . . . . . . 13 3.4 Invertibility and Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 Direct Products and Vecs . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4 Matrix Factorization 22 4.1 Rank of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 i 5 Linear Equations 34 5.1 Consistency Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.2 Solutions to Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2.1 Aispbypof rank p. . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2.2 Aisnbypof rank p. . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2.3 Aisnbypof rank rwhere r·p·n. . . . . . . . . . . . . . . 37 5.2.4 Generalized Inverses . . . . . . . . . . . . . . . . . . . . . . . . . 39 6 Determinants 40 6.1 Definition and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6.2 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 7 Inner Product Spaces 44 7.1 definitions and Elementary Properties . . . . . . . . . . . . . . . . . . . . 44 7.2 Gram Schmidt Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.3 Orthogonal Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 8 Characteristic Roots and Vectors 51 8.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 8.2 Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 8.3 Quadratic Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 8.4 Jordan Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 8.5 The Singular Value Decomposition (SVD) of a Matrix . . . . . . . . . . . 61 8.5.1 Use of the SVD in Data Reduction and Reconstruction . . . . . . 63 æ ii Chapter 1 Linear Vector Spaces 1.1 Definition and Examples Definition 1.1 A linear vector space Vis a set of points (called vectors) satisfying the following conditions: (1) An operation + exists on Vwhich satisfies the following properties: (a)x+y=y+x (b)x+ (y+z) = (x+y) +z (c) A vector 0exists in Vsuch that x+0=xfor every x2 V (d) For every x2 Va vector ¡xexists in Vsuch that ( ¡x) +x=0 (2) An operation ±exists on Vwhich satisfies the following properties: (a)®±(x+y) =®±y+®±x (b)®±(¯±x) = (®¯)±x (c) (®+¯)±x=®±x+¯±x (d) 1±x=x 1 where the scalars ®and¯belong to a field Fwith the identity being given by 1. For ease of notation we will eliminate the ±in scalar multiplication. In most applications the field Fwill be the field of real numbers Ror the field of complex numbers C. The 0vector will be called the null vector or the origin . example 1: Letxrepresent a point in two dimensional space with addition and scalar multiplication defined by " x1 x2# +" y1 y2# =" x1+y1 x2+y2# and®" x1 x2# =" ®x1 ®x2# The origin and negatives are defined by " 0 0# and¡" x1 x2# =" ¡x1 ¡x2# example 2: Letxrepresent a point in ndimensional space (called Euclidean space and denoted by Rn) with addition and scalar multiplication defined by 2 66664x1 x2 ... xn3 77775+2 66664y1 y2 ... yn3 77775=2 66664x1+y1 x2+y2 ... xn+yn3 77775and®2 66664x1 x2 ... xn3 77775=2 66664®x1 ®x2 ... ®xn3 77775 The origin and negatives are defined by 2 666640 0 ... 03 77775and¡2 66664x1 x2 ... xn3 77775=2 66664¡x1 ¡x2 ... ¡xn3 77775 example 3: Letxrepresent a point in ndimensional complex space (called Unitary space and denoted by Cn) with addition and scalar multiplication defined by 2 66664x1 x2 ... xn3 77775+2 66664y1 y2 ... yn3 77775=2 66664x1+y1 x2+y2 ... xn+yn3 77775and®2 66664x1 x2 ... xn3 77775=2 66664®x1 ®x2 ... ®xn3 77775 2 The origin and negatives are defined by 2 666640 0 ... 03 77775and¡2 66664x1 x2 ... xn3 77775=2 66664¡x1 ¡x2 ... ¡xn3 77775 In this case the xiandyican be complex numbers as can the scalars. example 4: Letpbe an nth degree polynomial i.e. p(x) =®0+®1x+¢¢¢+®nxn where the ®iare complex numbers. Define addition and scalar multiplication by (p1+p2)(x) =nX i=0(®1i+®2i)xiand®p=nX i=0®®ixi The origin is the null function and ¡pis defined by ¡p=nX i=0¡®ixi example 5: LetX1; X2; : : : ; X nbe random variables defined on a probability space and define Vas the collection of all linear combinations of X1; X2; : : : ; X n. Here the vectors inVare random variables. 1.2 Linear Independence and Bases Definition 1.2 A finite set of vectors fx1;x2; : : : ;xkgis said to be a linearly inde- pendent set ifX i®ixi=0=)®i= 0 for each i If a set of vectors is not linearly independent it is said to be linearly dependent . If the set of vectors is empty we defineP ixi=0so that, by convention, the empty set of vectors is a linearly independent set of vectors. 3 Theorem 1.1 The set fx1;x2; : : : ;xkgis linearly dependent if and only if xt=t¡1X i=1®ixifor some t¸2 Proof: Sufficiency is obvious since the equation xt¡t¡1X i=1®ixi=0 does not imply that all of the coefficients of the vectors are equal to 0. Conversely, if the vectors are linearly dependent then we have X i¯ixi=0 where at least two of the ¯s are non-zero (we assume that none of the x’s are the zero vector). Thus, with suitable relabelling, we have tX i=1¯ixi=0 where ¯t6= 0. Thus xt=¡t¡1X i=1ïi ¯t! xi=t¡1X i=1®ixi2 Definition 1.3 Alinear basis orcoordinate system in a vector space Vis a set Eof linearly independent vectors in Vsuch that each vector in Vcan be written as a linear combination of the vectors in E. Since the vectors in Eare linearly independent the representation as a linear com- bination is unique. If the number of vectors in Eis finite we say that Visfinite dimensional . Definition 1.4 Thedimension of a vector space is the number of vectors in any basis of the vector space. 4 If we have a set of linearly independent vectors fx1;x2; : : : ;xkg, this set may be ex- tended to form a basis. To see this let Vbe finite dimensional with basis fy1;y2; : : : ;yng. Consider the set fx1;x2; : : : ;xk;y1;y2; : : : ;yng Letzbe the first vector in this set which is a linear combination of the preceeding ones. Since the x’s are linearly independent we must have z=yifor some i. Thus the set fx1;x2; : : : ;xk;y1;y2; : : : ;yi¡1;yi+1; : : : ;yng can be used to construct every vector in V. If this set of vectors is linearly independent it is a basis which includes the x’s. If not we continue removing y’s until the remaining vectors are linearly independent. It can be proved, using the Axiom of Choice, that every vector space has a basis. In most applications an explicit basis can be written down and the existence of a basis is a vacuous question. Definition 1.5 A non-empty subset Mof a vector space Vis called a linear manifold or asubspace ifx;y2 Vimplies that every linear combination ®x+¯y2 M . Theorem 1.2 The intersection of any collection of subspaces is a subspace. Proof: Since 0is in each of the subspaces it is in their intersection. Thus the intersection is non-empty. If xandyare in the intersection then ®x+¯yis in each of the subspaces and hence in their intersection. It follows that the intersection is a subspace. 2 Definition 1.6 Iffxi; i2Igis a set of vectors the subspace spanned byfxi; i2Igis defined to be the intersection of all subspaces containing fxi; i2Ig. Theorem 1.3 Iffxi; i2Igis a set of vectors the subspace spanned byfxi; i2Ig, sp(fxi; i2Ig), is the set of all linear combinations of the vectors in fxi; i2Ig. Proof: The set of all linear combinations of vectors in fxi; i2Igis obviously a subspace which contains fxi; i2Ig. Conversely, sp(fxi; i2Ig) contains all linear combinations of vectors in fxi; i2Igso that the two subspaces are identical. 2 It follows that an alternative characterization of a basis is that it is a set of linearly independent vectors which spans V. 5 example 1: IfXis the empty set then the space spanned by Xis the 0vector. example 2: InR3letXbe the space spanned by e1;e2where e1=2 641 0 03 75ande2=2 640 1 03 75 Then spfe1;e2gis the set of all vectors of the form x=2 64x1 x2 03 75 example 3: IffX1; X2; : : : ; X ngis a set of random variables then the space spanned byfX1; X2; : : : ; X ngis the set of all random variables of the formP iaiXi. This set is a basis if P(Xi=Xj) = 0 for i6=j. æ 6 Chapter 2 Linear Transformations LetUbe a pdimensional vector space and let Vbe an ndimensional vector space. 2.1 Sums and Scalar Products Definition 2.1 A linear transformation LfromUtoVis a mapping (function) from U toVsuch that L(®x+¯y) =®L(x) +¯L(y) for every x;y2 U and all ®; ¯ Definition 2.2 The sum of two linear transformations L1andL2is defined by the equation L(x) =L1(x) +L2(x) for every x2 U Similarly ®Lis defined by [®L](x) =®L(x) The transformation Odefined by O(x) =0has the properties: L+O=O+L;L+ (¡L) = (¡L) +L=O Also note that L1+L2=L2+L1. Thus linear transformations with addition and scalar multiplication as defined above constitute an additive commutative group. 7 2.2 Products IfUispdimensional, Vismdimensional and Wisndimensional and L1:U ! V andL2:V ! W we define the product ,L, ofL1andL2by L(x) =L2(L1(x)) Note that the product of linear transformations is not commutative. The following are some properties of linear transformations LO =OL=O L1(L2+L3) = L1L2+L1L3 L1(L2L3) = ( L1L2)L3 IfU=V,Lis called a linear transformation on a vector space and we can define the identity transformation Iby the equation I(x) =x Then LI=IL=L We can also define, in this case, A2, and in general Anfor any integer n. Note that AnAm=An+mand ( An)m=Anm If we define A0=Ithen we can define p(A), where pis a polynomial by p(A)(x) =nX i=0®iAix æ 8 Chapter 3 Matrices 3.1 Definitions IfLis a linear transformation from U(pdimensional) to V(ndimensional) and we have basesfxj:j2Jgandfyi:i2Igrespectively for UandVthen for each j2Jwe have L(xj) =nX i=1`ijyifor some choice of `ij Then£parray2 66664`11`12¢¢¢`1p `21`22¢¢¢`2p ............ `n1`n2¢¢¢`np3 77775 is called the matrix ofLrelative to the bases fxj:j2Jgandfyi:i2Ig. To determine the matrix of Lwe express the transformed jth vector of the basis in the U space in terms of the basis of the Vspace. The nnumbers so obtained form the jth column of the matrix of L. Note that the matrix of Ldepends on the bases chosen for UandV. In typical applications a specific basis is usually present. Thus in Rnwe usually 9 choose the basis fe1;e2; : : : ;engwhere ei=2 66664±1i ±2i ... ±ni3 77775and±ji=( 1j=i 0j6=i In such circumstances we call Lthe matrix of the linear transformation. Definition 3.1 A matrix Lis an nbyparray of scalars and is a carrier of a linear transformation ( Lcarries the basis of Uto the basis of V). The scalars making up the matrix are called the elements of the matrix. We will write L=f`ijg and call `ijthei; jelement of L(`ijis thus the element in the ith row and jth column of the matrix L). The zero or null matrix is the matrix each of whose elements is 0 and corresponds to the zero transformation. A one by pmatrix is called a row vector and is written as `T i= (`i1; `i2; : : : ; ` ip) Similarly an nby one matrix is called a column vector and is written as `j=2 66664`1j `2j ... `nj3 77775 With this notation we can write the matrix Las L=2 66664`T 1 `T 2... `T n3 77775 Alternatively if `jdenotes the jth column of Lwe may write the matrix Las L=h `1`2¢¢¢`pi 10 3.2 Sums and Products of Matrices IfL1andL2are linear transformations then their sum has matrix Ldefined by the equation L(xj) = ( L1+L2)(xj) =L1(xj+L2(xj) =X i`(1) ijyi+X i`(2) ijyi =X i³ `(1) ij+`(2) ij´ yi Thus we have the following Definition 3.2 The sum of two matrices AandBis defined as A+B=faij+bijg Note that AandBboth must be of the same order for the sum to be defined. Definition 3.3 The multiplication of a matrix by a scalar is defined by the equation ¸A=f¸aijg Matrix addition and scalar multiplication of a matrix have the following properties: ²A+O=O+A=A ²A+B=B+A ²A+ (B+C) = (AB) +C ²A+ (¡A) =O IfL1andL2are linear transformations then their product has matrix Ldefined by the equation L(xj) = L2(L1(xj)) 11 =L2ÃX k`(1) kjyk! =ÃX k`(1) kjL2(yk)! =X k`(1) kjÃX i`(2) ikzi! =X iÃX k`(2) ik`(1) kj! zi Thus we have Definition 3.4 The product of two matrices AandBis defined by the equation AB=fX kaikbkjg Thus the matrix of the product can be found by taking the ith row of Atimes the jth column of Belement by element and summing. Note that the product is defined only if the number of columns of Ais equal to the number of rows of B. We say that A premultiplies Bor that Bpost multiplies Ain the product AB. Matrix multiplication is not commutative. Provided the indicated products exist matrix multiplication has the following prop- erties: ²AO=OandOA=O ²A(B+C) =AB+AC ²(A+B)C=AC+BC ²A(BC) = (AB)C Ifn=pthe matrix Ais said to be a square matrix. In this case we can compute An for any integer nwhich has the following properties: ²AnAm=An+m 12 ²(An)m=Anm Theidentity matrix Ican be found using the equation I(xj) =xj so that the jth column of the identity matrix consists of a one in the jth row and zeros elsewhere. The identity matrix has the property that AI=IA=A If we define A0=Ithen if pis a polynomial we may define p(A) by the equation p(A) =nX i=0®iAi 3.3 Conjugate Transpose and Transpose Operations Definition 3.5 Theconjugate transpose ofA,A¤is A¤=f¯ajig where ¯ ais the complex conjugate of a. Thus if Aisnbyp, the conjugate transpose A¤, ispbynwith i; jelement equal to the complex conjugate of the j; ielement of A. Definition 3.6 Thetranspose ofA,ATis AT=fajig Thus if Aisnbypthe transpose ATispbynwith i; jelement equal to the j; ielement ofA. IfAis a matrix with real elements then A¤=AT. Definition 3.7 A square matrix is said to be ²Hermitian ifA¤=A 13 ²symmetric ifAT=A ²normal ifAA¤=A¤A The following are some properties of the conjugate transpose and transpose operations: (AB)¤=B¤A¤(AB)T=BTAT I¤=I;O¤=OTIT=I (A+B)¤=A¤+B¤(A+B)T=AT+BT (®A)¤= ¯®A¤(®A)T=®AT Definition 3.8 A square matrix Ais said to be ²diagonal ifaij= 0 for i6=j ²upper right triangular ifaij= 0 for i > j ²lower left triangular ifaij= 0 for i < j Acolumn vector is an nby one matrix and a row vector is a one by nmatrix. If x is a column vector then xTis the row vector with the same elements. 3.4 Invertibility and Inverses Lemma 3.1 A =Bif and only if Ax=Bxfor all x. Proof: IfA=Bthe assertion is obvious. IfAx=Bxfor all xthen we need only take x=eifori= 1;2; : : : ; n where eiis the column vector with 1 in the ith row and zeros elsewhere. Thus AandBare equal row by row. 2 IfAisnbypandBispbymare written as A=" A11A12 A21A22# andB=" B11B12 B21B22# 14 then the product ABsatisfies AB=" A11B11+A12B21A11B12+A12B22 A21B11+A22B21A21B12+A22B22# if the partitions are conformable. If a vector is written as x=P i®ieiwhere the eiform a basis for Vthen the product Axgives the transformed value of xunder the linear transformation Awhich corresponds to the matrix Avia the formula A(x) =X i®iA(ei) Definition 3.9 A square matrix Ais said to be invertible if (1)x16=x2=)Ax16=Ax2 (2) For every vector ythere exists at least one xsuch that Ax=y. IfAis invertible and maps UintoV, both ndimensional, then we define A¡1, which mapsVintoU, by the equation A¡1(y0) =x0 where y0is inVandx0is inUand satisfies Ax0=y0(such an x0exists by (2) and is unique by (1)). Thus defined A¡1is a legitimate transformation from VtoU. That A¡1is a linear transformation from VtoUcan be seen by the fact that if ®y1+¯y22 V then there exist unique x1andx2inUsuch that y1=A(x1) and y2=A(x2). Since A(®x1+¯x2) = ®A(x1) +¯A(x2) =®y1+¯y2 it follows that A¡1(®y1+¯y2) = ®x1+¯x2 =®A¡1(y1) +¯A¡1(y2) 15 Thus A¡1is a linear transformation and hence has a matrix representation. Finding the matrix representation of A¡1is not an easy task however. Theorem 3.2 IfA,BandCare matrices such that AB=CA=I thenAis invertible and A¡1=B=C. Proof: IfAx1=Ax2thenCAx 1=CAx 2so that x1=x2and (1) of defintion 3.9 is satisfied. If yis any vector then defining x=Byimplies Ax=ABy =yso that (2) of definition 3.9 is also satisfied and hence Ais invertible. Since AB=I=)B=A¡1 andCA=I=)C=A¡1the conclusions follow. 2 Theorem 3.3 A matrix Ais invertible if and only if Ax=0implies x=0or equiva- lently if and only if every y2 Vcan be written as y=Ax. Proof: IfAis invertible then Ax=0andA0=0implies that x=0since otherwise we have a contradiction. If Ais invertible then by (2) of definition 3.9 we have that y=Axfor every y2 V. Suppose that Ax=0implies that x=0. Then if x16=x2we have that A(x1¡x2)6= 0so that Ax16=Ax2i.e. (1) of definition 3.9 is satisfied. If x1;x2; : : : ;xnis a basis for Uthen X i®iA(xi) =0=)AÃX i®ixi! =0=)X i®ixi=0=)®1=®2=¢¢¢=®n= 0 It follows that fAx1;Ax2; : : : ;Axngis a basis for Vso that we can write each y2 Vas y=Axsince y=X i¯iA(xi) =AÃX i¯ixi! =Ax Thus (2) of definition 3.9 is satisfied and Ais invertible. Suppose now that for each y2 V we can write y=AxLetfy1;y2; : : : ;yngbe a basis for Vand let xibe such that yi=Axi. Then ifP i®ixi=0we have 0=AÃX i®ixi! 16 =X i®iA(xi) =X i®iyi which implies that each of the ®iequal 0. Thus fx1;x2; : : : ;xngis a basis for U. It follows that every xcan be written asP i¯xiand hence Ax=0implies that x=0i.e. (1) of definition 3.9 is satisfied. By assumption, (2) of definition 3.9 is satisfied so that Ais invertible. 2 Theorem 3.4 (1) If AandBare invertible so is ABand (AB)¡1=B¡1A¡1 (2) If Ais invertible and ®6= 0 then ®Ais invertible and ( ®A)¡1=®¡1A¡1 (3) If Ais invertible then A¡1is invertible and ( A¡1)¡1=A Proof: Since (AB)B¡1A¡1=AA¡1=I and B¡1A¡1AB=B¡1B=I by Theorem 3.2, ( AB)¡1exists and equals B¡1A¡1 Since (®A)®¡1A¡1=AA¡1=I and ®¡1A¡1(®A) =A¡1A=I it again follows from Theorem 3.2 that ( ®A)¡1exists and equals ®¡1A¡1.2 Since A¡1A=AA¡1=I it again follows from Theorem 3.2 that A¡1exists and equals A. In many problems one “guesses” the inverse of Aand then verifies that it is in fact the inverse. The following theorems help. Theorem 3.5 17 (1) Let" A B C D# where Ais invertible Then" A B C D#¡1 =" A¡1+A¡1BQ¡1CA¡1¡A¡1BQ¡1 ¡Q¡1CA¡1Q¡1# where Q=D¡CA¡1B. (2) Let" A B C D# where Dis invertible Then " A B C D#¡1 =" (A¡BD¡1C)¡1¡(A¡BD¡1C)¡1BD¡1 ¡D¡1C(A¡BD¡1C)¡1D¡1+D¡1C(A¡BD¡1C)¡1BD¡1# Proof:" A B C D#¡1" A¡1+A¡1BQ¡1CA¡1¡A¡1BQ¡1 ¡Q¡1CA¡1Q¡1# is equal to " AA¡1+AA¡1BQ¡1CA¡1¡BQ¡1CA¡1AA¡1BQ¡1+BQ¡1 CA¡1+CA¡1BQ¡1CA¡1¡DQ¡1CA¡1¡CA¡1BQ¡1+DQ¡1# which simplifies to " I+BQ¡1CA¡1¡BQ¡1CA¡1¡BQ¡1+BQ¡1 ¡CA¡1+ (D¡CA¡1B)Q¡1CA¡1(D¡CA¡1B)Q¡1# which is seen to be the identity matrix. 2 The proof for (2) follows similarly. Theorem 3.6 LetAbenbyn,Ubembyn,SbembymandVbembyn. Then ifA,A+UTSVandS+SVA¡1UTSare each invertible we have h A+UTSVi =A¡1¡A¡1UTSh S+SVA¡1UTSi¡1SVA¡1 18 Proof: h A+UTSVi h A+UTSVi¡1=I¡UTSh S+SVA¡1UTSi¡1SVA¡1 +UTSVA¡1¡UTSVA¡1h S+SVA¡1UTSi¡1SVA¡1 =I+UTµ I¡Sh S+SVA¡1UTSi¡1¶ SVA¡1 ¡SVA¡1UTSh S+SVA¡1UTSi¡1SVA¡1 =I+UTµ I¡h S+SVA¡1UTSi h S+SVA¡1UTSi¡1¶ SVA¡1 =I2 Corollary 3.7 IfS¡1exists in the above theorem then h A+UTSVi¡1=A¡1¡A¡1UTh S¡1+VA¡1UTi¡1VA¡1 Corollary 3.8 IfS=Ianduandvare vectors then h A+uvTi =A¡1¡1 (1 +vTA¡1u)A¡1uvTA¡1 The last corollary is used as starting point for the development of a theory of recursuve estimation in least squares and Kalman filtering in information theory. 3.5 Direct Products and Vecs ²IfAis ap£qmatrix and Bis an r£smatrix then their direct product denoted byA­Bis the pr£qsmatrix defined by A­B= (aijB) =2 66664a11Ba12B: : : a 1qB a21Ba22B: : : a 2qB ............ ap1Bap2B: : : a pqB3 77775 19 –Properties of direct products: 0­A=A­0=0 (A1+A2)­B=A1­B+A2­B A­(B1+B2) = A­B1+A­B2 ®A­¯B=®¯(A­B) A1A2­B1B2= (A1­B1)(A2­B2) (A­B)T=AT­BT rank ( A­B) = rank ( A)rank ( B) trace ( A­B) = [trace ( A)][trace[ B] (A­B)¡1=A¡1­B¡1 det(A­B) = [det( A)]p[det(B)]m ²IfYis an n£pmatrix: –vecR(Y) is the np£1 matrix with the rows of Ystacked on top of each other. –vecC(Y) is the np£1 matrix with the columns of Ystacked on top of each other. –Thei; jelement of Yis the ( i¡1)p+jelement of vec R(Y). –Thei; jelement of Yis the ( j¡1)p+ielement of vec C(Y). – vecC(YT) = vec R(Y) vecR(ABC ) = (A­CT)vec R(B) where Aisn£q1,Bisq1£q2andCisq2£p. ²The following are some relationships between vecs and direct products. abT=bT­a =a­bT vecC(abT) = b­a 20 vecR(abT) = a­b vecC(ABC ) = ( CT­A)vec C(B) trace ( ATB) = [vec C(A)]T[vec C(B)] 21 Chapter 4 Matrix Factorization 4.1 Rank of a Matrix In matrix algebra it is often useful to have the matrices expressed in as simple a form as possible. In particular, if a matrix is diagonal the operations of addition, multiplication and inversion are easy to perform. Most of these methods are based on considering the rows and columns of a matrix as vectors in a vector space of the appropriate dimension. Definition: IfAis an nbypmatrix then (1) The row rank of Ais the number of linearly independent rows of the matrix considered as vectors in pdimensional space. (2) The column rank of Ais the number of linearly independent columns of the matrix considered as vectors in ndimensional space. Theorem 4.1 LetAbe an nbypmatrix. The set of all vectors ysuch that y=Ax is a vector space with dimension equal to the column rank of Aand is called the range space ofAand is denoted by R(A). 22 Proof: R(A) is non empty since 02 R(A) Ify1andy2are in R(A) then y=®1y1+®2y2 y=®1Ax1+®2Ax2 y=A(®1x1+®2x2) It follows that y2 R(A) and hence R(A) is a vector space. If fa1;a2; : : : ;apgare the columns of Athen for every y2 R(A) we can write y=Ax=x1a1+x2a2+¢¢¢+xpap Thus the columns of AspanR(A). It follows that the dimension of R(A) is equal to the column rank of A.2 Theorem 4.2 LetAbe an nbypmatrix. The set of all vectors xsuch that Ax=0is a vector space of dimension equal to p¡column rank of A. This vector space is called thenull space ofAand is denoted by N(A). Proof: Since 02 N(A) it follows that N(A) is non empty. If x1andx2are in N(A) then A(®1x1+®2x2) = ®1Ax1+®2Ax2 =0 so that N(A) is a vector space. Letfx1;x2; : : : ;xkgbe a basis for N(A). Then there exists vectors fxk+1;xk+2; : : : ;xpg such that fx1;x2; : : : ;xpgis a basis for pdimensional space. It follows that fAx1;Ax2; : : : ;Axpg spans the range space of Asince y=Ax =AÃX i®ixi! =X i®iAxi Since Axi=0fori= 1;2; : : : ; k it follows that fAxk+1;Axk+2; : : : ;Axpgspans the range space of A. Suppose now that ®k+1; ®k+2: : : ; ® pare such that ®k+1Axk+1+®k+2Axk+2+¢¢¢+®pAxp=0 23 Then A(®k+1xk+1+®k+2xk+2+¢¢¢+®pxp) =0 It follows that ®k+1xk+1+®k+2xk+2+¢¢¢+®pxp2 N(A) Sincefx1;x2; : : : ;xpgis a basis for N(A) it follows that for some ®1; ®2; : : : ; ® kwe have ®1x1+®2x2+¢¢¢+®kxk=®k+1xk+1+®k+2xk+2+¢¢¢+®pxp or ®1x1+®2x2+¢¢¢+®kxk¡®k+1xk+1+®k+2xk+2+¢¢¢+®pxp=0 Sincefx1;x2; : : : ;xpgis a basis for pdimensional space we have that ®1=®2=¢¢¢= ®p= 0. It follows that the set fAxk+1;Axk+2; : : : ;Axpg is linearly independent and spans the range space of A. The dimension of R(Ais thus p¡k. But by Theorem 4.1 we also have that the dimension of R(A) is equal to the column rank of A. Thus p¡k= column rank of A so that k=p¡column rank of A= dim ( N(A)2 Definition 4.2 The elementary row (column) operations on a matrix are defined to be (1) The interchange of two rows (columns). (2) The multiplication of a row (column) by a non zero scalar. (3) The addition of one row (column) to another row (column). Lemma 4.3 Elementary row (column) operations do not change the row (column) rank of a matrix. 24 Proof: The row rank of a matrix Ais the number of linearly independent vectors in the set defined by A=2 66664aT 1 aT 2... aT n3 77775 Clearly interchange of two rows does not change the rank nor does the multiplication of a row by a non zero scalar. The addition of aaT jtoaT iproduces the new matrix A=2 66666666664aT 1 aT 2... aT i+aaT j... aT n3 77777777775 which has the same rank as A. The statements on the column rank of Aare obtained by considering the row vectors of ATand using the above results. 2 Lemma 4.4 Elementary row (column) operations on a matrix can be achieved by pre (post) multiplication by non-singular matrices. Proof: Interchange of the ith and jth rows can be achieved by pre-multiplication by 25 the matrix E1=2 66666666666666666666666664eT 1 eT 2... eT i¡1 eT j eT i+1... eT j¡1 eT i eT j+1... eT n3 77777777777777777777777775 Multiplication by a non zero scalar and addition of a scalar multiple of one row to another row can be achieved by pre multiplication by the matrices E2andE3where E2=2 66666666664eT 1 eT 2... aeT i... eT n3 77777777775andE3=2 66666666664eT 1 eT 2... aeT j+eT i... eT n3 77777777775 The statements concerning column operations are obtained by using the above results onAand then transposing the final results. 2 Lemma 4.5 The matrices which produce elementary row (column) operations are non singular. 26 Proof: The inverse of E1isET 1. The inverse of E2is the matrix E2=2 66666666664eT 1 eT 2... 1 aeT i... eT n3 77777777775 Finally the inverse of E3is the matrix [e1;e2; : : : ;ei; : : : ;ej¡aei; : : : ;en] Again the results for column operations follow from the row results. 2 Lemma 4.6 The column rank of a matrix is invariant under pre multiplication by a non singular matrix. Similarly the row rank of a matrix is invariant under post multiplication by a non singular matrix. Proof: By Theorem 4.2 the dimension of N(A) is equal to p¡column rank of A. Since N(A=fx:Ax=0g it follows that x2 N(A) if and only EAx =0where Eis non singular. Thus the dimension of N(A) is invariant under pre multiplication by a non singular matrix and the conclusion follows. The result for post multiplication follow by considering ATand transposing. 2 Corollary 4.7 The column rank of a matrix is invariant under premultiplication by an elementary matrix . Similarly the row rank of a matrix is invariant under post multiplication by an elementary matrix. By suitable choices of elementary matrices we can thus write PA=E where Pis the product of non singular elementary matrices and hence is non singular. The matrix Eis arow echelon matrix i.e. a matrix with rnon zero rows in which 27 the first kcolumns consist of e1;e2; : : : ;erand0’s in some order. The remaining p¡ rcolumns have zeros below the first rrows and arbitrary elements in the remaining positions. It thus follows that r= row rank of A·column rank of A and hence row rank of AT·column rank of AT But we also have that row rank of AT= column rank of A and row rank of A= column rank of AT It follows that column rank of A·row rank of A and hence we have: Theorem 4.8 row rank of A= column rank of A Alternative Proof of Theorem 4.8 LetAbe an n£pmatrix i.e. A=2 66664a11a12¢¢¢a1p a21a22¢¢¢a2p ............ an1an2¢¢¢anp3 77775 We may write Ain terms of its columns or rows i.e. A=h Ac 1;Ac 2; : : : ; Ac pi =2 66664aT 1 aT 2... aT n3 77775 28 where the jth column vector, Ac j, and ith row vector, aT iare given by Ac j=2 66664a1j a2j ... anj3 77775ai=2 66664ai1 ai2 ... aip3 77775 The column vectors of Aspan a space which is a subset of Rnand is called the column space ofAand denoted by C(A) i.e. C(A) =sp(Ac 1;Ac 2; : : : ;Ac p) The row vectors of Aspan a space which is a subspace of Rpand is called the row space ofAand denoted by R(A) i.e. R(A) =sp(a1;a2; : : : ;an) The dimension of C(A) is called the column rank ofAand is denoted by C= c(A). Similarly the dimension of R(A) is called the row rank ofAand is denoted by R=r(A). Result 1: Let B=h bc 1bc 2: : :bc Ci where the columns of Bform a basis for the column space of A. Then there is a C£p matrix Lsuch that A=BL It follows that the rows of Aare linear combinations of the rows of Land hence R(A)µ R(L) Hence R= dim[ R(A)]·dim[R(L)]·C i.e. the row rank of Ais less than or equal to the column rank of A. 29 Result 2: R=2 66664rT 1 rT 2... rT R3 77775 where the rows of Rform a basis for the row space of A. Then there is a n£Rmatrix Ksuch that A=KR It follows that the columns of Aare linear combinations of the columns of Kand hence C(A)µ C(K) Hence C= dim[ C(A)]·dim[C(K)]·R i.e. the column rank of Ais less than or equal to the row rank of A. Hence we have that the row rank and column rank of a matrix are equal. Th common value is called the rank ofA. Reference Harville, David A. (1997) Matrix Algebra From a Statistician’s Perspective. Springer (pages 36-40). We thus define the rank of a matrix A,½(A) to be the number of linearly independent rows or the number of linearly independent columns in the matrix A. Note that ½(A) is unaffected by pre or post multiplication by non singular matrices. By pre and post multiplying by suitable elementary matrices we can write any matrix as PAQ =B=" IrO O O# where Odenotes a matrix of zeroes of the appropriate order. Since PandQare non singular we have A=P¡1BQ¡1 which is an example of a matrix factorization . Another factorization of considerable importance is contained in the following Lemma. 30 Lemma 4.9 IfAis an nbypmatrix of rank rthen there are matrices B(nbyr) and C(rbyp) such that A=BC where BandCare both of rank r. Proof: Let the rows of Cform a basis for the row space of A. Then Cisrbypof rank r. Since the rows of Cform a basis for the row space of Awe can write the ith row of AasaT i=bT iCfor some choice of bi. Thus A=BC.2 The fact that the rank of Bin Lemma 4.9 is rfollows from the following important result Theorem 4.10 rank ( AB)·minfrank ( A);rank ( B)g Proof: Each row of ABis a linear combination of the rows of B. Thus rank ( AB)·rank ( B) Similarly each column of ABis a linear combination of the columns of Aso that rank ( AB)·rank ( A) The conclusion follows. 2 Theorem 4.11 Annbynmatrix is non singular if and only if it is of rank n. Proof: For any matrix we can write PAQ =" IrO O O# where PandQare non singular. Since the right hand side of this equation is invertible if and only if r=nthe conclusion follows. 2 Definition 4.3 IfAis an nbypmatrix then the pbypmatrix A¤A(ATAifAis real) is called the Gram matrix of A. Theorem 4.12 IfAis an nbypmatrix then (1) rank ( A¤A) = rank ( A) = rank ( AA¤) 31 (2) rank ( ATA) = rank ( A) = rank ( AAT) ifAis real. Proof: Assume that the field of scalars is such thatP iz¤ izi= 0 implies that z1=z2= ¢¢¢=zn= 0. If Ax=0thenA¤Ax=0. Also if A¤Ax=0thenx¤A¤Ax= 0 or z¤z= 0 so that z=0i.e.Ax=0. Hence A¤Ax=0andAx=0are equivalent statements. It follows that N(A¤A) =fx:A¤Ax=0g=fx:Ax=0g=N(A) Thus rank ( A¤A) = rank ( A). The conclusion that rank ( A¤A) = rank ( A) follows by symmetry. 2 Theorem 4.13 rank ( A+B)·rank ( A) + rank ( B) Proof: Ifa1;a2; : : : ;arandb1;b2; : : : ;bsdenote linearly independent columns of Aand Brespectively then fa1;a2; : : : ;ar;b1;b2; : : : ;bsg span the column space of A+B. Hence rank ( A+B)·r+s= rank ( A) + rank ( B)2 Definition 4.4 (1) A square matrix Aisidempotent ifA2=A. (2) A square matrix Aisnilpotent ifAm=Ofor some integer mgreater than one. Definition 4.5 Thetrace of a square matrix is the sum of its diagonal elements i.e. tr (A) =X iaii Theorem 4.14 tr (AB) = tr ( BA); tr ( A+B) = tr ( A) + tr ( B); tr ( AT) = tr ( A) Theorem 4.15 IfAis idempotent then rank ( A) = tr ( A) 32 Proof: We can write A=BCwhere Bisnbyrof rank r,Cisrbynof rank randr is the rank of A. Thus we have A2=BCBC =A=BC Hence B¤BCBCC¤=B¤BCC¤ Since BandCare each of rank rwe have that CB=Iand hence tr (BC) = tr ( CB) = tr ( I) =r= rank ( A)2 33 Chapter 5 Linear Equations 5.1 Consistency Results Consider a set of nlinear equations in punknowns a11x1+a12x2+¢¢¢+a1pxp=y1 a21x1+a22x2+¢¢¢+a2pxp=y2 ........................... an1x1+an2x2+¢¢¢+anpxp=yn which may be compactly written in matrix notation as Ax=y where Ais the nbypmatrix with i; jelement equal to aij,xis the pby one column vector with jth element equal to xjandyis the nby one column vector with ith element equal to yi. Often such “equations” arise without knowledge of whether they are really equations, i.e. does there exist a vector xwhich satisfies the equations? If such an xexists the equations are said to be consistent , otherwise they are said to be inconsistent . The equations Ax=ycan be discussed from a vector space perspective since Ais a carrier of a linear transformation from the pdimensional space spanned by the xi’s to 34 thendimensional space where y“lives”. It follows that a solution exists if and only if y is inR(A), the range space of A. Thus a solution exists if and only if yis in the column space of Adefined as the set of all vectors of the form fy:y=Axfor some xg. If we consider the augmented matrix [ A;y] we have the following theorem on consistency Theorem 5.1 The equations Ax=yare consistent if and only if rank([ A;y]) = rank( A) Proof: Obviously rank([ A;y])¸rank(A) If the equations have a solution then there exists xsuch that Ax=yso that rank(A)·rank([ A;y]) = rank([ A;Ax]) = rank( A[I;x])·rank(A) It follows that rank([ A;y]) = rank( A) if the equations are consistent. Conversely if rank([ A;y]) = rank( A) thenyis a linear combination of the columns of Aso that a solution exists. 2 Theorem 5.1 gives conditions under which solutions to the equations Ax=yexist but we need to know the form of the solution in order to explicitly solve the equations. The equations Ax=0are called the homogeneous equations . Ifx1andx2are solutions to the homogeneous equations then ®1x1+®2x2is also a solution to the homogeneous equations. In general, if fx1;x2; : : : ;xsgspan the null space of Athen x0=Ps i=1®ixiis a solution to the homogeneous equations. If xpis aparticular solution to the equations Ax=ythenxp+x0is also a solution to the equations Ax=y. Ifxis any solution then x=xp+ (x¡xp) so that every solution is of this form. We thus have the following theorem Theorem 5.2 A general solution to the consistent equations Ax=yis of the form x=xp+x0 35 where xpis any particular solution to the equations and x0is any solution to the homo- geneous equations Ax=0. A final existence question is to determine when the equations Ax=yhave a unique solution. The solution is unique if and only if the only solution to the homogeneous equations is the 0vector i.e. the null space of Acontains only the 0vector. If the solution xis unique the homogeneous equations cannot have a non zero solution x0 since then x+x0would be another solution. Conversely, if the homogeneous equations have only the 0vector as a solution then the solution to Ax=yis unique ( if there were two different solutions x1andx2thenx1¡x2would be a non zero solution to the homogeneous equations). Since the null space of Acontains only the 0vector if and only if the columns of A are linearly independent we have that the solution is unique if and only if the rank of A is equal to pwhere we assume with no loss of generality that Aisnbypwith p·n. We thus have the following theorem. Theorem 5.3 LetAbenbypwith p·nthen (1) The equations Ax=yhave the general solution x=xp+x0 where Axp=yandAx0=0if and only if rank([ A;y]) = rank( A) (2) The solution is unique ( x0=0) if and only if rank(A) =p 5.2 Solutions to Linear Equations 5.2.1 A is pbypof rank p Here there is a unique solution by Theorem 5.3 with explicit form given by A¡1y. The proof of this result is trivial given the following Lemma 36 Lemma 5.4 Apbypmatrix is non singular if and only if rank( A) =p. Proof: IfA¡1exists it is the unique matrix satisfying A¡1A=AA¡1=I Thus p¸rank(A)¸pi.e. the rank of AispifAis non singular. Conversely, if rank( A) =pthen there exists a unique solution xito the equation Axi=eifori= 1;2; : : : ; p . If we define Bby B= [x1;x2; : : : ;xp] thenAB =I. Similarly there exists a unique solution zito the equation ATzifor i= 1;2; : : : ; p so that if we define CT= [z1;z2; : : : ;zp] thenATCT=IorCA=I. It follows that that C=Bi.e. that A¡1exists. 2 5.2.2 A is nbypof rank p IfAisnbypof rank pwhere p·nthen by theorem 5.3 a unique solution exists and we need only find its form. Since the rank of Aispthe rank of ATAispand hence ATAhas an inverse. Thus if we define x1= (ATA)¡1ATywe have that Ax1=A(ATA)¡1ATy=A(ATA)¡1AT(Ax) =Ax=y so that x1is the unique solution to the equations. 2 5.2.3 A is nbypof rank rwhere r·p·n In this case a solution may not exist and even if a solution exists it may not be unique. Suppose that a matrix A¡can be found such that AA¡A=A 37 Such a matrix A¡is called a generalized inverse ofA If the equations Ax=yhave a solution then x1=Ayis a solution since Ax1=A(A¡y) =AA¡(Ax) =AA¡Ax=Ax=y so that A¡x1is a solution. The general solution is thus obtained by characterizing the solutions to the homogeneous equations i.e. we need to characterize the vectors in the null space of A. Ifzis an arbitrary vector then ( I¡A¡A)zis in the null space of A. The dimension of the set Uwhich can be written in this form is equal to the rank of I¡A¡A. Since (I¡A¡A)2=I¡A¡A¡A¡A+A¡AA¡A =I¡A¡A we see that rank ( I¡A¡A) = tr ( I¡A¡A) =p¡tr (A¡A) =p¡rank ( A¡A)) =p¡rank ( A) =p¡r It follows that Uis of dimension p¡rand hence U=N(A). Thus we have the following theorem Theorem 5.5 IfAisnbypof rank r·p·nthen (1) If a solution exists the general solution is given by x=A¡y+ (I¡A¡A)z where zis an arbitrary pby one vector and A¡is a generalized inverse of A. (2) If x0=Byis a solution to Ax=yfor every yfor which the equations are consistent then Bis a generalized inverse of A. Proof: Since we have established (1) we prove (2) Let y=A`where `is arbitrary. The equations Ax=A`have a solution by assumption which is of the form BA`. It follows thatABA =A`. Since `is arbitrary we have that ABA =Ai.e.Bis a generalized inverse of A.2 38 5.2.4 Generalized Inverses We now establish that a generalized inverse of Aalways exists. Recall that we can find non singular matrices PandQsuch that PAQ =Bi.e.A=P¡1BQ¡1 where Bis given by B=" I O O O# Matrix multiplication shows that BB¡B=Bwhere B¡=" I U V W# where U;VandWare arbitrary. Since A(QB¡P)A=P¡1BQ¡1QB¡PP¡1BQ¡1 =P¡1BQ¡1 =A we see that QB¡Pis a generalized inverse of Aestablishing the existence of a generalized inverse for any matrix. We also note that if PA=" I C O O# Then another generalized inverse of AisB¡Pwhere B¡=" I O O O# æ 39 Chapter 6 Determinants 6.1 Definition and Properties Definition 6.1 LetAbe square matrix with columns fx1;x2; : : : ;xpg. The determi- nant ofAis that function det : Rp!Rsuch that (1) det( x1;x2; : : : ; c xm; : : : ;xp) =cdet(x1;x2; : : : ;xm; : : : ;xp) (2) det( x1;x2; : : : ;xm+xk; : : : ;xp= det( x1;x2; : : : ;xm; : : : ;xp) (3) det( e1;e2; : : : ;ep) = 1 where eiis the ith unit vector. Properties of Determinants (1) If xi=0thenxi= 0xiso that by (1) of the definition det( x1;x2; : : : ;xp) = 0 if xi=0. (2) det( x1;x2; : : : ;xm+cxk; : : : ;xp) = det( x1;x2; : : : ;xm; : : : ;xp). Ifc= 0 this result is trivial. If c6= 0 we note that det(x1;x2; : : : ;xm+cxk; : : : ;xp) = ¡1 cdet(x1;x2; : : : ;xm+cxk; : : : ;¡cxk; : : : ;xp) 40 =¡1 cdet(x1;x2; : : : ;xm; : : : ;¡cxk; : : : ;xp) = det( x1;x2; : : : ;xm; : : : ;xp) (3) If two columns of Aare identical then det = 0. Similarly if the columns of Aare linearly dependent then the determinant of Ais 0. (4) If xkandxmare interchanged then the determinant changes sign i.e. det(x1;x2; : : : ;xm; : : : ;xk; : : : ;xp) =¡det(x1;x2; : : : ;xk; : : : ;xm; : : : ;xp) To prove this we note that det(x1;x2; : : : ;xm; : : : ;xk; : : : ;xp) = det( x1;x2; : : : ;xm+xk; : : : ;xk; : : : ;xp) = det( x1;x2; : : : ;xm+xk; : : : ;xk¡(xm+xk); : : : ;xp) = det( x1;x2; : : : ;xm+xk; : : : ;¡xm; : : : ;xp) = det( x1;x2; : : : ;xk; : : : ;¡xm; : : : ;xp) =¡det(x1;x2; : : : ;xk; : : : ;xm; : : : ;xp) Thus the interchange of an even number of columns does not change the sign of the determinant while the interchange of an odd number of columns does change the sign. (5) det( x1;x2; : : : ;xm+y; : : : ;xp) is equal to det(x1;x2; : : : ;xm; : : : ;xp) + det( x1;x2; : : : ;y; : : : ;xp) If the vectors xifori6=mare dependent the assertion is obvious since both terms are 0. If the xiare linearly independent for i6=mandxm=P icixithe assertion follows by repeated use of (2) and the fact that the first term of the expression is always zero. If the xiare linearly independent then y=P idixiso that det(x1;x2; : : : ;xm+y; : : : ;xp) = det( x1;x2; : : : ;xm+X idixi; : : : ;xp) = det( x1;x2; : : : ; (1 +dm)xm; : : : ;xp) 41 = (1 + dm) det(x1;x2; : : : ;xm; : : : ;xp) = det( x1;x2; : : : ;xp) + det( x1;x2; : : : ; d mxm; : : : ;xp) = det( x1;x2; : : : ;xp) + det( x1;x2; : : : ;X idixi; : : : ;xp) = det( x1;x2; : : : ;xp) + det( x1;x2; : : : ;y; : : : ;xp) Using the above results we can show that the determinant of a matrix is a well defined function of a matrix and give a method for computing the determinant. Since any column vector of A, sayxmcan be written as xm=pX i=1aimei we have that det(x1;x2; : : : ;xp) = det(X i1ai11ei1;x2; : : : ;xp) =X i1ai11det(ei1;x2; : : : ;xp) =X i1ai11X i2ai22det(ei1;ei2; : : : ;xp) =X i1X i2¢¢¢X ipai11ai22¢¢¢aippdet(ei1;ei2; : : : ;eip) Now note that det( ei1;ei2; : : : ;ep) is 0 if any of the subscripts are the same, +1 if i1; i2; : : : ; i pis an even permutation of 1 ;2; : : : ; p and¡1 ifi1; i2; : : : ; i pis an odd per- mutation of 1 ;2; : : : ; p . Hence we can evaluate the determinant of a matrix and it is a uniquely defined function satisfying the conditions (1), (2) and (3). 6.2 Computation The usual method for computing a determinant is to note that if xm=P iaimxithen det(x1;x2; : : : ;xp) =X iaimdet(x1;x2; : : : ;em; : : : ;xp) =X iaimAim 42 where Aim= det( x1;x2; : : : ;em; : : : ;xp) is called the cofactor ofaimand is simply the determinant of Awhen the mth column ofAis replaced by ei. We now note that Aim=X i1X i2¢¢¢X ipai1ai2¢¢¢aipdet(ei1; : : : ;ei; : : : ;eip) Hence Aim= (¡1)i+mdet(Mim) where Mimis the matrix formed by deleting the ith row of Aand the jth column of A. Thus the value of the determinant of a pbypmatrix can be reduced to the calculation ofpdeterminants of p¡1 by p¡1 matrices. The determinant of Mimis called the minor ofaim. æ 43 Chapter 7 Inner Product Spaces 7.1 definitions and Elementary Properties Definition 7.1 Aninner product on a linear vector space Vis a function ( ;) mapping V £ V intoCsuch that 1. (x;x)¸0 with ( x;x) = 0 if and only if x=0. 2. (x;y) =(x;y) 3. (®x+y; vbfz ) =®(x;z) +¯(y;z) A vector space with an inner product is called an inner product space . Definition 7.2: Thenorm orlength ofx,jjxjjis defined by jjxjj2= (x;x) Definition 7.3: The vectors xandyare said to be orthogonal if (x;x) = 0. We write x?yifxis orthogonal to y. More generally (1)xis said to be orthogonal to the set of vectors Xif (x;y) = 0 for every y2 X 44 (2)XandYare said to be orthogonal if (x;y) = 0 for every x2 X andy2 Y Definition 7.4: Xis anorthonormal set of vectors if (x;y) =( 1 ifx=y 0 ifx6=y Xis acomplete orthonormal set of vectors if it is not contained in a larger set of orthonormal vectors. Lemma 7.1 IfXis an orthonormal set then its vectors are linearly independent. Proof: IfP i®ix=0forxi2 X then 0=ÃX i®ixi;xj! =X i®i(xi;xj) =®j It follws that each of the ®jare equal to 0 and hence that the xjs are linearly independent. 2 Lemma 8.2 Letfx1;x2; : : : ;xpgbe an orthonormal basis for X. Then x? X if and only if x?xifori= 1;2; : : : ; p . Proof: Ifx? X then by definition x?xifori= 1;2; : : : ; p . Conversely, if x?xifori= 1;2; : : : ; p . Then if y2 X we have y=P i®ixi. Thus (x;y) =X i¯®i(x;xi) = 0 Thus x? X.2 Theorem 7.3 (Bessel’s Inequality) Let fx1;x2; : : : ;xpgbe an orthonormal set in a linear vector space Vwith an inner product. Then 1.P ij®ij2· jjxjj2where xis any vector in Vand®i= (x;xi). 2. The vector r=x¡P i®ixis orthogonal to each xjand hence to the space spanned byfx1;x2; : : : ;xpg. 45 Proof: We note that jjx¡X i®ixijj2=à x¡X i®ixi;x¡X i®ixi! = (x;x)¡X i(®i(xi;x)¡(x;X i®ixi) + (X i®ixi;X i®ixi) =jjxjj2¡X i®i¯®i¡X i¯®i(x;xi) +X i®i(xi;X i®ixi) =jjxjj2¡2X ij®ij2+X i®i(xi; ®xi) =jjxjj2¡X ij®ij2 Sincejjx¡P i®ixijj2¸0 result (1) follows. For result (2) we note that à x¡X i®ixi;xj! = (x;xj)¡X i®i(x¡i;xj) = (x;xj)¡(x;xj) = 0 2 Theorem 7.4 (Cauchy Schwartz Inequality) If xandyare vectors in an inner product space then j(x;y)j · jjxjj jjyjj Proof: Ify=0equality holds. If y6=0theny jjyjjis orthonormal and by Bessel’s inequality we have ¯¯¯¯¯Ã x;y jjyjj!¯¯¯¯¯2 · jjxjj2orj(x;y)j · jjxjj jjyjj2 Theorem 7.5 IfX=fx1;x2; : : : ;xngis any finite orthonormal set in a vector space V then the following conditions are equivalent: (1)Xis complete. (2) (x;xi) =0fori= 1;2; : : : ; n implies that x=0. 46 (3) The space spanned by Xis equal to V. (4) If x2 Vthenx=P i(x;xi)xi. (5) If xandyare in Vthen (x;y) =X i(x;xi)(xi;y) (6) If x2 Vthen jjxjj2=X ij(xi;x)j2 Result (5) is called Parseval’s identity. Proof: (1) =)(2) IfXis complete and ( x;xi) = 0 for each ithenx jjxjjcould be “added” to the setXwhich would be a contradiction. Thus x=0. (2) =)(3) If xis not a linear combination of the xithenx¡P i(x;xi)xiis not equal toxand is orthogonal to Xwhich is a contradiction. Thus the sapace spanned by Xis equal to V¿ (3) =)(4) If x2 Vwe can write x=P j®jxj. It follows that (x;xi) =X j®j(xj;xi) =®i (4) =)(5) Since x=X i(x;xi)xiandy=X j(y;xj)xj we have (x;y) = (X i(x;xi)xi;X j(y;xj)xj) =X i(x;xi)¯(y;xi) =X i(x;xi)(xi;y) 47 (5) =)(6) In result (5) simply set x=y. (6) =)(1) If xois orthogonal to each xithen by (6) we have jjxojj2=X ij(xi;xo)j2= 0 so that xo=0.2 7.2 Gram Schmidt Process The Gram Schmidt process can be used to construct an orthonormal basis for a finite dimensional vector space. Start with a basis for Vasfx1;x2; : : : ;xng. Form y1=x1 jjx1jj Next define z2=x2¡(x2;y1)y1 Since the xiare linearly independent z26=0andz2is orthogonal to y1. Hence y2=z2 jjz2jj is orthogonal to y1and has unit norm. If y1;y2; : : : ;yrhave been so chosen then we form zr+1=xr+1¡rX i=1(xr+1;yi)yi Since the xiare linearly independent jjzr+1jj>0 and since zr+1?yifori= 1;2; : : : ; r it follows that yr+1=zr+1 jjzr+1jj may be ”added” to the set fy1;y2; : : : ;yrgto form a new orthonormal set. The process necessarily stops with ynsince there can be at most nelements in a linearly independent set.2 48 7.3 Orthogonal Projections Theorem 7.6 (Orthogonal Projection) Let Ube a subspace of an inner product space Vand let ybe a vector in Vwhich is not in U. Then there exists a unique vector yU2 U and and a unique vector e2 Vsuch that y=yU+eande? U Proof: Letfx1;x2; : : : ;xrgbe a basis of U. Since y=2 U the set fx1;x2; : : : ;xr;ygis a linearly independent set. Use the Gram Schmidt process on this set to form a set of orthonormal vectors fy1;y2; : : : ;yr;yr+1g. Since yis in the space spanned by these vectors we can write y=r+1X i=1®iyr=rX i=1®iyr+®r+1yr+1 If we define yU=rX i=1®iyiande=®r+1yr+1 thenYU2 Uande? U. To show uniqueness, suppose that we also have y=z1+e1where z12 U ande1? U Then we have (z1¡yU) + (e1¡e) =0 so that ( z1¡yU;z1¡yU) = 0 and hence z1=yUande1=e.2 Definition 7.4 The vector ein Theorem 7.6 is called the orthogonal projection from ytoUand the vector yUis called the orthogonal projection ofyonU. Theorem 7.7 The projection of yonUhas the property that jjy¡yUjj=minxfjjy¡xjj:x2 Ug Proof: Letx2 UThen ( x¡yU;e) = 0. Hence jjy¡xjj= (y¡x;y¡x) 49 = (y¡yU+yU¡x;y¡yU+yU¡x) =jjy¡yUjj+jjyU¡xjj+ (y¡yU;yU¡x) + (yU¡x;y¡yU) =jjy¡yUjj+jjyU¡xjj ¸ jjy¡yUjj with the minimum occurring when x=yU. Thus the projection minimizes the distance fromUtox.2æ 50 Chapter 8 Characteristic Roots and Vectors 8.1 Definitions Definition 8.1: A scalar ¸is acharacteristic root and a non-zero vector xis a characteristic vector of the matrix Aif Ax=¸x Other names for charateristic roots are proper value, latent root, eigenvalue and secular value with similar adjectives appying to characteristic vectors. If¸is a characteristic root of Alet the set X¸be defined by X¸=fx:Ax=¸xg Thegeometric multiplicity of¸is defined to be the dimension of X¸[ f0g.¸is said to be a simple characteristic root if its geometric multiplicity is 1. Definition 8.2: Thespectrum ofAis the set of all characteristic roots of Aand is denoted by Λ( A) Since Ax=¸xif and only if [ A¡¸]x=0we see that ¸2Λ(A) is equivalent to the set of ¸such that A¡¸I. Similarly xis a characteristic vector corresponding to ¸ 51 if and only xis in the null space of A¡¸I. Using the properties of determinants we have the following Theorem. Theorem 8.1 ¸2Λ(A) if and only if det( A¡¸I) = 0. If the field of scalars is the set of complex numbers (or any algebraically closed field) then if Aispbypwe have det(A¡¸A) =qY i=1(¸¡¸i)ni whereqX i=1=pandni¸1 Thealgebraic multiplicity of the characteristic root ¸iis the number niwhich appears in the above expression. The algebraic and geometric multiplicity of a characteristic root need not correspond. To see this let A=" 1 1 0 1# Then det (A¡¸I) =¯¯¯¯¯1¡¸ 1 0 1 ¡¸¯¯¯¯¯= (¸¡1)2 It follows that both of the characteristic roots of Aare equal to 1. Hence the algebraic multiplicity of the characteristic root 1 is equal to 2. However, the equation Ax=" 1 1 0 1# " x1 x2# =" x1 x2# yields the equations x1+x2=x1 x2=x2 Thus the geometric multiplicity of Ais equal to 1. Lemma 8.2 52 (1) The spectrum of TAT¡1is the same as the spectrum of A. (2) If ¸is a characteristic root of Athen p(¸) is a characteristic root of p(A) where p is any polynomial. Proof: Since TAT¡1¡¸I=T[A¡¸I]T¡1it follows that [ A¡¸I]x=0if and only if [TAT¡1¡¸I]Tx=0and the spectrums are thus the same. IfAx=¸xthenAnx=¸nxfor any integer nso that p(Ax=p(¸)x.2 8.2 Factorizations Theorem 8.3 (Schur’sTriangular Factorization) Let Abe any pbypmatrix. Then there exists a unitary matrix Ui.e.U¤U=Isuch that U¤AU=T where Tis an upper right triangular matrix with diagonal elements equal to the char- acteristic roots of A Proof: Letp= 2 and let u1be such that Au1=¸1u1andu1u1= 0 Define the matrix U= [u1;u2] where u2is chosen so that U¤U=I. Then U¤AU = [u1;u2]¤A[u1;u] =" u¤ 1 u¤ 2# [¸u1;Au2] =" ¸u¤ 1Au2 0u¤ 2Au2# Note that u¤ 2Au2=¸2is the other characteristic root of A. Now assume that the result is true for n=Nand let n=N+ 1. Let Au1=¸1u1andu¤ 1u1= 1 and let fvbfb 1;b2; : : : ;bNgbe such that U1= [u1;b1;b2; : : : ;bN] 53 is unitary. Thus U¤ 1AU 1= [u1;b1;b2; : : : ;bN]A[u1;b1;b2; : : : ;bN] = [u1;b1;b2; : : : ;bN]¤[¸1u1;Ab1;Ab2; : : : ;AbN] =" ¸1u¤ 1Au1¢¢¢u¤ 1AuN 0 B N# Since the characteristic roots of the above matrix are the solutions to the equation (¸1¡¸) det(BN¡¸I) = 0 it follows that the characteristic roots of BNare the remaining characteristic roots ¸1; ¸2; : : : ; ¸ N+1ofA. By the induction assumption there exists a unitary matrix Lsuch that L¤BNL is upper right triangular with diagonal elements equal to ¸1; ¸2; : : : ; ¸ N+1. Let UN+1=" 10T 0 L# andU=U1UN+1 Then U¤AU =U¤ N+1U1AU 1UN+1 =U¤ N+1" ¸1t¤ 0 B N# =" 10T 0 L¤# " ¸1b¤ 0 B N# " 10T 0L# =" ¸1b¤ 0 L¤BNL# which is upper right triangular as claimed with the diagonal elements equal to the characteristic roots of A.2 Theorem 8.4 IfAis normal ( A¤A=AA¤) then there exists a unitary matrix Usuch that U¤AU=D 54 where Dis diagonal with elements equal to the characteristic roots of A. Proof: By Theorem 8.3 there is a unitary matrix Usuch that U¤AU =Twhere Tis upper right triangular. Thus we als have U¤A¤U=T¤where T¤is lower right triangular. It follows that U¤AA¤U=TT¤andU¤A¤AU=T¤T Hence the off diagonal elements of Tvanish i.e. Tis diagonal as claimed. 2 Theorem 8.5 (Cochran’s Theorem) If Ais normal then A=nX i=1¸iEi where E¤ iEj=Ofori6=j;E2 i=Eiand the ¸iare the characteristic roots of A. Proof: By Theorem 8.3 there is a unitary matrix Usuch that U¤AU=Dis diagonal with diagonal elements equal to the characteristic roots of A. Hence A=UDU¤ =U2 66664¸1u¤ 1 ¸2u¤ 2... ¸nu¤ n3 77775 =nX i=1¸iuiu¤ i Defining Ei=uiu¤ icompletes the proof. 2 This representation of Ais called the spectral representation ofA. In most applications Ais symmetric. The spectral representation can be rewritten as A=nX i=1¸iEi=qX j=1¸jEj 55 where ¸1< ¸ 2<¢¢¢< ¸ qare the distinct characteristic roots of A. Now define S0=OandSi=iX j=1Ejfori= 1;2; : : : ; q Then Ei=Si¡Si¡1fori= 1;2; : : : ; q and hence A=qX j=1¸jEj =qX j=1¸j(Sj¡Sj¡1) =qX j=1¸j∆S¸j which may be written as a Stielges integral i.e. A=Z ¸dS(¸) which is also called the spectral representation of A. The spectral representation of Ahas the property that (Ax;y) = (Z ¸dS(¸)x;y) =0 @qX j=1¸j∆S¸jx;y1 A =qX j=1¸j(∆S¸jx;y) =qX j=1¸j[(Sjx;y)¡(Sj¡1x;y)] =Z ¸ d(S(¸)x;y) In more advanced treatments applicable to Hilbert spaces the property just established is taken as the defining property forR¸ d(S(¸). 56 8.3 Quadratic Forms IfAis a symmetric matrix with real elements xTAxis called a quadratic form . A quadratic form is said to be ²positive definite ifxTAx>0 for all x6=0 ²non negative definite ifxTAx¸0 for all x6=0 IfAis positve definite then all of its characteristic roots are positive while if Ais non negative definite then all of its characteristic roots are non negative. To prove this note that if xiis a characteristic vector of Acorresponding to ¸ithenAxi=¸ixiand hence xT iAxi=¸ixT ixi. If¸i6=¸jthen the corresponding characteristic vectors are orthogonal since ¸jxT ixj=xT iAxj= (Axi)xj=¸ixT ixj which implies that xT ixj= 0 i.e. that xiandxjare orthogonal if ¸i6=¸j. Another way of characterizing characteristic roots is to consider the stationary values of XTAx xTx asxvaries over Rp. Since A=pX i=1¸iEi where ¸1¸¸2¸ ¢¢¢ ¸ ¸pwe have that Ax=pX i=1¸iEix It follows that XTAx =pX i=1¸ixTEix 57 =pX i=1¸ixTEiET ix =pX i=1¸ikEixk2 Since Ei=yiyT i, where the yiform an orthonormal basis we have that UTU=Iwhere U= [y1;y2; : : : ;yp] It follows that U¡1=UTand hence that UUT=IThus I=UUT = [y1;y2; : : : ;yp]2 66664y1 y2 ... yp3 77775 =pX i=1yiyp i =pX i=1Ei It follows that xTx=pX i=1xTEix =pX i=1xTEiET ix =pX i=1kEixk2 Thus XTAx xTx=Pp i=1¸ikEixk2 Pp i=1kEixk2 58 Ifxis orthogonal to E1;E2; : : : ;Ekthen XTAx xTx=Pp i=k+1¸ikEixk2 Pp i=k+1kEixk2 and it follows that maximum of XTAx xTx subject to Eix=0fori= 1;2; : : : ; k is¸k+1. Thenorm of a matrix Ais defined as kAk=max fx:kxk 6=0gkAk kxk IfPandQare orthogonal matrices of order n£nandp£prespectively then kPAQk=kAk Lemma 8.6 The characterisitic roots of a Hermitian matrix are real and the character- istic roots of a real symmetric matrix are real. Proof: If¸is a characteristic root of Athen Ax=¸xandx¤A¤=¯¸x¤ Since Ais Hermitian it follows that x¤A¤=x¤A=¯¸x¤ and hence ¸x¤x=¯¸x¤x or¸=¯¸. IfAis a real symmetric matrix it is Hemitian so that the result for real symmetric matrices is true. Lemma 8.7 A necessary and sufficient condition that A=0is that hAx;yi= 0 for all xandy. 59 Theorem 8.8 A necessary and sufficient condition that a symmetric matrix on a real inner product space satisfies A=0is that hAx;xi= 0. Proof: Necessity is obvious. To prove sufficiency we note that hA(x+y);(x+y)i=h(Ax+Ay);(x+y)i :=hAx;xi+hAx;yi+hAy;xi+hAy;yi It follows that hAx;yi+hAy;xi=hA(x+y);(x+y)i ¡ hA(x;(xi ¡ hA(y;(yi Thus the real part of hAxh= 0 since Ais symmetric. Thus hAxh= 0 and by Lemma 8.2 the result follows. 8.4 Jordan Canonical Form The most general canonical form for matrices is the Jordan Canonical Form. This particular canonical form is used in the theory of Markov chains. The Jordan canonical form is a nearly diagonal canonical form for a matrix. Let Jpi(¸i) bepi£pimatrix of the form Jpi(¸i) =¸iIpi+Npi where Npi=2 666666640 1 0 0 ¢¢¢0 0 0 1 0 ¢¢¢0 .................. 0 0 0 0 ¢¢¢1 0 0 0 0 ¢¢¢03 77777775 is a nilpotent matrix of order pii.e.Npipi=0. 60 Theorem 8.9 (Jordan Canonical Form). Let ¸1; ¸2; : : : ; ¸ qbe the qdistinct charac- teristic roots of a p£pmatrix A. Then there exists a non singular matrix Vsuch that VAV¡1= diag³ Jp1;Jp2; : : : ;Jpq´ One use of the Jordan canonical form occurs when we want an expression for An. Using the Jordan canonical form we see that VAnV¡1= diag³ Jn p1;Jn p2; : : : ;Jn pq´ Thus if n¸maxpiwe have Jn pi(¸i) = ( ¸iIpi+Npi)n =X r= 0nÃn r! ¸n¡r iNr pi by the binomial expansion. Since Nr pi=0ifr¸piwe obtain Jn pi(¸i) =pi¡1X r=0Ãn r! ¸n¡r iNr pi Thus for large nwe have a relatively simple expression for An. 8.5 The Singular Value Decomposition (SVD) of a Matrix Theorem 8.10 IfAis any nbypmatrix then there exists matrices U,VandDsuch that A=UDVT where ²UisnbypandUTU=Ip ²VispbypandVTV=Ip 61 ²D= diag ( ¾1; ¾2; : : : ; ¾ p) and ¾1¸¾2¸ ¢¢¢ ¸ ¾p¸0 Proof: Let xbe such that jjxjj= 1 and jjAxjj=jjAjj. That such an xcan be chosen follows from the fact that the norm is a continuous function on a closed and bounded subset of Rnand hence achieves its maximum at a point in the set. Let y1=Axand define y=y1 jjAjj Then jjyjj= 1 and Ax=jjAjjy=¾y where ¾=jjAjj LetU1andV1be such that U= [y; U1] and [ x; V1] are orthogonal where UisnbypandVispbyp. It then follows that UTAV=" yT UT 1# A[x; V1] =" yTAx yTAV1 UT 1AxUT 1AV1# Thus A1=UTAV=" ¾wT 0B1# where wT=yTAV1,B1=UT 1AV1andyTAx=¾yTy=¾ If we define z=A1" ¾ w# =" ¾wT 0B1# " ¾ w# =" ¾2+wTw B1w# Then jjzjj2= [¾2+wTw;wTBT 1]" ¾2+wTw B1w# = (¾2+wTw)2+wTBT 1B1w 62 Thus ¾2=jjAjj2=jjUTAVjj2=jjA1jj2¸(¾2+wTw) and it follows that w=0. Thus UTAV=" ¾0T 0B1# Induction now establishes the result. The orthogonality properties of UandVthen imply that UTAV=D() A=UDVT 8.5.1 Use of the SVD in Data Reduction and Reconstruction LetYbe a data matrix consisting of nobservations on presponse variables. That is Y=2 66664y11y12¢¢¢y1p y21y22¢¢¢y2p ............ yn1yn2¢¢¢ynp3 77775 The singular value decomposition of Yallows us to represent Yas Y=U1D1VT 1 where U1isnbyp,V1ispbypandD1is apbypdiagonal matrix with ithdiagonal element di. We know that di¸0 and we may assume that d1¸d2¸ ¢¢¢ ¸ dp Recall that the matrices U1andV1have the properties UT 1U1=IpandVT 1V1=Ip so that the columns of U1form an orthonormal basis for the column space of Yi.e. the subspace of Rnspanned by the columns of Y. Similarly the columns of V1form an 63 orthonormal basis for the row space of Yi.e. the subspace of Rpspace spanned by the rows of Y. The rows of Yrepresent points in pdimensional space and the yi1; yi2; : : : ; y ip represent the coordinates of the ithindividual’s values relative to the axes of the p original variables. Two individuals are “close” in this space if the distance (norm) between them is “small”. In this case the two individuals have nearly the same values on each of the variables i.e. their coordinates with respect to the original variables are nearly equal. We refer to this subspace of Rpasindividual space orobservation space . The columns of Yrepresent ppoints in Rnand represent the observed values of a variable on nindividuals. Two points in this space are close if they have similar values over the entire collection of observed individuals i.e. the two variables are measuring the same thing. We call this space variable space . The distance between individuals iandi0is given by jjyi¡yi0jj=2 4pX j=1(yij¡yi0j)23 51=2 For any data matrix Ythere is an orthogonal matrix V1such that if Z=YV1then the distances between individuals are preserved i.e. jjzi¡zi0jj=jjyiV1¡yi0V1jj=h (yi¡yi0)TVT 1V1(yi¡yi0)i1=2=jjyi¡yi0jj Thus the original data is replaced by a new data set in which the coordinate axes of the individuals are now the columns of Z. We now note that U1= [u1;u2;¢¢¢;up] where ujis the jthcolumn vector of U1and that V1= [v1;v2;¢¢¢;vp] 64 where vjis the jthcolumn vector of V1. Thus we can write Y=U1DVT 1=pX j=1d2 jujvT j That is we may reconstruct Yas a sum of constants (the d2 j) times matrices which are the outer product of vectors which span variable space (the uj) and individual space (the vj). The interpretation of these vectors is of importance to understanding the nature of the representaion. We note that YYT= (U1D1VT 1)(V1D1UT 1) =U1D2 1UT 1 Thus YYTU1=U1D2 1 which shows that the columns of U1are the eigenvectors of YYTwith eigenvalues equal to the d2 j. We also note that YTY= (V1D1UT 1)(U1D1VT 1) =V1D2 1VT 1 so that YTYV1=V1D2 1 Thus the columns of V1are the eigenvalues of YTYwith eigenvalues again equal to the d2 j. The relationship YV1=U1D1 shows that the columns of V1transform an individual’s values on the original variables to values in the new variables U1with relative importance given by the dj If some of the djare zero or are approximately 0 then we can approximate Yas Y»pX j=1d2 jujvT j which tells us that an approximating subspace has the same dimension in variable space or observation space. æ 65