Linear algebra cheat-sheet - Laurent Lessard

1 Linear algebra cheat-sheetLaurent LessardUniversity of Wisconsin MadisonLast updated: October 12, 2016 Matrix basicsA matrix is an array of Rm nmeans that:A= (mrows andncolumns)Two matrices can be multiplied if inner dimensions agree:C(m p)=A(m n)B(n p)wherecij=n k=1aikbkjTranspose: The transpose operatorATswaps rows andcolumns. IfA Rm nthenAT Rn mand (AT)ij=Aji. (AT)T=A. (AB)T= basics (cont d)Vector products. Ifx,y Rnare column vectors, Theinner productisxTy R( dot product) Theouter productisxyT Rn are just ordinary matrix multiplications!

2 Inverse. LetA Rn n(square). If there existsB Rn nwithAB=IorBA=I(if one holds, then the other holds with thesameB) thenBis called theinverseofA, denotedB=A properties of the matrix inverse: A 1is unique if it exists. (A 1) 1=A. (A 1)T= (AT) 1. (AB) 1=B 1A normsA norm :Rn Ris a function satisfying the properties: x = 0 if and only ifx= 0 (definiteness) cx =|c| x for allc R(homogeneity) x+y x + y (triangle inequality)Common examples of norms: x 1=|x1|+ +|xn|(the 1-norm) x 2= x21+ +x2n(the 2-norm) x = max1 i n|xi|(max-norm)x1x2-11-11norm ball:{x| x = 1}Properties of the 2-norm (Euclidean norm) If you see x , think x 2(it s the default) xTx= x 2 xTy x y (Cauchy-Schwarz inequality)4 Linear independenceA set of vectors{x1.}

3 ,xn} Rmislinearly independentifc1x1+ +cnxn= 0if and only ifc1= =cn= 0If we define the matrixA=[x1 xn] Rm nthen thecolumns ofAare linearly independent ifAw= 0if and only ifw= 0If the vectors are not linearly independent, then they arelinearly dependent. In this case, at least one of the vectorsis redundant (can be expressed as a Linear combination of theothers). there exists akand real numberscisuch thatxk= i6=kcixi5 The rank of a matrixrank(A) = maximum number of linearly independent columnsrank(A) = maximum number of linearly independent rowsIfA Rm nandB Rn pthen rank(A) min(m,n) rank(AB) min(rank(A),rank(B)) min(m,n,p) if rank(A) =nthen rank(AB) = rank(B) if rank(B) =nthen rank(AB) = rank(A)So multiplying by an invertible matrix doesnotalter the properties of the matrix rank.

4 Rank(A+B) rank(A) + rank(B) rank(A) = rank(AT) = rank(ATA) = rank(AAT) A Rn nis invertible if and only if rank(A) = equationsGivenA Rm nandb Rm, Linear equations take the formAx=bWhere we must solve forx Rn. Three possibilities: No solutions. Example:x1+x2= 1 andx1+x2= 0. Exactly one solution. Example:x1= 1 andx2= 0. Infinitely many solutions. Example:x1+x2= common cases: Overdetermined:m>n. Typically no solutions. Oneapproach isleast-squares; findxto minimize Ax b 2. Underdetermined:m<n. Typically infinitely manysolutions. One approach isregularization; find thesolution toAx=bsuch that x 2is as small as squaresWhen the Linear equationsAx=bare overdetermined andthere is no solution, one approach is to find anxthatalmostworks by minimizing the 2-norm of the residual:minimizex Ax b 2(1)This problem always has a solution (not necessarily unique).

5 Xminimizes (1) iff xsatisfies thenormal equations:ATA x=ATbThe normal equations (and therefore (1)) have a uniquesolution iff the columns ofAare linearly independent. Then, x= (ATA) 1 ATb8 Range and nullspaceGivenA Rm n, we have the definitions:Range:R(A) ={Ax|x Rn}. Note:R(A) RmNullspace:N(A) ={x Rn|Ax= 0}. Note:N(A) RnThe following statements are equivalent: Thereexistsa solution to the equationAx=b b R(A) rank(A) = rank([A b])The following statements are equivalent: Solutions to the equationAx=bareunique N(A) ={0} rank(A) =nRemember: rank(A) = dim(R(A))Theorem: rank(A) + dim(N(A)) =n9 Orthogonal matricesA matrixU Rm nisorthogonalifUTU=I.

6 Note that wemust havem n. Some properties of orthogonalUandV: Columns are orthonormal:uTiuj= ij. Orthogonal transformations preserve angles & distances:(Ux)T(Uz) =xTzand Ux 2= x 2. Certain matrix norms are also invariant: UAVT 2= A 2and UAVT F= A F IfUis square,UTU=UUT=IandU 1=UT. UVis subspace has an orthonormal basis: For anyA Rm n,there exists an orthogonalU Rm rsuch thatR(A) =R(U)andr= rank(A). One way to findUis Rn nsatisfiesP2=P, it s called aprojection general,P:Rn S, whereS Rnis a subspace. IfPis aprojection matrix, so is (I P).

7 We can uniquely decompose:x=u+vwhereu S,v S (u=Px,v= (I P)x)Pythagorean theorem: x 22= u 22+ v 22 IfA Rm nhas linearly independent columns, then theprojection ontoR(A) is given byP=A(ATA) :decomposebusing the projection above:b=A(ATA) 1 ATb+ (I A(ATA) 1AT)b=A x+ (b A x)Where x= (ATA) 1 ATbis the LS estimate. Therefore theoptimal residual is orthogonal toA singular value decompositionEveryA Rm ncan be factored asA(m n)=U1(m r) 1(r r)VT1(n r)T(economy SVD)U1is orthogonal, its columns are theleft singular vectorsV1is orthogonal, its columns are theright singular vectors 1is diagonal.

8 1 r>0 are thesingular valuesComplete the orthogonal matrices so they become square:A(m n)=[U1U1](m m)[ 1000](m n)[VT1VT2](n n)=U VT(full SVD)The singular values iare an intrinsic property ofA.(the SVD is not unique, but every SVD ofAhas the same 1)12 Properties of the SVDS ingular vectorsui,viand singular values isatisfyAvi= iuiandATui= iviSupposeA=U VT(full SVD) as in previous slide. rank: rank(A) =r transpose:AT=V UT pseudoinverse:A =V1 11UT1 Fundamental subspaces: R(U1) =R(A) andR(U2) =R(A) (range ofA) R(V1) =N(A) andR(V2) =N(A)(nullspace ofA)Matrix norms: A 2= 1and A F= 21+ + 2r13