10Reviewand miscellaneaType 1: Interchange of two rows.Fori+j,interchangeofrowsi and j ofAresults from leftmultiplication of Aby01...10The two off-diagonal ls are in the i,j and ji positions, the two diagonal Os are inpositions i,i and j, j, and all unspecified entries are O.Type2:Multiplicationof arowbyanonzeroscalar.Multiplication of row i of A by a nonzero scalar c results from left multiplication of AbyThe i,i entry is c, all other main diagonal entries are 1, and all unspecified entriesare 0.Type 3: Addition of a scalar multiple of one row to another row.Fori+j,additionofctimesrowiofAtorowjofAresultsfromleftmultiplicationof A byThej.ientryis c,all maindiagonal entries are,and allunspecifiedentries areO.Thedisplayed matrix illustrates thecasein whichj>i.Thematrices of each of thethreeelementaryrow (or column)operationsare justtheresultof applyingtherespectiveoperationtotheidentitymatrixI (ontheleftforarowoperation; on the right for a column operation).The effect of a type 1operation onthe determinant is to multiply it by-l; the effect of a type 2operation is to multiplyit by the nonzero scalar c; a type3operation does not change thedeterminant.Thedeterminant of a squarematrixwith azero row is zero.The determinant of a squarematrix is zero if and only if some subset of the rows of the matrix is linearly dependent
10 Review and miscellanea Type 1: Interchange of two rows. For i = j, interchange of rows i and j of A results from left multiplication of A by ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 . 0 ··· 1 1 . . . . . . . 1 1 ··· ··· ··· 0 1 . 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ The two off-diagonal 1s are in the i, j and j,i positions, the two diagonal 0s are in positions i,i and j, j, and all unspecified entries are 0. Type 2: Multiplication of a row by a nonzero scalar. Multiplication of row i of A by a nonzero scalar c results from left multiplication of A by ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 . 1 c 1 . 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ The i,i entry is c, all other main diagonal entries are 1, and all unspecified entries are 0. Type 3: Addition of a scalar multiple of one row to another row. For i = j, addition of c times row i of A to row j of A results from left multiplication of A by ⎡ ⎢ ⎢ ⎢ ⎣ 1 . 1 1 c . 1 ⎤ ⎥ ⎥ ⎥ ⎦ The j,i entry is c, all main diagonal entries are 1, and all unspecified entries are 0. The displayed matrix illustrates the case in which j > i. The matrices of each of the three elementary row (or column) operations are just the result of applying the respective operation to the identity matrix I (on the left for a row operation; on the right for a column operation). The effect of a type 1 operation on the determinant is to multiply it by −1; the effect of a type 2 operation is to multiply it by the nonzero scalar c; a type 3 operation does not change the determinant. The determinant of a square matrix with a zero row is zero. The determinant of a square matrix is zero if and only if some subset of the rows of the matrix is linearly dependent
110.3Determinants0.3.4 Reduced row echelon form.To each A=[ai,] EMm.n(F) there correspondsa (unique) canonical form in Mm.n(F),the reduced row echelon form, alsoknown asthe Hermite normal form.If a row of A is nonzero, its leading entry is its first nonzero entry.The definingspecificationsoftheRREFareasfollows:(a)Anyzerorowsoccuratthebottomof thematrix.(b) The leading entry of any nonzero row is a 1.(c) All other entries in the column of a leading entry are zero.(d) The leading entries occur in a stairstep pattern, left to right; that is, if row i isnonzero and aikis its leading entry,then eitheri =m,or rowi+1is zero,or theleading entry in row i +1 is di+1.e, in which l >k.For example,0021S0000元00004100000isinRREFIf R e Mm.n(F) is the RREF of A, then R = EA, in which the nonsingular matrixEMm(F)isaproductoftype1,type2,andtype3elementarymatricescorrespondingtothesequenceofelementaryrowoperationsperformedtoreduceAtoRREFThedeterminantofAEM,(F)isnonzeroifand onlyif itsRREFisI.Thevalueof det Amaybecalculatedby recording theeffects on thedeterminant of each of theelementary operations that lead to the RREF.For the systemoflinearequations Ax=b,with A eMm.n(F)and b eFmgiven andx e F" unknown, the set of solutions is unchanged if the same sequence of elementaryrowoperationsisperformedonbothAandb.ThesolutionsofAx=barerevealedbyinspection of the RREF of [A b]. Since the RREF is unique, for given Ai, A2 E Mm,nand givenbi,b2Fm,thesystems of linearequationsAμx=band A2x=b2havethe same set of solutions if and only if [A bi] and [A2 b2] have the same RREF.0.3.5 Multiplicativity.A key property of the determinant function is that it is multi-plicative: For A, B E M,(F)det AB = det A det BThis may be proved using elementaryoperations that row-reduce both A and B0.3.6 Functional characterization of thedeterminant.If wethink of the deter-minantasafunctionof eachrow(or column)of amatrixseparatelywiththeothersfixed,theLaplaceexpansion(0.3.1.1)revealsthatthedeterminantisalinearfunctionof the entries in any one given row (column).We summarize this propertyby sayingthat the function A -→ det A is multilinear in the rows (columns) of A
0.3 Determinants 11 0.3.4 Reduced row echelon form. To each A = [ai j] ∈ Mm,n(F) there corresponds a (unique) canonical form in Mm,n(F), the reduced row echelon form, also known as the Hermite normal form. If a row of A is nonzero, its leading entry is its first nonzero entry. The defining specifications of the RREF are as follows: (a) Any zero rows occur at the bottom of the matrix. (b) The leading entry of any nonzero row is a 1. (c) All other entries in the column of a leading entry are zero. (d) The leading entries occur in a stairstep pattern, left to right; that is, if row i is nonzero and aik is its leading entry, then either i = m, or row i + 1 is zero, or the leading entry in row i + 1 is ai+1,, in which > k. For example, ⎡ ⎢ ⎢ ⎣ 0 1 −100 2 00 010 π 00 001 4 00 000 0 ⎤ ⎥ ⎥ ⎦ is in RREF. If R ∈ Mm,n(F) is the RREF of A, then R = E A, in which the nonsingular matrix E ∈ Mm(F) is a product of type 1, type 2, and type 3 elementary matrices corresponding to the sequence of elementary row operations performed to reduce A to RREF. The determinant of A ∈ Mn(F) is nonzero if and only if its RREF is In. The value of det A may be calculated by recording the effects on the determinant of each of the elementary operations that lead to the RREF. For the system of linear equations Ax = b, with A ∈ Mm,n(F) and b ∈ Fm given and x ∈ Fn unknown, the set of solutions is unchanged if the same sequence of elementary row operations is performed on both A and b. The solutions of Ax = b are revealed by inspection of the RREF of [A b]. Since the RREF is unique, for given A1, A2 ∈ Mm,n and given b1, b2 ∈ Fm, the systems of linear equations A1x = b1 and A2x = b2 have the same set of solutions if and only if [A1 b1] and [A2 b2] have the same RREF. 0.3.5 Multiplicativity. A key property of the determinant function is that it is multiplicative: For A, B ∈ Mn(F) det AB = det A det B This may be proved using elementary operations that row-reduce both A and B. 0.3.6 Functional characterization of the determinant. If we think of the determinant as a function of each row (or column) of a matrix separately with the others fixed, the Laplace expansion (0.3.1.1) reveals that the determinant is a linear function of the entries in any one given row (column). We summarize this property by saying that the function A → det A is multilinear in the rows (columns) of A
12Review and miscellaneaThe determinant function A-→ det A is the unique function f : Mn(F)-→F that is(a)Multilinear inthe rows of its argument(b) Alternating: any type 1 operation on A changes the sign of f(A)(c) Normalized: f() = 1The permanent function is also multilinear (as are other generalized matrix func-tions),and it is normalized, but it is not alternating.0.4Rank0.4.1Definition.If A EMm.n(F),rank A=dimrangeA is thelength of a longestlinearly independent list of columns of A. There can be more than one linearly in-dependent list of columns whose length equals the rank. It is a remarkable fact thatrank AT =rank A.Therefore, an equivalent definition of rank is the length of a longestlinearly independent list of rows of A:rowrank=column rank.0.4.2 Rank and linear systems. Let A e Mm.n(F) and b e F" be given. The linearsystemAx=bmayhaveno solution,exactlyonesolution,orinfinitelymanysolutions:these are the only possibilities. If there is at least one solution, the linear system isconsistent;if there is no solution, the linear systemis inconsistent.The linear systemAx = b is consistent if and only if rank[A b] = rank A. The matrix [A b] e Mm.n+i(F)is the augmented matrix.To say that the augmented matrix and thecoefficient matrixAofalinearsystemhavethesamerankisjusttosaythatbisalinearcombinationof the columns of A. In this case, appending b to the columns of A does not increasetherank.Asolution of thelinear systemAx=b isavectorx whose entries arethecoefficients in a representation of b as a linear combination of the columns of A.0.4.3RREF and rank.Elementaryoperations do not change the rank of a matrixand thus rank A is the same as the rank of the RREF of A, which is just the number ofnonzerorowsintheRREF.Asapracticalmatter,however,numerical calculationoftherank by calculation of the RREFis unwise.Round-off errors in intermediate numericalcalculationscanmakezerorowsoftheRREFappeartobenonzero,therebyaffectingperception of the rank.0.4.4 Characterizations of rank.The following statements about a given matrixA e Mm.n(F) are equivalent; each can be useful in a different context. Note that in (b)and (c)thekeyissue is linear independence of lists of columns or rows of a matrix:(a) rank A = k.(b) k, and no more than k, rows of A are linearly independent.(c) k, and no more than k, columns of A are linearly independent(d) Some k-by-k submatrix of A has nonzero determinant, and every (k + 1)-by-(k+1) submatrix of Ahas zero determinant.(e) dim(rangeA)=k
12 Review and miscellanea The determinant function A→det A is the unique function f : Mn(F)→ F that is (a) Multilinear in the rows of its argument (b) Alternating: any type 1 operation on A changes the sign of f (A) (c) Normalized: f (I) = 1 The permanent function is also multilinear (as are other generalized matrix functions), and it is normalized, but it is not alternating. 0.4 Rank 0.4.1 Definition. If A ∈ Mm,n(F), rank A = dim range A is the length of a longest linearly independent list of columns of A. There can be more than one linearly independent list of columns whose length equals the rank. It is a remarkable fact that rank AT = rank A. Therefore, an equivalent definition of rank is the length of a longest linearly independent list of rows of A: row rank = column rank. 0.4.2 Rank and linear systems. Let A ∈ Mm,n(F) and b ∈ Fn be given. The linear system Ax = b may have no solution, exactly one solution, or infinitely many solutions; these are the only possibilities. If there is at least one solution, the linear system is consistent; if there is no solution, the linear system is inconsistent. The linear system Ax = b is consistent if and only if rank[A b] = rank A. The matrix [A b] ∈ Mm,n+1(F) is the augmented matrix. To say that the augmented matrix and the coefficient matrix A of a linear system have the same rank is just to say that b is a linear combination of the columns of A. In this case, appending b to the columns of A does not increase the rank. A solution of the linear system Ax = b is a vector x whose entries are the coefficients in a representation of b as a linear combination of the columns of A. 0.4.3 RREF and rank. Elementary operations do not change the rank of a matrix, and thus rank A is the same as the rank of the RREF of A, which is just the number of nonzero rows in the RREF. As a practical matter, however, numerical calculation of the rank by calculation of the RREF is unwise. Round-off errors in intermediate numerical calculations can make zero rows of the RREF appear to be nonzero, thereby affecting perception of the rank. 0.4.4 Characterizations of rank. The following statements about a given matrix A ∈ Mm,n(F) are equivalent; each can be useful in a different context. Note that in (b) and (c) the key issue is linear independence of lists of columns or rows of a matrix: (a) rank A = k. (b) k, and no more than k, rows of A are linearly independent. (c) k, and no more than k, columns of A are linearly independent. (d) Some k-by-k submatrix of A has nonzero determinant, and every (k + 1)-by- (k + 1) submatrix of A has zero determinant. (e) dim (range A) = k
130.4 Rank(f) There are k, but no more than k, linearly independent vectors br, ..., bk such thatthe linear system Ax = b, is consistent for each j = l, ...,k.(g) k = n - dim(nullspace A) (the rank-nullity theorem).(h) k = min(p : A = XYT for some X e Mm.p(F),Y e Mn.p(F).()k=min(p:A=xiy,+...+xpy,)forsomexi,...,XpeF",yi....ypeF".0.4.5Rank inequalities.Some fundamental inequalities involving rank are:(a) If A e Mm.n(F), then rank A ≤ min(m, n).(b)If one or morerows and/or columns aredeleted from a matrix, the rank of theresulting submatrix is not greater than the rank of the original matrix.(c) Sylvester inequality: If A e Mm,(F) and B E Mk.n(F), then(rankA+rank B)-k≤rankAB ≤min(rank A, rank B)(d) The rank-sum inequality: If A, B Mm.n(F), then[rank A - rank BI ≤ rank(A + B) ≤ rank A + rank B(0.4.5.1)with equality in the second inequality if and only if (range A) n (range B) = (0)and(rangeA)n(rangeB)=(O).If rankB=1then(0.4.5.2)rank(A + B) - rank A/ ≤ 1in particular, changing one entry of a matrix can change its rank by at most1.(e) Frobenius inequality: If A e Mm,(F), B e Mk,p(F), and C e Mp,n(F), thenrankAB+rankBC≤rankB+rankABCwith equality if and only if there are matrices X and Y such that B = BCX +YAB.0.4.6 Rank equalities. Some fundamental equalities involving rank are:(a) If A e Mm,n(C), then rank A* = rank AT = rank A = rank A.(b) If A Mm(F)andC eM,(F)arenonsingularandB e Mmn(F),thenrank AB =rankB=rankBC=rankABC;thatis,leftorrightmultiplicationbyanon-singular matrix leaves rank unchanged.(c) If A, B e Mm.n(F), then rank A = rank B if and only if there exist a nonsingularX e Mm(F) and a nonsingular Y e Mn(F) such that B= XAY.(d) If A e Mm,n(C), then rank A*A = rank A.(e) Full-rankfactorization: If A e Mmn(F), then rank A = k if and only if A = XyTfor some X e Mm,(F) and Y e Mn.(F)that each have independent columns. Theequivalent factorization A=X BYT for some nonsingular B e M(F) can alsobe useful. In particular, rank A = 1 if and only if A = xyT for some nonzerovectorsxeF"and y eF".(f) If A e Mm,n(F), then rank A = k if and only if there exist nonsingular matricesS e Mm(F) and T e M,(F) such that A = s[ ]r
0.4 Rank 13 (f) There are k, but no more than k, linearly independent vectors b1,., bk such that the linear system Ax = bj is consistent for each j = 1,., k. (g) k = n − dim(nullspace A) (the rank-nullity theorem). (h) k = min{p : A = XY T for some X ∈ Mm,p(F), Y ∈ Mn,p(F)}. (i) k = min{p : A = x1 yT 1 +···+ x p yT p } for some x1,., x p ∈ Fm, y1,., yp ∈ Fn. 0.4.5 Rank inequalities. Some fundamental inequalities involving rank are: (a) If A ∈ Mm,n(F), then rank A ≤ min{m, n}. (b) If one or more rows and/or columns are deleted from a matrix, the rank of the resulting submatrix is not greater than the rank of the original matrix. (c) Sylvester inequality: If A ∈ Mm,k (F) and B ∈ Mk,n(F), then (rank A + rank B) − k ≤ rank AB ≤ min{rank A,rank B} (d) The rank-sum inequality: If A, B ∈ Mm,n(F), then |rank A − rank B| ≤ rank(A + B) ≤ rank A + rank B (0.4.5.1) with equality in the second inequality if and only if (range A) ∩ (range B) = {0} and (range AT ) ∩ (range BT ) = {0}. If rank B = 1 then | rank(A + B) − rank A| ≤ 1 (0.4.5.2) in particular, changing one entry of a matrix can change its rank by at most 1. (e) Frobenius inequality: If A ∈ Mm,k (F), B ∈ Mk,p(F), and C ∈ Mp,n(F), then rank AB + rank BC ≤ rank B + rank ABC with equality if and only if there are matrices X and Y such that B = BCX + Y AB. 0.4.6 Rank equalities. Some fundamental equalities involving rank are: (a) If A ∈ Mm,n(C), then rank A∗ = rank AT = rank A¯ = rank A. (b) If A ∈ Mm(F) andC ∈ Mn(F) are nonsingular and B ∈ Mm,n(F), then rank AB = rank B = rank BC = rank ABC; that is, left or right multiplication by a nonsingular matrix leaves rank unchanged. (c) If A, B ∈ Mm,n(F), then rank A = rank B if and only if there exist a nonsingular X ∈ Mm(F) and a nonsingular Y ∈ Mn(F) such that B = XAY. (d) If A ∈ Mm,n(C), then rank A∗A = rank A. (e) Full-rank factorization: If A ∈ Mm,n(F), then rank A = k if and only if A = XY T for some X ∈ Mm,k (F) and Y ∈ Mn,k (F) that each have independent columns. The equivalent factorization A = XBY T for some nonsingular B ∈ Mk (F) can also be useful. In particular, rank A = 1 if and only if A = x yT for some nonzero vectors x ∈ Fm and y ∈ Fn. (f) If A ∈ Mm,n(F), then rank A = k if and only if there exist nonsingular matrices S ∈ Mm(F) and T ∈ Mn(F) such that A = S Ik 0 0 0 T
14Review and miscellanea(g) Let A e Mm.n(F). If X e Mn.(F) and Y e Mm,(F), and if W = yT AX is non-singular, thenrank(A-AXW-IyTA)=rankA-rankAXW-lyTA(0.4.6.1)When k = 1, this is Wedderburn's rank-one reduction formula: If x e F" andy eF",and ifw=yT Ar+ o, thenrank (A - @-I AxyT A) = rank A - 1(0.4.6.2)Conversely, if eF, u e F", ueF", and rank(A-ouu)< rank A, thenrank(A-αuuT)= rank A-1 and there are x e F" and y e F" such thatu = Ax, = A y, y Ax 0, and o = (yT Ax)-1.0.5NonsingularityA linear transformation or matrix is said to be nonsingular if it produces the output oonly for the input O. Otherwise, it is singular. If A e Mm,n(F) and m < n, then A isnecessarily singular. An A e Mn(F) is invertible if there is a matrix A- e Mn(F) (theinverse of A) such that A-'A=I.If A e M, and A-IA=I,then AA-I =I; that is,A- is a left inverse if and only if it is a right inverse; A-l is unique whenever it exists.It is useful to be able to call on a variety of criteria for a square matrix to benonsingular.Thefollowing are equivalentfor a given AeM,(F):(a) A is nonsingular.(b) A-1l exists.(c) rank A = n.(d) The rows of A are linearly independent(e)The columns of A are linearly independent(f) det A 0(g) The dimension of the range of A is n(h)The dimension of the null space of A is 0.(i)Ax =b is consistent for each b eFn.G) If Ax = b is consistent, then the solution is unique.(k) Ax =b has a unique solution for each b eF"() The only solution to Ax = 0 is x = 0.(m) 0 is not an eigenvalue of A (see Chapter 1).The conditions (g) and (h) are equivalent for a linear transformation T : V→V ona finite dimensional vector space V; that is,Tx=y has a solution x for every y Vif and only if the only x such that Tx = O is x = O if and only if Tx =y has a uniquesolutionxforeveryy eV.The nonsingular matrices in M,(F)form a group,thegeneral lineargroup,oftendenoted by GL(n, F).If A e Mn(F)is nonsingular, then (A-I) AT)T = A(A-I) = I, so(A-I)T AT = I,whichmeans that(A-1)T=(AT)-1.It is convenient to write either (A-1)T or(A)-)as A-T.If A E M,(C) is nonsingular, then (A-')*=(A*)-1,and we may safely writeeither as A-*
14 Review and miscellanea (g) Let A ∈ Mm,n(F). If X ∈ Mn,k (F) and Y ∈ Mm,k (F), and if W = Y T AX is nonsingular, then rank(A − AXW−1 Y T A) = rank A − rank AXW−1 Y T A (0.4.6.1) When k = 1, this is Wedderburn’s rank-one reduction formula: If x ∈ Fn and y ∈ Fm, and if ω = yT Ax = 0, then rank A − ω−1AxyT A = rank A − 1 (0.4.6.2) Conversely, if σ ∈ F, u ∈ Fn, v ∈ Fm, and rank A − σuvT < rank A, then rank A − σuvT = rank A − 1 and there are x ∈ Fn and y ∈ Fm such that u = Ax, v = AT y, yT Ax = 0, and σ = (yT Ax) −1. 0.5 Nonsingularity A linear transformation or matrix is said to be nonsingular if it produces the output 0 only for the input 0. Otherwise, it is singular. If A ∈ Mm,n(F) and m < n, then A is necessarily singular. An A ∈ Mn(F) is invertible if there is a matrix A−1 ∈ Mn(F) (the inverse of A) such that A−1A = I. If A ∈ Mn and A−1A = I, then AA−1 = I; that is, A−1 is a left inverse if and only if it is a right inverse; A−1 is unique whenever it exists. It is useful to be able to call on a variety of criteria for a square matrix to be nonsingular. The following are equivalent for a given A ∈ Mn(F): (a) A is nonsingular. (b) A−1 exists. (c) rank A = n. (d) The rows of A are linearly independent. (e) The columns of A are linearly independent. (f) det A = 0. (g) The dimension of the range of A is n. (h) The dimension of the null space of A is 0. (i) Ax = b is consistent for each b ∈ Fn. (j) If Ax = b is consistent, then the solution is unique. (k) Ax = b has a unique solution for each b ∈ Fn. (l) The only solution to Ax = 0 is x = 0. (m) 0 is not an eigenvalue of A (see Chapter 1). The conditions (g) and (h) are equivalent for a linear transformation T : V → V on a finite dimensional vector space V; that is, T x = y has a solution x for every y ∈ V if and only if the only x such that T x = 0 is x = 0 if and only if T x = y has a unique solution x for every y ∈ V. The nonsingular matrices in Mn(F) form a group, the general linear group, often denoted by G L(n, F). If A ∈ Mn(F) is nonsingular, then ((A−1) T AT ) T = A(A−1) = I, so (A−1) T AT = I, which means that (A−1) T = (AT ) −1. It is convenient to write either (A−1) T or (AT ) −1 as A−T . If A ∈ Mn(C) is nonsingular, then (A−1) ∗ = (A∗) −1, and we may safely write either as A−∗