MIT OpenCourseWare http://ocw.mit.edu 18.085 Computational Science and Engineering I Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.Linear Algebra In A Nutshell 685 LINEAR ALGEBRA IN A NUTSHELL One question always comes on the first day of class. “Do I have to know linear algebra?” My reply gets shorter every year: “You soon wil l.” This section brings together many important points in the theory. It serves as a quick primer, not an official part of the applied mathematics course (like Chapter 1 and 2). This summary begins with two lists that use most of the key words of linear algebra. The first list applies to invertible matrices. That property is described in 14 different ways. The second list shows the contrast, when A is singular (not invertible). There are more ways to test invertibility of an n by n matrix than I expected. Nonsingular Singular A is invertible A is not invertible The columns are independent The columns are dependent The rows are independent The rows are dependent The determinant is not zero The determinant is zero Ax = 0 has one solution x =0 Ax = 0 has infinitely many solutions Ax = b has one solution x = A−1b Ax= b has no solution or infinitely many A has n (nonzero) pivots A has r<n pivots A has full rank A has rank r<n The reduced row echelon form is R = IRha s at least one zero row The column space is all of Rn The column space has dimension r<n The row space is all of RnThe row space has dimension r<n All eigenvalues are nonzero Zero is an eigenvalue of A ATA is symmetric positive definite ATA is only semidefinite A has n (positive) singular values A has r<n singular values Now we take a deeper look at linear equations, without proving every statement we make. The goal is to discover what Ax = b really means. One reference is my textbook Introduction to Linear Algebra, published by Wellesley-Cambridge Press. That book has a much more careful development with many examples (you could look at the course page, with videos of the lectures, on ocw.mit.edu or web.mit.edu/18.06). The key is to think of every multiplication Ax, a matrix A times a vector x,asa combination of the columns of A: Matrix Multiplication by Columns  12 36 C D  = C  1 3  + D  2 6  = combination of columns . Multiplying by rows, the first component C +2D comes from 1 and 2 in the first row of A. But I strongly recommend to think of Ax acolumn at atime.Noticeh ow686 Linear Algebra In A Nutshell x =(1, 0) and x =(0, 1) will pick out single columns of A:    12 1 12 0 =firstc olumn   = last column . 36 0 36 1 Suppose A is an m by n matrix. Then Ax = 0 has at least one solution, the all-zeros vector x = 0. There are certainly other solutions in case n>m(more unknowns than equations). Even if m = n, there might be nonzero solutions to Ax =0; then A is square but not invertible. It is the number r of independent rows and columns that counts. That number r is the rank of A (r ≤ m and r ≤ n). The nullspace of A is the set of all solutions x to Ax = 0. This nullspace N (A)contains only x = 0 when the columns of A are independent.In that case the matrix A has full column rank r = n: independent columns. For our 2 by 2 example, the combination with C =2 and D = −1 produces the zero vector. Thus x =(2, −1) is in the nullspace, with Ax =0. The columns (1, 3) and (2, 6) are “linearly dependent.” One column is a multiple of the other column. The rank is r =1. The matrix A has a whole line of vectors cx = c(2, −1) in its nullspace:   Nullspace 12 2 0 12 2c 0 = and also = . is a line 36 −1  0  36 −c  0 If Ax =0 and Ay = 0, then every combination cx + dy is in the nullspace. Always Ax = 0 asks for a combination of the columns of A that produces the zero vector: x in nullspace x1 (column 1) + ···+ xn (column n)= zero vector When those columns are independent, the only way to produce Ax =0i sw ithx 1 =0, x2 =0, ..., xn =0. Then x =(0,...,0) is the only vector in the nullspace of A. Often this will be our requirement (independent columns) for a good matrix A.In that case, ATA also has independent columns. The square n by n matrix ATA is then invertible and symmetric and positive definite. If A is good then ATA is even better. I will extend this review (still optional) to the geometry of Ax = b. Column Space and Solutions to Linear Equations Ax = b asks for a linear combination of the columns that equals b.Ino ur 2 by 2 example, the columns go in the same direction! Then b does too: 12 C 1 Column space Ax =  is always on the line through 36 D 3 . We can only solve Ax = b when the vector b is on that line. For b =(1, 4) there is no solution, it is off the line. For b =(5, 15) there are many solutions (5 times column 1 gives b,andt hisb is on the line). The big step is to look at a space of vectors:Linear Algebra In A Nutshell 687 Definition: The column space contains all combinations of the columns. In other words, C (A) contains all possible products A times x. Therefore Ax = b is solvable exactly when the vector b is in the column space C (A). For an m by n matrix, the columns have m components. The column space of A is in m-dimensional space. The word “space” indicates that the key operation of linear algebra is allowed: Any combination of vectors in the space stays in the space. The zero combination is allowed, so the vector x = 0 is in every space. How do we write down all solutions, when b belongs to the column space of A ? Any one solution to Ax = b is a particular solution xp. Any vector xn in the nullspace solves Ax = 0. Adding Axp = b to Axn =0 gives A(xp + xn)=b . The complete solution to Ax = b has this form x = xp + xn:            Complete solution x = x + x =(onex p)+(all xparticular nullspace n). In the example, b =(5, 15) is 5 times the first column, so one particular solution is xp =(5, 0). To find all other solutions, add to xp any vector xn in the nullspace— which is the line through (2, −1). Here is xp +(all xn): 12 …