Linear Algebra Review and Reference Zico Kolter (updated by Chuong Do) October 7.2008 Contents 1 Basic Concepts and Notation 2 l.1 Basic Notation...···.········· 2 2 Matrix Multiplication 3 2.1 Vector-Vector Products... 4 2.2 Matrix-Vector Products 4 2.3 Matrix-Matrix Products 5 3 Operations and Properties 个 3.1 The Identity Matrix and Diagonal Matrices 8 3.2 The Transpose·········· 8 3.3 Symmetric Matrices..·..·. 8 3.4 The Trace..········· 9 3.5 Norms.····· 10 3.6 Linear Independence and Rank 11 3.7 The Inverse·.:..······· 11 3.8 Orthogonal Matrices...................·.··.. 12 3.9 Range and Nullspace of a Matrix 12 3.l0 The Determinant.·.·. 14 3.11 Quadratic Forms and Positive Semidefinite Matrices.......··· 17 3.12 Eigenvalues and Eigenvectors... 18 3.13 Eigenvalues and Eigenvectors of Symmetric Matrices 19 4 Matrix Calculus 20 4.1 The Gradient 20 4.2 The Hessian.. 2 4.3 Gradients and Hessians of Quadratic and Linear Functions 23 4.4 Least☒Squares...............······· 5 4.5 Gradients of the Determinant 25 4.6 Eigenvalues as Optimization ... 26
Linear Algebra Review and Reference Zico Kolter (updated by Chuong Do) October 7, 2008 Contents 1 Basic Concepts and Notation 2 1.1 Basic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Matrix Multiplication 3 2.1 Vector-Vector Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Matrix-Vector Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Matrix-Matrix Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Operations and Properties 7 3.1 The Identity Matrix and Diagonal Matrices . . . . . . . . . . . . . . . . . . 8 3.2 The Transpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Symmetric Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.4 The Trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.5 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.6 Linear Independence and Rank . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.7 The Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.8 Orthogonal Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.9 Range and Nullspace of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . 12 3.10 The Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.11 Quadratic Forms and Positive Semidefinite Matrices . . . . . . . . . . . . . . 17 3.12 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.13 Eigenvalues and Eigenvectors of Symmetric Matrices . . . . . . . . . . . . . 19 4 Matrix Calculus 20 4.1 The Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2 The Hessian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 Gradients and Hessians of Quadratic and Linear Functions . . . . . . . . . . 23 4.4 Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.5 Gradients of the Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.6 Eigenvalues as Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1
1 Basic Concepts and Notation Linear algebra provides a way of compactly representing and operating on sets of linear equations.For example,consider the following system of equations: 4x1-5x2=-13 -2x1+3x2=9. This is two equations and two variables,so as you know from high school algebra,you can find a unique solution for x and z2(unless the equations are somehow degenerate,for example if the second equation is simply a multiple of the first,but in the case above there is in fact a unique solution).In matrix notation,we can write the system more compactly as Ax=b with 4=[4],=[] As we will see shortly,there are many advantages (including the obvious space savings) to analyzing linear equations in this form. 1.1 Basic Notation We use the following notation: By A E Rmxn we denote a matrix with m rows and n columns,where the entries of A are real numbers. By z E R",we denote a vector with n entries.By convention,an n-dimensional vector is often thought of as a matrix with n rows and 1 column,known as a column vector. If we want to explicitly represent a row vector-a matrix with 1 row and n columns -we typically write zT(here aT denotes the transpose of x,which we will define shortly). The ith element of a vector x is denoted xi: T1 T= In 2
1 Basic Concepts and Notation Linear algebra provides a way of compactly representing and operating on sets of linear equations. For example, consider the following system of equations: 4x1 − 5x2 = −13 −2x1 + 3x2 = 9. This is two equations and two variables, so as you know from high school algebra, you can find a unique solution for x1 and x2 (unless the equations are somehow degenerate, for example if the second equation is simply a multiple of the first, but in the case above there is in fact a unique solution). In matrix notation, we can write the system more compactly as Ax = b with A = 4 −5 −2 3 , b = −13 9 . As we will see shortly, there are many advantages (including the obvious space savings) to analyzing linear equations in this form. 1.1 Basic Notation We use the following notation: • By A ∈ R m×n we denote a matrix with m rows and n columns, where the entries of A are real numbers. • By x ∈ R n , we denote a vector with n entries. By convention, an n-dimensional vector is often thought of as a matrix with n rows and 1 column, known as a column vector. If we want to explicitly represent a row vector — a matrix with 1 row and n columns — we typically write x T (here x T denotes the transpose of x, which we will define shortly). • The ith element of a vector x is denoted xi : x = x1 x2 . . . xn . 2
We use the notation aii (or Ai,Aii,etc)to denote the entry of A in the ith row and jth column: a11 012··· ain a21 a22 a2n A= aml am2 amn We denote the ith column of A by aj or A.j: … We denote the ith row of A by af or Ai.:: A= Note that these definitions are ambiguous (for example,the a and af in the previous two definitions are not the same vector).Usually the meaning of the notation should be obvious from its use. 2 Matrix Multiplication The product of two matrices AE Rmxn and BERnxp is the matrix C=AB∈RmxP, where C,=∑AkB k=1 Note that in order for the matrix product to exist,the number of columns in A must equal the number of rows in B.There are many ways of looking at matrix multiplication,and we'll start by examining a few special cases. 3
• We use the notation aij (or Aij , Ai,j , etc) to denote the entry of A in the ith row and jth column: A = a11 a12 · · · a1n a21 a22 · · · a2n . . . . . . . . . . . . am1 am2 · · · amn . • We denote the jth column of A by aj or A:,j : A = | | | a1 a2 · · · an | | | . • We denote the ith row of A by a T i or Ai,: : A = — a T 1 — — a T 2 — . . . — a T m — . • Note that these definitions are ambiguous (for example, the a1 and a T 1 in the previous two definitions are not the same vector). Usually the meaning of the notation should be obvious from its use. 2 Matrix Multiplication The product of two matrices A ∈ R m×n and B ∈ R n×p is the matrix C = AB ∈ R m×p , where Cij = Xn k=1 AikBkj . Note that in order for the matrix product to exist, the number of columns in A must equal the number of rows in B. There are many ways of looking at matrix multiplication, and we’ll start by examining a few special cases. 3
2.1 Vector-Vector Products Given two vectors r,ye R",the quantity ry,sometimes called the inner product or dot product of the vectors,is a real number given by 1 2 x'y∈R=[x12·cn : Tiyi i=l Observe that inner products are really just special case of matrix multiplication.Note that it is always the case that aTy=yTc. Given vectors E R,yE R(not necessarily of the same size),xyTE Rmxn is called the outer product of the vectors.It is a matrix whose entries are given by (y)=ij, i.e., T1 T141 T142 ··1yn xyT∈Rmxn T2 E21 E22 T2Un 1 2· m]= Imy1 Tmy2 TmYn As an example of how the outer product can be useful,let 1 ER"denote an n-dimensional vector whose entries are all equal to 1.Furthermore,consider the matrix A E Rmxn whose columns are all equal to some vector xE Rm.Using outer products,we can represent A compactly as, T1 --小 2 2 T2 2 [11 1]=x1 工m m 2.2 Matrix-Vector Products Given a matrix A E Rmxn and a vector x E R",their product is a vector y=Ax E Rm. There are a couple ways of looking at matrix-vector multiplication,and we will look at each of them in turn. If we write A by rows,then we can express Ax as, x Ax= 4
2.1 Vector-Vector Products Given two vectors x, y ∈ R n , the quantity x T y, sometimes called the inner product or dot product of the vectors, is a real number given by x T y ∈ R = x1 x2 · · · xn y1 x2 . . . yn = Xn i=1 xiyi . Observe that inner products are really just special case of matrix multiplication. Note that it is always the case that x T y = y T x. Given vectors x ∈ R m, y ∈ R n (not necessarily of the same size), xyT ∈ R m×n is called the outer product of the vectors. It is a matrix whose entries are given by (xyT )ij = xiyj , i.e., xyT ∈ R m×n = x1 x2 . . . xm y1 y2 · · · yn = x1y1 x1y2 · · · x1yn x2y1 x2y2 · · · x2yn . . . . . . . . . . . . xmy1 xmy2 · · · xmyn . As an example of how the outer product can be useful, let 1 ∈ R n denote an n-dimensional vector whose entries are all equal to 1. Furthermore, consider the matrix A ∈ R m×n whose columns are all equal to some vector x ∈ R m. Using outer products, we can represent A compactly as, A = | | | x x · · · x | | | = x1 x1 · · · x1 x2 x2 · · · x2 . . . . . . . . . . . . xm xm · · · xm = x1 x2 . . . xm 1 1 · · · 1 = x1 T . 2.2 Matrix-Vector Products Given a matrix A ∈ R m×n and a vector x ∈ R n , their product is a vector y = Ax ∈ R m. There are a couple ways of looking at matrix-vector multiplication, and we will look at each of them in turn. If we write A by rows, then we can express Ax as, y = Ax = — a T 1 — — a T 2 — . . . — a T m — x = a T 1 x a T 2 x . . . a T mx . 4
In other words,the ith entry of y is equal to the inner product of the ith row of A and x, 头=ax. Alternatively,let's write A in column form.In this case we see that, =Ax= 小小小小 In other words,y is a linear combination of the columns of A,where the coefficients of the linear combination are given by the entries of z. So far we have been multiplying on the right by a column vector,but it is also possible to multiply on the left by a row vector.This is written,yT=TA for A ERmxn,e Rm, and y ER".As before,we can express yf in two obvious ways,depending on whether we express A in terms on its rows or columns.In the first case we express A in terms of its columns,which gives yT=TA=2T which demonstrates that the ith entry of y is equal to the inner product of x and the ith column of A. Finally,expressing A in terms of rows we get the final representation of the vector-matrix product, y=xTA =[12 品 =1[-a-]+2[-a3-]+.+xn[-a7-] so we see that y is a linear combination of the rows of A,where the coefficients for the linear combination are given by the entries of r. 2.3 Matrix-Matrix Products Armed with this knowledge,we can now look at four different (but,of course,equivalent) ways of viewing the matrix-matrix multiplication C AB as defined at the beginning of this section. First,we can view matrix-matrix multiplication as a set of vector-vector products.The most obvious viewpoint,which follows immediately from the definition,is that the (i,j)th 5
In other words, the ith entry of y is equal to the inner product of the ith row of A and x, yi = a T i x. Alternatively, let’s write A in column form. In this case we see that, y = Ax = | | | a1 a2 · · · an | | | x1 x2 . . . xn = a1 x1 + a2 x2 + . . . + an xn . In other words, y is a linear combination of the columns of A, where the coefficients of the linear combination are given by the entries of x. So far we have been multiplying on the right by a column vector, but it is also possible to multiply on the left by a row vector. This is written, y T = x TA for A ∈ R m×n , x ∈ R m, and y ∈ R n . As before, we can express y T in two obvious ways, depending on whether we express A in terms on its rows or columns. In the first case we express A in terms of its columns, which gives y T = x TA = x T | | | a1 a2 · · · an | | | = x T a1 x T a2 · · · x T an which demonstrates that the ith entry of y T is equal to the inner product of x and the ith column of A. Finally, expressing A in terms of rows we get the final representation of the vector-matrix product, y T = x TA = x1 x2 · · · xn — a T 1 — — a T 2 — . . . — a T m — = x1 — a T 1 — + x2 — a T 2 — + ... + xn — a T n — so we see that y T is a linear combination of the rows of A, where the coefficients for the linear combination are given by the entries of x. 2.3 Matrix-Matrix Products Armed with this knowledge, we can now look at four different (but, of course, equivalent) ways of viewing the matrix-matrix multiplication C = AB as defined at the beginning of this section. First, we can view matrix-matrix multiplication as a set of vector-vector products. The most obvious viewpoint, which follows immediately from the definition, is that the (i, j)th 5
entry of C is equal to the inner product of the ith row of A and the jth row of B.Symbolically, this looks like the following, aTb1ab2· aTbp a喝b C=AB ambi amb2 ambp Remember that since A∈Rmxn and B∈Rnxp,ai∈Rn and b,∈Rm,so these inner products all make sense.This is the most "natural"representation when we represent A by rows and B by columns.Alternatively,we can represent A by columns,and B by rows. This representation leads to a much trickier interpretation of AB as a sum of outer products. Symbolically, C=AB= a:t Put another way,AB is equal to the sum,over all i,of the outer product of the ith column of A and the ith row of B.Since,in this case,aiE Rm and biE RP,the dimension of the outer product ab is m x p,which coincides with the dimension of C.Chances are,the last equality above may appear confusing to you.If so,take the time to check it for yourself! Second,we can also view matrix-matrix multiplication as a set of matrix-vector products. Specifically,if we represent B by columns,we can view the columns of C as matrix-vector products between A and the columns of B.Symbolically, C=AB=A Ab Ab2 b, Here the ith column of C is given by the matrix-vector product with the vector on the right, ci=Abi.These matrix-vector products can in turn be interpreted using both viewpoints given in the previous subsection.Finally,we have the analogous viewpoint,where we repre- sent A by rows,and view the rows of C as the matrix-vector product between the rows of A and C.Symbolically, 二 C=AB Here the ith row of C is given by the matrix-vector product with the vector on the left, c=a B. 6
entry of C is equal to the inner product of the ith row of A and the jth row of B. Symbolically, this looks like the following, C = AB = — a T 1 — — a T 2 — . . . — a T m — | | | b1 b2 · · · bp | | | = a T 1 b1 a T 1 b2 · · · a T 1 bp a T 2 b1 a T 2 b2 · · · a T 2 bp . . . . . . . . . . . . a T mb1 a T mb2 · · · a T mbp . Remember that since A ∈ R m×n and B ∈ R n×p , ai ∈ R n and bj ∈ R n , so these inner products all make sense. This is the most “natural” representation when we represent A by rows and B by columns. Alternatively, we can represent A by columns, and B by rows. This representation leads to a much trickier interpretation of AB as a sum of outer products. Symbolically, C = AB = | | | a1 a2 · · · an | | | — b T 1 — — b T 2 — . . . — b T n — = Xn i=1 aib T i . Put another way, AB is equal to the sum, over all i, of the outer product of the ith column of A and the ith row of B. Since, in this case, ai ∈ R m and bi ∈ R p , the dimension of the outer product aib T i is m × p, which coincides with the dimension of C. Chances are, the last equality above may appear confusing to you. If so, take the time to check it for yourself! Second, we can also view matrix-matrix multiplication as a set of matrix-vector products. Specifically, if we represent B by columns, we can view the columns of C as matrix-vector products between A and the columns of B. Symbolically, C = AB = A | | | b1 b2 · · · bp | | | = | | | Ab1 Ab2 · · · Abp | | | . Here the ith column of C is given by the matrix-vector product with the vector on the right, ci = Abi . These matrix-vector products can in turn be interpreted using both viewpoints given in the previous subsection. Finally, we have the analogous viewpoint, where we represent A by rows, and view the rows of C as the matrix-vector product between the rows of A and C. Symbolically, C = AB = — a T 1 — — a T 2 — . . . — a T m — B = — a T 1 B — — a T 2 B — . . . — a T mB — . Here the ith row of C is given by the matrix-vector product with the vector on the left, c T i = a T i B. 6
It may seem like overkill to dissect matrix multiplication to such a large degree,especially when all these viewpoints follow immediately from the initial definition we gave (in about a line of math)at the beginning of this section.However,virtually all of linear algebra deals with matrix multiplications of some kind,and it is worthwhile to spend some time trying to develop an intuitive understanding of the viewpoints presented here. In addition to this,it is useful to know a few basic properties of matrix multiplication at a higher level: Matrix multiplication is associative:(AB)C=A(BC). Matrix multiplication is distributive:A(B+C)=AB+AC. Matrix multiplication is,in general,not commutative;that is,it can be the case that AB≠BA.(For example,ifA∈Rmxn and B∈Rnxg,the matrix product BA does not even exist if m and g are not equal!) If you are not familiar with these properties,take the time to verify them for yourself. For example,to check the associativity of matrix multiplication,suppose that A Rmxn B∈Rnxp,andC∈Rpxg.Note that AB∈Rmxp,so(AB)C∈Rmxg.Similarly,BC∈Rnxg, so A(BC)E Rmxa.Thus,the dimensions of the resulting matrices agree.To show that matrix multiplication is associative,it suffices to check that the (i,j)th entry of(AB)C is equal to the (i,j)th entry of A(BC).We can verify this directly using the definition of matrix multiplication: (AB)C)5= Ck 1 若 ( (BC)-(A(BC) Here,the first and last two equalities simply use the definition of matrix multiplication,the third and fifth equalities use the distributive property for scalar multiplication over addition, and the fourth equality uses the commutative and associativity of scalar addition.This technique for proving matrix properties by reduction to simple scalar properties will come up often,so make sure you're familiar with it. 3 Operations and Properties In this section we present several operations and properties of matrices and vectors.Hope- fully a great deal of this will be review for you,so the notes can just serve as a reference for these topics. 7
It may seem like overkill to dissect matrix multiplication to such a large degree, especially when all these viewpoints follow immediately from the initial definition we gave (in about a line of math) at the beginning of this section. However, virtually all of linear algebra deals with matrix multiplications of some kind, and it is worthwhile to spend some time trying to develop an intuitive understanding of the viewpoints presented here. In addition to this, it is useful to know a few basic properties of matrix multiplication at a higher level: • Matrix multiplication is associative: (AB)C = A(BC). • Matrix multiplication is distributive: A(B + C) = AB + AC. • Matrix multiplication is, in general, not commutative; that is, it can be the case that AB 6= BA. (For example, if A ∈ R m×n and B ∈ R n×q , the matrix product BA does not even exist if m and q are not equal!) If you are not familiar with these properties, take the time to verify them for yourself. For example, to check the associativity of matrix multiplication, suppose that A ∈ R m×n , B ∈ R n×p , and C ∈ R p×q . Note that AB ∈ R m×p , so (AB)C ∈ R m×q . Similarly, BC ∈ R n×q , so A(BC) ∈ R m×q . Thus, the dimensions of the resulting matrices agree. To show that matrix multiplication is associative, it suffices to check that the (i, j)th entry of (AB)C is equal to the (i, j)th entry of A(BC). We can verify this directly using the definition of matrix multiplication: ((AB)C)ij = X p k=1 (AB)ikCkj = X p k=1 Xn l=1 AilBlk! Ckj = X p k=1 Xn l=1 AilBlkCkj! = Xn l=1 X p k=1 AilBlkCkj! = Xn l=1 Ail Xn k=p BlkCkj! = Xn l=1 Ail(BC)lj = (A(BC))ij . Here, the first and last two equalities simply use the definition of matrix multiplication, the third and fifth equalities use the distributive property for scalar multiplication over addition, and the fourth equality uses the commutative and associativity of scalar addition. This technique for proving matrix properties by reduction to simple scalar properties will come up often, so make sure you’re familiar with it. 3 Operations and Properties In this section we present several operations and properties of matrices and vectors. Hopefully a great deal of this will be review for you, so the notes can just serve as a reference for these topics. 7
3.1 The Identity Matrix and Diagonal Matrices The identity matric,denoted I E Rnxr,is a square matrix with ones on the diagonal and zeros everywhere else.That is, (1i=j ={0i+j It has the property that for all ARmxn, AI=A=IA. Note that in some sense,the notation for the identity matrix is ambiguous,since it does not specify the dimension of I.Generally,the dimensions of I are inferred from context so as to make matrix multiplication possible.For example,in the equation above,the I in Al=A is an n x n matrix,whereas the I in A=IA is an m x m matrix. A diagonal matrin is a matrix where all non-diagonal elements are 0.This is typically denoted D diag(di,d2,...,dn),with di i=j 0i≠j Clearly,I diag(1,1,...,1). 3.2 The Transpose The transpose of a matrix results from "flipping"the rows and columns.Given a matrix A E Rmxr,its transpose,written ATE Rnxm,is the n x m matrix whose entries are given by (AT)i=Aji We have in fact already been using the transpose when describing row vectors,since the transpose of a column vector is naturally a row vector. The following properties of transposes are easily verified: ·(AT)T=A ·(AB)T=BTAT ·(A+B)T=AT+BT 3.3 Symmetric Matrices A square matrix AE Rnxn is symmetric if A=AT.It is anti-symmetric if A=-AT. It is easy to show that for any matrix A E R"x",the matrix A+AT is symmetric and the 8
3.1 The Identity Matrix and Diagonal Matrices The identity matrix, denoted I ∈ R n×n , is a square matrix with ones on the diagonal and zeros everywhere else. That is, Iij = 1 i = j 0 i 6= j It has the property that for all A ∈ R m×n , AI = A = IA. Note that in some sense, the notation for the identity matrix is ambiguous, since it does not specify the dimension of I. Generally, the dimensions of I are inferred from context so as to make matrix multiplication possible. For example, in the equation above, the I in AI = A is an n × n matrix, whereas the I in A = IA is an m × m matrix. A diagonal matrix is a matrix where all non-diagonal elements are 0. This is typically denoted D = diag(d1, d2, . . . , dn), with Dij = di i = j 0 i 6= j Clearly, I = diag(1, 1, . . . , 1). 3.2 The Transpose The transpose of a matrix results from “flipping” the rows and columns. Given a matrix A ∈ R m×n , its transpose, written AT ∈ R n×m, is the n × m matrix whose entries are given by (A T )ij = Aji. We have in fact already been using the transpose when describing row vectors, since the transpose of a column vector is naturally a row vector. The following properties of transposes are easily verified: • (AT ) T = A • (AB) T = BTAT • (A + B) T = AT + BT 3.3 Symmetric Matrices A square matrix A ∈ R n×n is symmetric if A = AT . It is anti-symmetric if A = −AT . It is easy to show that for any matrix A ∈ R n×n , the matrix A + AT is symmetric and the 8
matrix A-AT is anti-symmetric.From this it follows that any square matrix A E R"x"can be represented as a sum of a symmetric matrix and an anti-symmetric matrix,since A=(A+4)+(A-AT) and the first matrix on the right is symmetric,while the second is anti-symmetric.It turns out that symmetric matrices occur a great deal in practice,and they have many nice properties which we will look at shortly.It is common to denote the set of all symmetric matrices of size n as S",so that A E S"means that A is a symmetric n x n matrix; 3.4 The Trace The trace of a square matrix A E Rnx",denoted tr(A)(or just trA if the parentheses are obviously implied),is the sum of diagonal elements in the matrix: trA As described in the CS229 lecture notes,the trace has the following properties (included here for the sake of completeness): ●ForA∈Rnxn,trA=trAT. ·ForA,B∈Rnxn,tr(A+B)=trA+trB. ·ForA∈Rmxn,t∈R,tr(tA)=ttrA. For A,B such that AB is square,trAB trBA For A,B,C such that ABC is square,trABC trBCA trCAB,and so on for the product of more matrices. As an example of how these properties can be proven,we'll consider the fourth property given above.Suppose that A E Rmxn and B E Rnxm (so that AB E Rmxm is a square matrix).Observe that BA E Rnxn is also a square matrix,so it makes sense to apply the trace operator to it.To verify that trAB =trBA,note that =(三)B4防=BM 9
matrix A−AT is anti-symmetric. From this it follows that any square matrix A ∈ R n×n can be represented as a sum of a symmetric matrix and an anti-symmetric matrix, since A = 1 2 (A + A T ) + 1 2 (A − A T ) and the first matrix on the right is symmetric, while the second is anti-symmetric. It turns out that symmetric matrices occur a great deal in practice, and they have many nice properties which we will look at shortly. It is common to denote the set of all symmetric matrices of size n as S n , so that A ∈ S n means that A is a symmetric n × n matrix; 3.4 The Trace The trace of a square matrix A ∈ R n×n , denoted tr(A) (or just trA if the parentheses are obviously implied), is the sum of diagonal elements in the matrix: trA = Xn i=1 Aii. As described in the CS229 lecture notes, the trace has the following properties (included here for the sake of completeness): • For A ∈ R n×n , trA = trAT . • For A, B ∈ R n×n , tr(A + B) = trA + trB. • For A ∈ R n×n , t ∈ R, tr(tA) = t trA. • For A, B such that AB is square, trAB = trBA. • For A, B, C such that ABC is square, trABC = trBCA = trCAB, and so on for the product of more matrices. As an example of how these properties can be proven, we’ll consider the fourth property given above. Suppose that A ∈ R m×n and B ∈ R n×m (so that AB ∈ R m×m is a square matrix). Observe that BA ∈ R n×n is also a square matrix, so it makes sense to apply the trace operator to it. To verify that trAB = trBA, note that trAB = Xm i=1 (AB)ii = Xm i=1 Xn j=1 AijBji! = Xm i=1 Xn j=1 AijBji = Xn j=1 Xm i=1 BjiAij = Xn j=1 Xm i=1 BjiAij! = Xn j=1 (BA)jj = trBA. 9
Here,the first and last two equalities use the definition of the trace operator and matrix multiplication.The fourth equality,where the main work occurs,uses the commutativity of scalar multiplication in order to reverse the order of the terms in each product,and the commutativity and associativity of scalar addition in order to rearrange the order of the summation. 3.5 Norms A norm of a vector is informally a measure of the "length"of the vector.For example, we have the commonly-used Euclidean or e2 norm, 2 Note that竖=xTx. More formally,a norm is any function f:R"-R that satisfies 4 properties: l.For all x∈Rn,f(x)≥0(non-negativity) 2.f(r)=0 if and only if x =0 (definiteness). 3.For all xE R",tER,f(tx)=tf(r)(homogeneity) 4.For all,y∈R",f(x+y）≤f(r)+f(y)）(triangle inequality). Other examples of norms are the ei norm, lh=∑zl and the loo norm, llclloo maxiil. In fact,all three norms presented so far are examples of the family of ep norms,which are parameterized by a real number p>1,and defined as 1 Norms can also be defined for matrices,such as the Frobenius norm, A号=V(AT④. Many other norms exist,but they are beyond the scope of this review. 10
Here, the first and last two equalities use the definition of the trace operator and matrix multiplication. The fourth equality, where the main work occurs, uses the commutativity of scalar multiplication in order to reverse the order of the terms in each product, and the commutativity and associativity of scalar addition in order to rearrange the order of the summation. 3.5 Norms A norm of a vector kxk is informally a measure of the “length” of the vector. For example, we have the commonly-used Euclidean or ℓ2 norm, kxk2 = vuutXn i=1 x 2 i . Note that kxk 2 2 = x T x. More formally, a norm is any function f : R n → R that satisfies 4 properties: 1. For all x ∈ R n , f(x) ≥ 0 (non-negativity). 2. f(x) = 0 if and only if x = 0 (definiteness). 3. For all x ∈ R n , t ∈ R, f(tx) = |t|f(x) (homogeneity). 4. For all x, y ∈ R n , f(x + y) ≤ f(x) + f(y) (triangle inequality). Other examples of norms are the ℓ1 norm, kxk1 = Xn i=1 |xi | and the ℓ∞ norm, kxk∞ = maxi |xi |. In fact, all three norms presented so far are examples of the family of ℓp norms, which are parameterized by a real number p ≥ 1, and defined as kxkp = Xn i=1 |xi | p !1/p . Norms can also be defined for matrices, such as the Frobenius norm, kAkF = vuut Xm i=1 Xn j=1 A2 ij = p tr(ATA). Many other norms exist, but they are beyond the scope of this review. 10