Solving Ax = b: Row Reduced form R

Solving Ax = b: row reduced form R When does Ax = b have solutions x, and how can we describe those solutions? Solvability conditions on b We again use the example: ⎡ ⎤ 1 2 2 2 A = ⎣ 2 4 6 8 ⎦. 3 6 8 10 The third row of A is the sum of its first and second rows, so we know that if Ax = b the third component of b equals the sum of its first and second components. If b does not satisfy b3 = b1 + b2 the system has no solution. If a combination of the rows of A gives the zero row, then the same combination of the entries of b must equal zero. One way to find out whether Ax = b is solvable is to use elimination on the augmented matrix. If a row of A is completely eliminated, so is the corre­ sponding entry in b. In our example, row 3 of A is completely eliminated: ⎡ ⎤ ⎡ ⎤ 1 2 2 2 b1 1 2 2 2 b1 ⎣ 2 4 6 8 b2 ⎦ → · · · → ⎣ 0 0 2 4 b2 − 2b1 ⎦. 3 6 8 10 b3 0 0 0 0 b3 − b2 − b1 If Ax = b has a solution, then b3 − b2 − b1 = 0. For example, we could choose � � b= 1 5 6 . From an earlier lecture, we know that Ax = b is solvable exactly when b is in the column space C ( A). We have these two conditions on b; in fact they are equivalent. Complete solution In order to find all solutions to Ax = b we first check that the equation is solvable, then find a particular solution. We get the complete solution of the equation by adding the particular solution to all the vectors in the nullspace. A particular solution One way to find a particular solution to the equation Ax = b is to set all free variables to zero, then solve for the pivot variables. For our example matrix A, we let x2 = x4 = 0 to get the system of equa­ tions: x1 + 2x3 = 1 2x3 = 3 which has the solution x3 = 3/2, x1 = −2. Our particular solution is: ⎡ ⎤ −2 ⎢ 0 ⎥ ⎥ xp = ⎢ ⎣ 3/2 ⎦ . 0 Combined with the nullspace The general solution to Ax = b is given by xcomplete = x p + xn , where xn is a generic � vector �in the nullspace. To see this, we add Ax p = b to Axn = 0 and get A x p + xn = b for every vector xn in the nullspace. Last lecture we learned that the nullspace of A is the collection of all combi­ ⎡ ⎤ ⎡ ⎤ ⎢ nations of the special solutions ⎣ � to the equation Ax = 1 5 6 � is: ⎡ xcomplete −2 2 1 ⎥ ⎢ 0 ⎥ and ⎣ . So the complete solution 0 ⎦ −2 ⎦ 0 1 ⎤ ⎡ ⎤ ⎡ −2 −2 2 ⎢ ⎥ ⎢ 1 ⎥ ⎢ 0 0 ⎥ ⎢ ⎥ ⎢ =⎢ ⎣ 3/2 ⎦ + ⎣ 0 ⎦ + c2 ⎣ −2 0 0 1 ⎤ ⎥ ⎥, ⎦ where c1 and c2 are real numbers. The nullspace of A is a two dimensional subspace of R4 , and the solutions ⎡ ⎤ −2 0 ⎥ ⎢ to the equation Ax = b form a plane parallel to that through x p = ⎣ . 3/2 ⎦ 0 Rank The rank of a matrix equals the number of pivots of that matrix. If A is an m by n matrix of rank r, we know r ≤ m and r ≤ n. Full column rank If r = n, then from the previous lecture we know that the nullspace has dimen­ sion n − r = 0 and contains only the zero vector. There are no free variables or special solutions. If Ax = b has a solution, it is unique; there is either 0 or 1 solution. Exam­ ples like this, in which the columns are independent, are common in applica­ tions. We know r ≤ m, so if r = n the number of columns of the matrix is less than or equal to the number of rows. The row reduced echelon form of the � � I . For any vector b in Rm that’s not a linear 0 combination of the columns of A, there is no solution to Ax = b. matrix will look like R = Full row rank � � If r = m, then the reduced matrix R = I F has no rows of zeros and so there are no requirements for the entries of b to satisfy. The equation Ax = b is solvable for every b. There are n − r = n − m free variables, so there are n − m special solutions to Ax = 0. Full row and column rank If r = m = n is the number of pivots of A, then A is an invertible square matrix and R is the identity matrix. The nullspace has dimension zero, and Ax = b has a unique solution for every b in Rm . Summary If R is in row reduced form with pivot columns first (rref), the table below summarizes our results. r=m=n r=n< m r=m< n r < m, r < n � � R I I 0 # solutions to Ax = b 1 0 or 1 � I F � infinitely many � I 0 F 0 � 0 or infinitely many