LINEAR ALGEBRA with A:= A22-A21 A11 A12, and A is nonsingular iff A is nonsingular. Dually, if A22 A1141 IA12A21[△0 A21A22 12A21I with A: =Al1-A12 A22 A21, and A is nonsingular iff A is nonsingular. The matrix A (A) is called the Schur complement of All(A22)in A Moreover, if A is nonsingular, then A21A22 △-1A2141 A11A12 124-1 22 A2A214-1A2+A22A214-1412 The preceding matrix inversion formulas are particularly simple if A is block trian- A 0 att A21A2 -A242141A2 12 0A22 Aoo The following identity is also very useful. Suppose All and A22 are both ne matrices: then (A1-A12A242)-1=A1+A11A12(22-A21A1A12)-1A2141 As a consequence of the matrix decomposition formulas mentioned previously, an calculate the determinant of a matrix by using its submatrices. Suppose All is nonsingular: then det a=det All det(A22-A21 A11 A12) On the other hand, if A22 is nonsingular, then det A= det A22 det(A11-A12A22 A21). In particular, for any B E cmxn and CE Cnxm, we have I det(In +CB)=det(Im BC) nd for z,y∈ det(In+xy)=1+y’x Related MATLAB Commands: inv, det
14 LINEAR ALGEBRA with ∆ := A22 − A21A−1 11 A12, and A is nonsingular iff ∆ is nonsingular. Dually, if A22 is nonsingular, then A11 A12 A21 A22 = I A12A−1 22 0 I ∆ 0 ˆ 0 A22 I 0 A−1 22 A21 I with ∆ := ˆ A11 − A12A−1 22 A21, and A is nonsingular iff ∆ is nonsingular. The matrix ∆ ˆ (∆) is called the ˆ Schur complement of A11 (A22) in A. Moreover, if A is nonsingular, then A11 A12 A21 A22 −1 = A−1 11 + A−1 11 A12∆−1A21A−1 11 −A−1 11 A12∆−1 −∆−1A21A−1 11 ∆−1 and A11 A12 A21 A22 −1 = ∆ˆ −1 −∆ˆ −1A12A−1 22 −A−1 22 A21∆ˆ −1 A−1 22 + A−1 22 A21∆ˆ −1A12A−1 22 . The preceding matrix inversion formulas are particularly simple if A is block triangular: A11 0 A21 A22 −1 = A−1 11 0 −A−1 22 A21A−1 11 A−1 22 A11 A12 0 A22 −1 = A−1 11 −A−1 11 A12A−1 22 0 A−1 22 . The following identity is also very useful. Suppose A11 and A22 are both nonsingular matrices; then (A11 − A12A−1 22 A21) −1 = A−1 11 + A−1 11 A12(A22 − A21A−1 11 A12) −1A21A−1 11 . As a consequence of the matrix decomposition formulas mentioned previously, we can calculate the determinant of a matrix by using its submatrices. Suppose A11 is nonsingular; then det A = det A11 det(A22 − A21A−1 11 A12). On the other hand, if A22 is nonsingular, then det A = det A22 det(A11 − A12A−1 22 A21). In particular, for any B ∈ Cm×n and C ∈ Cn×m, we have det Im B −C In = det(In + CB) = det(Im + BC) and for x,y ∈ Cn det(In + xy∗)=1+ y∗x. Related MATLAB Commands: inv, det
2.4. Invariant Subspaces 2.4 Invariant Subspaces Let a: c Cn be a linear transformation, a be an eigenvalue of A, and a be a corresponding eigenvector, respectively. Then AT Ar and A(ar)= A(oz) for any a C. Clearly, the eigenvector r defines a one-dimensional subspace that is invariant with respect to premultiplication by A since Ar= Ar, Vk. In general, a subspace SCCn is called invariant for the transformation A, or A-invariant, if Ar E S for every r E S. In other words, that S is invariant for A means that the image of S under A is contained in S: AS CS. For example, 101, Cn, Ker A, and ImA are all A-invariant subspaces As a generalization of the one-dimensional invariant subspace induced by an eigen vector, let A1, .. Ak be eigenvalues of A (not necessarily distinct), and let Ti be the cor- responding eigenvectors and the generalized eigenvectors. Then S=spana,.. IkJ is an A-invariant subspace provided that all the lower-rank generalized eigenvector are included. More specifically, let A1=A2 ai be eigenvalues of A, and let 51, 2,.. aI be the corresponding eigenvector and the generalized eigenvectors ob- tained through the following equations: (4-A1D)x1 (A-A1I)r (A-A1l)al Then a subspace S with at E S for somet I is an A-invariant subspace only if all lower rank eigenvectors and generalized eigenvectors of Tt are in S(i.e.,x;∈S.Ⅵ≤i≤t) This will be further illustrated in Example 2.1 On the other hand, if S is a nontrivial subspace and is A-invariant, then there is r E S and A such that A= Ar An A-invariant subspace s c cn is called a stable invariant subspace if all the eigenvalues of A constrained to S have negative real parts. Stable invariant subspaces will play an important role in computing the stabilizing solutions to the algebraic Riccati equations in Chapter 12 2.1 Suppose a matrix A has the following Jordan canonical form A[1 I2 I3 I4]=[T1 T2 I] IA] will say subspace S is trivial if S=
2.4. Invariant Subspaces 15 2.4 Invariant Subspaces Let A : Cn 7−→ Cn be a linear transformation, λ be an eigenvalue of A, and x be a corresponding eigenvector, respectively. Then Ax = λx and A(αx) = λ(αx) for any α ∈ C. Clearly, the eigenvector x defines a one-dimensional subspace that is invariant with respect to premultiplication by A since Akx = λkx, ∀k. In general, a subspace S ⊂ Cn is called invariant for the transformation A, or A-invariant, if Ax ∈ S for every x ∈ S. In other words, that S is invariant for A means that the image of S under A is contained in S: AS ⊂ S. For example, {0}, Cn, KerA, and ImA are all A-invariant subspaces. As a generalization of the one-dimensional invariant subspace induced by an eigenvector, let λ1,...,λk be eigenvalues of A (not necessarily distinct), and let xi be the corresponding eigenvectors and the generalized eigenvectors. Then S = span{x1,...,xk} is an A-invariant subspace provided that all the lower-rank generalized eigenvectors are included. More specifically, let λ1 = λ2 = ··· = λl be eigenvalues of A, and let x1,x2,...,xl be the corresponding eigenvector and the generalized eigenvectors obtained through the following equations: (A − λ1I)x1 = 0 (A − λ1I)x2 = x1 . . . (A − λ1I)xl = xl−1. Then a subspace S with xt ∈ S for some t ≤ l is an A-invariant subspace only if all lowerrank eigenvectors and generalized eigenvectors of xt are in S (i.e., xi ∈ S, ∀1 ≤ i ≤ t). This will be further illustrated in Example 2.1. On the other hand, if S is a nontrivial subspace1 and is A-invariant, then there is x ∈ S and λ such that Ax = λx. An A-invariant subspace S ⊂ Cn is called a stable invariant subspace if all the eigenvalues of A constrained to S have negative real parts. Stable invariant subspaces will play an important role in computing the stabilizing solutions to the algebraic Riccati equations in Chapter 12. Example 2.1 Suppose a matrix A has the following Jordan canonical form: A x1 x2 x3 x4 = x1 x2 x3 x4 λ1 1 λ1 λ3 λ4 1We will say subspace S is trivial if S = {0}.
LINEAR ALGEBRA with ReA1 <0, A3<0, and A4>0. Then it is easy to verify that S n 1 S1 anIl,12 S1 span-C1, 12, I3) spans S1 spana, 13 $124= span r1, r2, T4l span aA S14= span(J1, I4) S: spana, T4l are all A-invariant subspaces. Moreover, S1, S3, S12, S13, and S123 are stable A-invariant $234=span([2, T3, I4) are, however, not A-invariant subspaces since the 2, t4. and subspaces. The subspaces S2= span=21, $23= span a2, I3, S24= spant eigenvector Ti is not in these subspaces. To illustrate, consider the subspace $23. Then by definition, AT2 E S23 if it is an A-invariant subspace. Since Az2 E S23 would require that ai be a linear combination of 2 and a3, but this is impossible since T1 is independent of 2 and T3 2.5 Vector Norms and matrix norms In this section, we shall define vector and matrix norms. Let X be a vector space. A real-valued function l defined on X is said to be a norm on X if it satisfies the wing properties (i)‖l≥0( positivity); (ii)a=0 if and only if a=0(positive definiteness) (iii)aa=al al, for any scalar a(homogeneity); (iv)|x+列≤‖xl+lyl!( triangle inequality) for any D∈ X and y∈X Let z EC". Then we define the vector p-norm of a as /p zP,frl≤p<∞ In particular, whe 2. oo we have 2:=1∑|
16 LINEAR ALGEBRA with Reλ1 < 0, λ3 < 0, and λ4 > 0. Then it is easy to verify that S1 = span{x1} S12 = span{x1,x2} S123 = span{x1,x2,x3} S3 = span{x3} S13 = span{x1,x3} S124 = span{x1,x2,x4} S4 = span{x4} S14 = span{x1,x4} S34 = span{x3,x4} are all A-invariant subspaces. Moreover, S1,S3,S12,S13, and S123 are stable A-invariant subspaces. The subspaces S2 = span{x2}, S23 = span{x2,x3}, S24 = span{x2,x4}, and S234 = span{x2,x3,x4} are, however, not A-invariant subspaces since the lower-rank eigenvector x1 is not in these subspaces. To illustrate, consider the subspace S23. Then by definition, Ax2 ∈ S23 if it is an A-invariant subspace. Since Ax2 = λx2 + x1, Ax2 ∈ S23 would require that x1 be a linear combination of x2 and x3, but this is impossible since x1 is independent of x2 and x3. 2.5 Vector Norms and Matrix Norms In this section, we shall define vector and matrix norms. Let X be a vector space. A real-valued function k·k defined on X is said to be a norm on X if it satisfies the following properties: (i) kxk ≥ 0 (positivity); (ii) kxk = 0 if and only if x = 0 (positive definiteness); (iii) kαxk = |α| kxk, for any scalar α (homogeneity); (iv) kx + yk≤kxk + kyk (triangle inequality) for any x ∈ X and y ∈ X. Let x ∈ Cn. Then we define the vector p-norm of x as kxkp := Xn i=1 |xi| p !1/p , for 1 ≤ p < ∞. In particular, when p = 1, 2,∞ we have kxk1 := Xn i=1 |xi|; kxk2 := vuutXn i=1 |xi| 2;
2.5. Vector Norms and matrix norms Clearly, norm is an abstraction and extension of our usual concept of length in three- dimensional Euclidean space. So a norm of a vector is a measure of the vector "length (for example, zl2 is the Euclidean distance of the vector z from the origin). Similarly, we can introduce some kind of measure for a matrix Let A=Oiil e cmxn; then the matrix norm induced by a vector p-norm is defined IAl:=SuPp zIp The matrix norms induced by vector p-norms are sometimes called induced p-norms This is because lAllp is defined by or induced from a vector p-norm. In fact, A can be viewed as a mapping from a vector space Cn equipped with a vector norm .l,to another vector space cm equipped with a vector norm lI- l,. So from a system theoretical point of view, the induced norms have the interpretation of input/output amplification In particular, the induced matrix 2-norm can be computed as ‖A|2=√Amax(A*A We shall adopt the following convention throughout this book for the vector and atria norms unless specified otherwise: Let a E Cn and A E cmxn; then we shall denote the euclidean 2-norm of r simply by -‖:=‖xl and the induced 2-norm of a by ‖A‖:=‖4‖2 The Euclidean 2-norm has some very nice properties Lemma2.2Letx∈ F"and y∈Fn 1. Suppose n≥m.Then‖l‖= yll iff there is a matriT U∈ Fnx such that ar=Uy andUO=l 2. Suppose n=m. Then a引≤‖x‖ly. Moreover, the equality holds iff a=ay for some a∈Fory=0. 3.‖‖≤‖l‖ iff there is a matria△∈Fn× with‖△‖≤1 such that z=△y Furthermore,‖-< lyll if‖‖<1. 4.‖Ux‖=|l‖ for any appropriately dimensioned unitary matrices U
2.5. Vector Norms and Matrix Norms 17 kxk∞ := max 1≤i≤n |xi|. Clearly, norm is an abstraction and extension of our usual concept of length in threedimensional Euclidean space. So a norm of a vector is a measure of the vector “length” (for example, kxk2 is the Euclidean distance of the vector x from the origin). Similarly, we can introduce some kind of measure for a matrix. Let A = [aij ] ∈ Cm×n; then the matrix norm induced by a vector p-norm is defined as kAkp := sup x6=0 kAxkp kxkp . The matrix norms induced by vector p-norms are sometimes called induced p-norms. This is because kAkp is defined by or induced from a vector p-norm. In fact, A can be viewed as a mapping from a vector space Cn equipped with a vector norm k·kp to another vector space Cm equipped with a vector norm k·kp. So from a system theoretical point of view, the induced norms have the interpretation of input/output amplification gains. In particular, the induced matrix 2-norm can be computed as kAk2 = pλmax(A∗A). We shall adopt the following convention throughout this book for the vector and matrix norms unless specified otherwise: Let x ∈ Cn and A ∈ Cm×n; then we shall denote the Euclidean 2-norm of x simply by kxk := kxk2 and the induced 2-norm of A by kAk := kAk2 . The Euclidean 2-norm has some very nice properties: Lemma 2.2 Let x ∈ Fn and y ∈ Fm. 1. Suppose n ≥ m. Then kxk = kyk iff there is a matrix U ∈ Fn×m such that x = Uy and U∗U = I. 2. Suppose n = m. Then |x∗y|≤kxk kyk. Moreover, the equality holds iff x = αy for some α ∈ F or y = 0. 3. kxk≤kyk iff there is a matrix ∆ ∈ Fn×m with k∆k ≤ 1 such that x = ∆y. Furthermore, kxk < kyk iff k∆k < 1. 4. kUxk = kxk for any appropriately dimensioned unitary matrices U
LINEAR ALGEBRA Another often used matrix norm is the so called Frobenius nor. It is defined as AllE AA=,∑∑laP However, the frobenius norm is not an induced norm. The following properties of matrix norms are easy to show: Lemma 2.3 Let A and b be any matrices with appropriate dimensions. Then 1.p(4)≤‖A‖( this is also true for the F- norm and any induced matrit norm) 2.AB≤‖4B. In particular, this gives I-1≥‖4-1 if a is invertible (This is also true for any induced matriz norm. 3.|UAV‖=‖4,and| UAVlF=‖A‖p, for any appropriately dimm 4.‖AB‖p≤‖A‖ BllF and‖AB‖p≤‖B‖‖Ap Note that although premultiplication or postmultiplication of a unitary matrix on matrix does not change its induced 2-norm and F-norm, it does change its eigenvalues or example, let 0 0 Then A1(A)=1, A2(A)=0. Now let then U is a unitary matrix and 2 with A1(U A)=v2, A2(U A)=0. This property is useful in some matrix perturbation problems, particularly in the computation of bounds for structured singular value which will be studied in Chapter 9 Related MATLAB Commands: norm, normest
18 LINEAR ALGEBRA Another often used matrix norm is the so called Frobenius norm. It is defined as kAkF := ptrace(A∗A) = vuutXm i=1 Xn j=1 |aij | 2 . However, the Frobenius norm is not an induced norm. The following properties of matrix norms are easy to show: Lemma 2.3 Let A and B be any matrices with appropriate dimensions. Then 1. ρ(A) ≤ kAk (this is also true for the F-norm and any induced matrix norm). 2. kABk≤kAk kBk. In particular, this gives A−1 ≥ kAk−1 if A is invertible. (This is also true for any induced matrix norm.) 3. kUAV k = kAk, and kUAV kF = kAkF , for any appropriately dimensioned unitary matrices U and V . 4. kABkF ≤ kAk kBkF and kABkF ≤ kBk kAkF . Note that although premultiplication or postmultiplication of a unitary matrix on a matrix does not change its induced 2-norm and F-norm, it does change its eigenvalues. For example, let A = 1 0 1 0 . Then λ1(A)=1,λ2(A) = 0. Now let U = " √ 1 2 √ 1 2 − √ 1 2 √ 1 2 # ; then U is a unitary matrix and UA = √2 0 0 0 with λ1(UA) = √ 2, λ2(UA) = 0. This property is useful in some matrix perturbation problems, particularly in the computation of bounds for structured singular values, which will be studied in Chapter 9. Related MATLAB Commands: norm, normest