Gaussian Elimination

Gaussian elimination Contents 1 Introduction 1 2 Some definitions and examples 2 3 Elementary row operations 7 4 Gaussian elimination 11 5 Rank and row reduction 16 6 Some computational tricks 18 1 Introduction The point of 18.700 is to understand vectors, vector spaces, and linear trans­ formations. The text provides an enormous amount of powerful abstract in­ formation about these things. Sometimes it’s helpful to be able to compute with these things, and matrices are a powerful tool for doing that. These notes concern the most fundamental and elementary matrix computation: solving systems of linear equations. The ideas should be familiar to you already; one reason to talk about them here is to connect those elementary computational ideas to the more theoretical ones introduced in the text. Another reason is that many people use some jargon about solving simulta­ neous equations (pivots and row-echelon form, for example) and you should know that language. 1 2 Some definitions and examples Always F is a field; you can think of F = Q, the field of rational numbers, which is where I’ll put most of the examples, but any field will do. The vector spaces we will look at are F n , the n-tuples of elements of F , for n a nonnegative integer. Almost always it will be most convenient to think of these as columns rather than rows: ⎧ ⎫ ⎛ ⎞ v1 ⎪ ⎪ ⎨ ⎬ ⎜ .. ⎟ n (2.1) F = v = ⎝ . ⎠ | vj ∈ F . ⎪ ⎪ ⎩ ⎭ vn An m × n matrix is a rectangular array of elements of F with m rows and n columns. The book doesn’t introduce a special notation for the set of all m × n matrices, but Mm×n (F ) is reasonable: ⎧ ⎫ ⎛ ⎞ a1 1 a1 2 · · · a1 n ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎜ a2 1 a2 2 · · · a2 n ⎟ ⎬ ⎜ ⎟ Mm×n (F ) = A = ⎜ . (2.2) | ai j ∈ F . ⎟ . . .. .. ⎠ ⎪ ⎪ ⎝ .. ⎪ ⎪ ⎪ ⎪ ⎩ ⎭ am 1 am 2 · · · am n Recall from Chapter 3 of the text that such a matrix A defines a linear map (which I’ll also call A) from F n to F m , by the formula A(v) = w, wi = n n ai j vj . (2.3) j=1 A little more explicitly, this is ⎛ ⎞ ⎛ ⎞ a1 1 v1 + a1 2 v2 + · · · a1 n vn v1 ⎜ ⎟ ⎜ .. ⎟ ⎜ a2 1 v1 + a2 2 v2 + · · · a2 n vn ⎟ A⎝ . ⎠ = ⎜ ⎟. .. ⎝ ⎠ . vn am 1 v1 + am 2 v2 + · · · a m n vn (2.4) The matrix A is exactly what we need to talk about simultaneous linear equations. A system of m linear equations in n unknowns is a1 1 x1 + a1 2 x2 + · · · + a1 n xn = b1 a2 1 x1 + a2 2 x2 + · · · + a2 n xn = b2 .. . am 1 x1 + am 2 x2 + · · · + am n xn = bm 2 (2.5a) The idea is that we are given the matrix A ∈ Mm×n (for instance some kind of model of a business operation), and the vector b ∈ F m (some kind of desired set of outcomes), and we wish to solve for an unknown vector x ∈ F n (the input conditions we should put into the model to get the desired outcomes). If we take advantage of matrix notation, the large and unwieldy equations in (2.5a) can be written Ax = b (x ∈ F n , b ∈ F m ). (2.5b) In terms of abstract linear algebra, (2.5a) can be phrased like this: Given A ∈ L(V, W ) and b ∈ W , find x ∈ V so that Ax = b. (2.5c) Here are some definitions for matrices related to the big ideas about linear transformations (null space and range). Definition 2.6. The null space of an m × n matrix A is Null(A) = {v ∈ F n | Av = 0} . The range of A is Range(A) = {Av ∈ F m | v ∈ F n } . It is easy to see that the range is exactly equal to the column space of A: if we write cj ∈ F m for the jth column of A, then Col(A) = span(c1 , . . . , cn ) = Range(A) ⊂ F m . The column rank of A, c-rank(A), is the dimension of the column space; equivalently, the dimension of the range of A: c-rank(A) = dim Col(A) = dim Range(A). Although we don’t have a linear algebra interpretation yet, it’s natural to define ri ∈ F n to be the ith row of A, and then Row(A) = span(r1 , . . . , rm ) ⊂ F n . Notice that here F n means row vectors of length n, rather than the column vectors we’ve usually been considering. The row rank of A, r-rank(A) is the dimension of the row space: r-rank(A) = dim Row(A). 3 Because this isn’t a serial drama in which I have to keep you in suspense until next week, I’ll spoil the story and tell you all the things we’re going to find out about these ranks and nullities. Proposition 2.7. Suppose A is an m × n matrix. 1. The row rank and the column rank of A are equal, and equal to the dimension of the range of A: r-rank(A) = c-rank(A) = dim Range(A). Their common value is called the rank of A, and written rank(A). 2. The dimension of the null space of A plus the rank of A is equal to n. The proof will appear in Section 5. You might think it strange that after the first result is a model of equal treatment for rows and columns, the second shows a sudden preference for n. Shouldn’t our null space be called a “column null space” (because it is contained in F n , and there are n columns); and shouldn’t there be a “row null space” contained in F m , with the property that dim(row null space of A) + r-rank(A) = m? (2.8) Sounds reasonable to me. Can you find such a definition? I’ll now pause to state some easy facts that are useful in their own right, and which can be taken as inspiration for the method of Gaussian elimina­ tion. Proposition 2.9. Suppose A is an m×n matrix, with rows r1 , . . . , rm ∈ F n . Suppose B is a p × m matrix. 1. Each row of BA is a linear combination of the rows of A. More pre­ cisely, the ith row of BA is the linear combination with coefficients given by the ith row of B: m n bij rj . j=1 2. The row space of BA is a subspace of the row space of A: Row(BA) ⊂ Row(A) ⊂ F n . 4 3. Each 1 × n row vector rj may be regarded as a linear map rj : F n → F, rj (v) = rj v from column vectors to F , by matrix multiplication. With this nota­ tion, ⎛ ⎞ r1 (v) ⎜ r2 (v) ⎟ ⎟ ⎜ Av = ⎜ . ⎟ ∈ F m . ⎝ .. ⎠ rm (v) 4. The null space of A is Null(A) = {v ∈ F n | rj (v) = 0 n = {v ∈ F | r(v) = 0 (j = 1, . . . , m)} (r ∈ Row(A))}. There are parallel results about right multiplication of A by C and the column space of A. Sketch of proof. The formula in (1) is just the definition of matrix multi­ plication. Then (2) follows. The formula in (3) is again the definition of matrix multiplication, and then (4) follows. This proposition shows that the row space of A (consisting of row vec­ tors of size n) can be interpreted as equations defining the null space of A (consisting of column vectors of size n). We now return to our march toward solving systems of equations. The next definition singles out some special matrices corresponding to systems of equations that are easy to solve. The strategy of Gaussian elimination is to transform any system of equations into one of these special ones. Definition 2.10. An m × n matrix A is said to be in row-echelon form if the nonzero entries are restricted to an inverted staircase shape. (The terminology comes from a French military description of troop arrangements; the word originally meant “rung of a ladder,” and is descended from the Latin “scala,” meaning ladder or stairs.) More precisely, we require 1. the first nonzero entry in each row is strictly to the right of the first nonzero entry in each earlier row; and 2. any rows consisting entirely of zeros must follow any nonzero rows. 5 The second requirement may be thought of as a special case of the first, if the “first nonzero entry” of a zero row is defined to be in position +∞, and one says that +∞ > +∞ > j for any finite position j. The pivots of a row-echelon matrix are the (finite) positions (i, j(i)) of the first nonzero entries of the nonzero rows i = 1, · · · , r, with r ≤ m the number of nonzero rows. Here is a row-echelon matrix, with the three pivots at (1, 2), (2, 4), and (3, 5) shown in bold: ⎛ ⎞ 0 −2 3 1 0 1 ⎜0 0 0 3/2 −4/3 17⎟ ⎜ ⎟ ⎜0 0 0 0 1 11⎟ ⎜ ⎟ ⎝0 0 0 0 0 0⎠ 0 0 0 0 0 0 The row-echelon matrix A is said to be in reduced row-echelon form if in addition 1. each pivot entry is equal to 1, and 2. all the other entries in the column of a pivot are equal to zero. The example above is not in reduced row-echelon form, because the pivots −2 and 3/2 are not equal to 1, and because of the two nonzero entries above the pivots 3/2 and 1. A reduced example is ⎛ ⎞ 0 1 −3/2 0 0 181/18 ⎜0 0 0 1 0 190/3 ⎟ ⎟ ⎜ ⎟ ⎜0 0 0 0 1 11 ⎟ ⎜ ⎝0 0 0 0 0 0 ⎠ 0 0 0 0 0 0 Suppose that the row-echelon matrix A has pivots in the first r rows, in columns 1 ≤ j(1) < j(2) < · · · < j(r) ≤ n. We call x1 , x2 ,. . . , xn the variables, having in mind a system of equations like (2.5a). The r variables xj(i) corresponding to the pivot columns are called pivot variables. The remaining n − r variables are called free variables. Proposition 2.11. Suppose that A is in reduced row-echelon form, with r pivots in the entries {(i, j(i)) | 1 ≤ i ≤ r}. 1. The first r standard basis vectors (f1 , . . . , fr ) of F m are a basis of Range(A). This is the column space of A, so c-rank(A) = r 6 2. The (first) r nonzero rows are a basis of the row space of A, so r-rank(A) = r. 3. For each free variable xj , there is a vector in the null space nj = ej − r n ai j ej(i) ; i=1 the n − r vectors nj , with xj a free variable, are a basis of Null(A). 4. The equation Ax = b (see (2.5)) has a solution if and only if bi = 0 for all i > r. In that case, one solution is xj(i) = bi (1 ≤ i ≤ r), xj = 0 (xj free variable). 5. Still assuming that bi = 0 for all i > r, the most general solution of Ax = b has arbitrary values xj for the n − r free variables, and n xj(i) = bi − ai j xj (1 ≤ i ≤ r). j free That is, we choose the n − r free variables, and then define the r pivot variables by the equation above. 3 Elementary row operations Proposition 2.11 provides very complete (and nearly obvious) information about how to solve Ax = b when A is in reduced row-echelon form. The present section gives a theoretical description of what you probably already know how to do in practice: to transform an arbitrary system of simultaneous equations into another system (A, b) ' (C, d) (3.1) with three properties: 1. A and C are matrices of the same size n × m, over the same field F , and b and d are vectors in F m ; 2. the two systems Ax = b and Cx = d have exactly the same solutions; that is, for x ∈ F n , the equation Ax = b is true if and only if Cx = d is true; and 7 3. the matrix C is in reduced row-echelon form. The procedure for doing this is called Gaussian elimination: Gaussian because it was systematized by Gauss (although the ideas are hundreds or thousands of years older), and elimination because the idea is to eliminate some of the variables xj from some of the equations. The procedure consists of a series of simple steps called elementary row operations, described in Definition 3.2 below. We will show that each el­ ementary row operation changes (A, b) to a new system (A' , b' ) satisfying the first two conditions of (3) above. Then we will explain how to perform a series of elementary row operations (the number depends on A, but the largest possibility is something like m2 − m) at the end of which we get a system in reduced row echelon form. Here is the main definition. Definition 3.2. Suppose Ax = b is a system of m equations in n unknowns ((2.5)). An elementary row operation is one of the four procedures below. 1. Multiply the ith equation by a nonzero scalar λ. That is, multiply the ith row of A and the ith entry of b each by λ: (ai 1 , ai 2 , . . . , ai n ) ' (λai 1 , λai 2 , . . . , λai n ), bi ' λbi . 2. Add a multiple µ of the jth equation to a later equation i, with 1 ≤ j < i ≤ m. That is (ai 1 , ai 2 , . . . , ai n ) ' (ai 1 + µaj, 1 , ai 2 + µaj 2 , . . . , ai n + µaj n ), bi ' bi + µbj . 3. Add a multiple µ of the jth equation to an earlier equation i, with 1 ≤ i < j ≤ m. That is (ai 1 , ai 2 , . . . , ai n ) ' (ai 1 + µaj, 1 , ai 2 + µaj 2 , . . . , ai n + µaj n ), bi ' bi + µbj . 4. Exchange equations i and j. (aj 1 , aj 2 , . . . , aj n ) ' (ai 1 , ai 2 , . . . , ai n ), bj ' bi (ai 1 , ai 2 , . . . , ai n ) ' (aj 1 , aj 2 , . . . , aj n ), bi ' bj 8 In order to talk about these operations formally, it is helpful to give them names. We call them M (i; λ) (1 ≤ i ≤ m, λ ∈ F − {0}) L(i, j; µ) (1 ≤ j < i ≤ m, µ ∈ F ) (3.3a) U (i, j; µ) (1 ≤ i < j ≤ m, µ ∈ F ) E(i, j) (1 ≤ j < i ≤ m). The letters stand for multiply, lower, upper, and exchange. To each elemen­ tary row operation we associate an m × m elementary row matrix ⎛ ⎞ 1 0 ··· 0 ⎜0 1 ··· 0 ⎟ ⎟ ⎜ ⎟ ⎜ . . ⎟ ⎜ . ⎟ ⎜ (3.3b) M (i; λ) = ⎜ 0⎟ ⎟ ⎜0 0 · · · λ · · · ⎟ ⎜ .. ⎠ ⎝ . 0 0 ··· 1 with λ appearing in the (i, i) place; ⎛ 1 0 ⎜0 1 ⎜ ⎜ ⎜ L(i, j; µ) = ⎜ ⎜0 · · · ⎜ ⎜ ⎝ 0 0 with µ appearing in the (i, j) ⎛ 1 ⎜0 ⎜ ⎜ ⎜ U (i, j; µ) = ⎜ ⎜0 ⎜ ⎜ ⎝ 0 ··· ··· .. . µ ··· 1 ··· .. . ··· ⎞ 0 0⎟ ⎟ ⎟ ⎟ ⎟ 0⎟ ⎟ ⎟ ⎠ 1 (3.3c) position (i > j); ··· ··· 0 1 .. . 0 ··· 1 ··· ··· 0 9 µ ··· .. . ⎞ 0 0 ⎟ ⎟ ⎟ ⎟ ⎟ 0 ⎟ ⎟ ⎟ ⎠ 1 (3.3d) with µ appearing in the (i, j) ⎛ 1 ⎜0 ⎜ ⎜ ⎜ ⎜ ⎜0 ⎜ E(i, j) = ⎜ ⎜ ⎜ ⎜0 ⎜ ⎜ ⎝ 0 position (i < j); and ··· ··· 0 1 .. . 0 ··· 0 ··· 0 ··· .. . 1 ··· ··· 0 1 ··· 0 ··· .. . ⎞ 0 0⎟ ⎟ ⎟ ⎟ ⎟ 0⎟ ⎟ ⎟ ⎟ ⎟ 0⎟ ⎟ ⎟ ⎠ 1 (3.3e) with the off-diagonal ones appearing in positions (i, j) and (j, i) (i < j). Proposition 3.4. Suppose that we are give a system of m simultaneous linear equations in n unknowns Ax = b ( (2.5)). 1. Performing an elementary row operation (Definition 3.2) is the same as multiplying A and b on the left by the corresponding elementary row matrix ( (3.3)). 2. Multiplying A and b on the left by any p×m matrix C can only enlarge the set of solutions. That is, any solution x of Ax = b is also a solution of (CA)x = Cb. 3. The elementary row matrices are all invertible. Explicitly, M (i; λ)−1 = M (i; λ−1 ); U (i, j; µ)−1 = U (i, j, −µ); L(i, j; µ)−1 = L(i, j, −µ); E(i, j)−1 = E(i, j). 4. Elementary row operations do not change the solutions of Ax = b. Consequently any finite sequence of elementary row operations amounts to left multiplication of A and b by an invertible m × m matrix L, and does not change the set of solutions. Sketch of proof. The assertion in (1) is best understood by looking at the definition of matrix multiplication, and trying some examples. One can make a formal proof by writing a formula for the entries of the elementary row matrices, like ⎧ ⎪ ⎨λ r = s = i M (i; λ)r s = 1 r = s = i ⎪ ⎩ 0 r = s, 10 and then plugging this formula into the definition of M (i; λ)A. The second statement in (2) is obvious (by applying C to the equation Ax = b, and using the associative law for matrix multiplication). The first statement in (2) follows from the second. The elementary row operations as described in Definition 3.2 are ob­ viously reversible, and in each case the inverse is another elementary row operation of the same kind. For example, to reverse the operation of adding µ times the jth row to the ith row, we simply add −µ times the jth row to the ith row. Because of (1), it follows that L(i, j, −µ)L(i, j; µ) = Im . This proves that L(i, j; µ)−1 = L(i, j, −µ), and the other assertions are similar. For (4), part (2) says that an elementary row operation L can only increase the set of solutions. So by (3), (solutions of Ax = b) ⊂ (solutions of LAx = Lb) ⊂ (solutions of L−1 LAx = L−1 Lb) = (solutions of Ax = b). So the containments must be equalities. 4 Gaussian elimination We now know some elementary things to do to a system of simultaneous equations that don’t change the solutions; and we know everything about solving systems that are in reduced row-echelon form. All that remains is to see that we can do those elementary things and put any system in reduced row-echelon form. This is pretty easy; the system of rules for doing it is Gaussian elimination. Here are the details. I’m going to do it in three parts. (This arrangement is slightly different from most of the written versions that you’ll see; it’s chosen to get some nice theoretical facts as consequences.) The first part of the algorithm finds (in succession) r special entries (i(1), j(1)), (i(2), j(2)), . . . , (i(r), j(r)), 1 ≤ j(1) < j(2) < · · · < j(r) ≤ n, 1 ≤ i(p) ≤ m all distinct 11 (4.1a) These entries will become the pivots in the row-echelon form (Definition 2.10). After we perform the row operations in the first part of the algo­ rithm, we will have a matrix with the following properties (which are in the direction of the requirements of row echelon form): the first entry of row i(p) is a 1, in column j(p); (4.1b) entries in column j(p) above row i(p), except in rows i(q) with q < p, are zero; and (4.1c) entries in column j(p) below row i(p) are zero. (4.1d) We will find these entries and arrange for the these vanishing conditions one row at a time. We know we are finished when we finally have all entries of A outside rows i(1), . . . , i(r) are zero. (4.1e) A theoretically important fact about this part of Gaussian elimination is the row operations to achieve (4.1b)–(4.1e) are of types M and L. (4.1f) Here is how we accomplish this with a succession of elementary row operations. It is better to look at examples than to write down the formal description. First I’ll do a “typical” 3 × 3 case: ⎛ ⎞ ⎛ ⎞ 1 3/2 2 2 3 4 M (1;1/2) ⎝ 2 2 2⎠ −−−−−−→ ⎝ 2 2 2⎠ 1 2 1 1 2 1 ⎛ ⎞ ⎛ ⎞ (4.2a) 1 3/2 2 1 3/2 2 L(2,1;−2) L(3,1;−1) −−−−−−→ ⎝ 0 −1 −2⎠ −−−−−−→ ⎝ 0 −1 −2⎠ 1 2 1 0 1/2 −1 Here I pick the first nonzero entry in the first nonzero column, and marked it in bold. This marks the first row as the first of our special rows. I then multiply this special row by the inverse of the first entry, to make the first entry 1. Then I subtract multiples of the first row from other rows to get rid of the other entries in the first column. Onward. . . ⎛ ⎞ ⎛ ⎞ 1 3/2 2 1 3/2 2 M (2;−1) ⎝ 0 −1 −2⎠ − 2⎠ −−−−→ ⎝ 0 1 0 1/2 −1 0 1/2 −1 (4.2b) ⎛ ⎞ 1 3/2 2 L(3,2;−1/2) 2⎠ −−−−−−−→ ⎝ 0 1 0 0 −2 12 Here I pick the first column that’s nonzero outside the first row, then marked in bold its first nonzero entry outside the first row: now the second row is identified as the second of our special rows. Its leading entry is −1, so I multiply the row by its inverse −1. Then I subtract multiples of the second row from later rows to get rid of the later entries in this column. Onward again. . . ⎛ ⎞ ⎛ ⎞ 1 3/2 2 1 3/2 2 M (3;−1/2) ⎝0 1 2 ⎠ −−−−−−−→ ⎝ 0 1 2 ⎠ (4.2c) 0 0 −2 0 0 1 For this last step in this first part, I notice that the third column is the first one that’s nonzero outside the first two special rows. Its first entry outside the two special rows is the lower right corner entry −2, so that one becomes our third pivot, marked in bold. I multiply that third row by −1/2 to make the leading entry 1, and we end up with a matrix satisfying the conditions in (4.6) Here’s a more peculiar example. ⎛ ⎞ ⎛ ⎞ 0 0 0 2 0 0 0 2 M (3;1/3) ⎝0 0 2 4⎠ − −−−−−→ ⎝0 0 2 4⎠ (4.3a) 0 3 6 9 0 1 2 3 The first nonzero column is the second one, and its first nonzero entry is in the third row; so that row is our first special one, and the leading entry will be our first pivot. We multiply the third row by −1/3 to make the leading entry 1, and we’re done with the first special row. ⎛ ⎞ ⎛ ⎞ 0 0 0 2 0 0 0 2 M (2;1/2) ⎝0 0 2 4⎠ − −−−−−→ ⎝0 0 1 2⎠ 0 1 2 3 0 1 2 3 (4.3b) ⎛ ⎞ 0 0 0 2 L(3,2;−2) −−−−−−→ ⎝0 0 1 2 ⎠ 0 1 0 −1 Here the first column that’s nonzero outside the special third row is the third column, and its first nonzero entry is in the second row; that leading entry will be our second pivot. We multiply the second row by 1/2 to make the leading entry one, and then we clear the column entries below it. 13 ⎛ 0 ⎝0 0 ⎛ 0 L(2,1;−2) ⎝ −−−−−−→ 0 0 ⎞ ⎛ 0 0 2 0 M (1;1/2) 0 1 2 ⎠ −−−−−−→ ⎝0 1 0 −1 0 ⎞ ⎛ 0 0 1 0 L(3,1;1) ⎠ ⎝ 0 1 0 −−−−−→ 0 1 0 −1 0 ⎞ 0 0 1 0 1 2⎠ 1 0 −1 ⎞ 0 0 1 0 1 0⎠ 1 0 0 (4.3c) This time the new pivot is in fourth column, the entry in the first row. We multiply that row by 1/2 to make the pivot entry equal to one, then clear the column entries below. We end up with a matrix satisfying the conditions in (4.6). The second part of the algorithm starts with a matrix having r special entries as in (4.1b)–(4.1e), and rearranges the rows so that row i(1) becomes row 1, row i(2) becomes row 2, and so on. At the end of this part, our pivots will be in locations (1, j(1)), (2, j(2)), . . . , (r, j(r)), 1 ≤ j(1) < j(2) < · · · < j(r) ≤ n. (4.4a) The matrix after this part of the algorithm will satisfy the following require­ ments, which mean in particular that it is in row echelon form (Definition 2.10). the first entry of row p is a 1, in column j(p) (1 ≤ p ≤ r); (4.4b) entries in column j(p) below row p are zero. (4.4c) all entries of A below rows 1, . . . , r are zero. (4.4d) The big theoretical fact about this part of Gaussian elimination is the row operations to achieve (4.4b)–(4.4d) are of type E. (4.4e) The way to carry out this part is almost obvious: we exchange (if they are not already the same) the first special row i(1) with row 1; then the second special row with row 2; and so on through the r special rows. The “typical” case (like (4.2)) has special rows 1 through r in that order, and this step of the algorithm does nothing. Here is what the second step looks like in the example (4.3). 14 ⎛ ⎞ ⎛ ⎞ 0 0 0 1 0 1 0 0 E(1,3) ⎝0 0 1 0 ⎠ − −−−→ ⎝0 0 1 0 ⎠ 0 1 0 0 0 0 0 1 (4.5a) After we exchange row i(1) = 3 with row 1, the first three rows are the special rows in order, and we are done. The third and last part of the algorithm starts with a matrix having r special entries in row echelon form as in (4.4b)–(4.4d), with pivots in locations (1, j(1)), (2, j(2)), . . . , (r, j(r)), (4.6a) 1 ≤ j(1) < j(2) < · · · < j(r) ≤ n. This part of the algorithm clears the column entries above the pivots. The matrix at the end of this last part will satisfy the following requirements, which mean that it is in reduced row echelon form (Definition 2.10). the first entry of row p is a 1, in column j(p) (1 ≤ p ≤ r); (4.6b) all other entries in column j(p) are zero. (4.6c) all entries of A below rows 1, . . . , r are zero. (4.6d) The theoretical fact about this part of Gaussian elimination is the row operations to achieve (4.6b)–(4.6d) are of type U . (4.6e) Here is how this looks in the example of (4.2). First we clear the column above the second pivot ⎛ ⎞ ⎛ ⎞ 1 3/2 2 1 0 −1 U (1,2;−3/2) ⎝0 1 2⎠ − −−−−−−→ ⎝ 0 1 2 ⎠ , (4.7a) 0 0 1 0 0 1 then the column above the third ⎛ ⎞ ⎛ 1 0 −1 1 U (1,3;1) ⎝0 1 2 ⎠ − −−−−→ ⎝ 0 0 0 1 0 pivot ⎞ ⎛ ⎞ 0 0 1 0 0 U (2,3;−2) 1 2 ⎠ −−−−−−→ ⎝ 0 1 0 ⎠ . 0 1 0 0 1 Here is a theorem summarizing the algorithm described above. 15 (4.7b) Theorem 4.8. Suppose A' is an m × n matrix with entries in a field F . Then we can perform a finite sequence of elementary row operations on A' to obtain a new m × n matrix A' in reduced row-echelon form. More precisely, we perform 1. at most m row operations of type M (multiply a row by a nonzero scalar) interspersed with at most m(m − 1)/2 operations of type L (add a multiple of a row to a later row); then 2. at most m(m − 1)/2 operations of type E (exchange two rows); then 3. at most m(m − 1)/2 operations of type U (add a multiple of a row to an earlier row). Consequently, we can write A' = U ELA, A = L−1 E −1 U −1 A' . Here L and L−1 are m × m invertible lower-triangular matrices; E and E −1 are invertible m × m permutation matrices; and U and U −1 are invertible m × m upper-triangular matrices with ones on the diagonal. The reduced row echelon matrix A is unique (independent of how the row reduction is performed). The detailed description of step (1) is in (4.1), illustrated in the examples (4.2) and (4.3). The detailed description of step (2) is in (4.4), illustrated in example (4.5). The detailed description of step (3) is in (4.6), illustrated in (4.7). These descriptions can easily be made into a proof of the theorem; all that requires some additional explanation is the uniqueness assertion: that if A1 and A2 are reduced row-echelon matrices, and it is possible to pass from A1 to A2 by a sequence of elementary row operations, then A1 = A2 . That is not terribly difficult, but I won’t explain it. If all we care about is solving a system of equations, we might as well stop after step (1): the system is then in row-echelon form, except that the equations have been rearranged, so we can solve it by Proposition 2.11. After step (2), the system is in row-echelon form. 5 Rank and row reduction In this section we’ll prove Proposition 2.7, using Gaussian elimination. We begin with some general statements about how row operations affect row and column spaces, null spaces, and ranges. 16 Proposition 5.1. Suppose A is an m × n matrix. 1. Elementary row operations do not change the null space Null(A) ⊂ F n . In particular, they do not change the nullity dim Null(A). 2. Elementary row operations do not change the row space Row(A) ⊂ F n . In particular, they do not change the row rank r-rank(A). 3. Applying a sequence of elementary row operations is equivalent to left multiplication of A by an invertible m × m matrix L. The effect of this is to apply L to Range(A) ⊂ F m : Range(LA) = Col(LA) = L(Col(A)) = L(Range(A)). 4. Elementary row operations do not change the column rank c-rank(A). Proof. Part (1) is a special case of Proposition 3.4(4). For part (2), write the rows of A as ri ∈ F n . (r1 , . . . , rm ), The row space of A is equal to the span of these m vectors. The statement that (for example) L(i, j; µ) does not change the span can be written as span(r1 , . . . , rj , . . . , ri , rm ) = span(r1 , . . . , rj , . . . , ri + µrj , . . . , rm ) for any 1 ≤ i, j ≤ m and any µ ∈ F . This is clear. The first statement of (3) is Proposition 3.4(1) and (3); and then the second is clear. For (4), because L is invertible, it does not change the dimension of Col(A). Proof of Proposition 2.7. Because of Proposition 5.1, it suffices to prove the proposition after applying a sequence of elementary row operations to A. By Theorem 4.8, we may therefore assume that A is in reduced row eche­ lon form. In that case the equality of row and column ranks follows from Proposition 2.11. Having come so far, here is an explicit description of subspaces of F n . Theorem 5.2. Suppose n and r are nonnegative integers. There is a oneto-one correspondence between r-dimensional subspaces U ⊂ F n , and r × n matrices A in reduced row-echelon form, with one pivot in each row; that is, with no rows equal to zero. The correspondence sends the matrix A to the span Row(A) of the rows of A. To go in the other direction, suppose U is 17 an r-dimensional subspace of Fn . Choose a basis (u1 , . . . , ur ) of U , and let A' be the r × n matrix with rows ui . Perform Gaussian elimination on A' , getting an r × n matrix A in reduced row echelon form; this is the matrix corresponding to the subspace U . Sketch of proof. A matrix A of the desired form clearly has r pivots, and so has rank r (Proposition 2.7). Therefore the row space Row(A) is indeed an r-dimensional subspace of F n . Conversely, given an r-dimensional U , the construction in the theorem produces an r ×n matrix A' with Row(A' ) = U . Now perform Gaussian elimination on A' (Theorem 4.8), obtaining a reduced row echelon matrix A with Row(A) = Row(A' ) = U , as desired. The theorem says that any subspace has a basis of a very specific form. For example, it says that any two-dimensional subspace of F 3 has as basis the rows of one of the matrices 1 0 a , 0 1 b 1 c 0 , 0 0 1 0 1 0 . 0 0 0 That is, any two-dimensional subspace of F 3 is either 1. the graph of z = ax + by (some a, b in F ); or 2. the graph of y = cx (some c in F ); or 3. the y-z plane x = 0. 6 Some computational tricks Although these notes were written to emphasize interesting theoretical con­ sequences of Gaussian elimination, the method was designed for solving systems of equations, so I will include a few remarks about that. Suppose A is an m × n matrix, and b ∈ F m . Recall from (2.5) the system of m simultaneous equations in n unknowns A(x) = b (x ∈ F n , b ∈ F m ). (6.1) The “augmented matrix” for this system is the m × (n + 1) matrix A =def (A|b) A 18 (6.2) Performing Gaussian elimination on the augmented matrix leads to a rowechelon matrix (A' |b' ), corresponding to an equivalent system of equations A' (x) = b' . Here’s how this looks in the example of (4.2). ⎛ ⎞⎛ ⎞ ⎛ ⎞ 2 3 4 x1 1 ⎝2 2 2⎠ ⎝x2 ⎠ = ⎝2⎠ (6.3a) 3 1 2 1 x3 A the sequence of row operations that I explained in Now I’ll perform on A the previous section for A ⎛ ⎞ ⎛ ⎞ 2 3 4 1 1 3/2 2 1/2 M (1;1/2) A =⎝ 2 2 2 2 ⎠ − A −−−−−→ ⎝ 2 2 2 2 ⎠ 1 2 1 3 1 2 1 3 ⎛ ⎞ ⎛ ⎞ 1 3/2 2 1/2 1 3/2 2 1/2 L(2,1;−2) L(3,1;−1) −−−−−−→ ⎝ 0 −1 −2 1 ⎠ −−−−−−→ ⎝ 0 −1 −2 1 ⎠ 1 2 1 3 0 1/2 −1 5/2 ⎛ ⎞ ⎛ ⎞ 1 3/2 2 1/2 1 3/2 2 1/2 M (2;−1) L(3,2;−1/2) 2 −1 ⎠ −−−−−−−→ ⎝ 0 1 2 −1 ⎠ −−−−−→ ⎝ 0 1 0 1/2 −1 5/2 0 0 −2 3 ⎛ ⎞ ⎛ ⎞ 1 3/2 2 1/2 1 0 −1 2 M (3;−1/2) U (1,2;−3/2) −1 ⎠ −−−−−−−→ ⎝ 0 1 2 −1 ⎠ −−−−−−−→ ⎝ 0 1 2 0 0 1 −3/2 0 0 1 −3/2 ⎛ ⎞ ⎛ ⎞ 1 0 0 1/2 1 0 0 1/2 U (1,3;1) U (2,3;−2) 2 ⎠. −−−−−→ ⎝ 0 1 2 −1 ⎠ −−−−−−→ ⎝ 0 1 0 0 0 1 −3/2 0 0 1 −3/2 (6.3b) The equivalent system of equations is x1 = 1/2, x2 = 2, x3 = −3/2, (6.3c) which solves itself. You should check that these values really do satisfy the system (6.3a). There is a similar computational technique to compute a (left) inverse of A. (Such a left inverse exists if and only if the null space of A is zero (see notes on one-sided inverses), which is the same as requiring that r = n: there are no free variables, and there is a pivot in every row. The reduced 19 row-echelon form of A must then ⎛ 1 0 ⎜0 1 ⎜ ⎜ ⎜ ⎜ ' A =⎜ ⎜0 0 ⎜0 0 ⎜ ⎜ ⎝ 0 0 be ··· ··· .. . ··· ··· .. . ··· ⎞ 0 0⎟ ⎟ ⎟ ⎟   ⎟ In ⎟ 1⎟ = 0m×n 0⎟ ⎟ ⎟ ⎠ 0 (6.4) Here is how to compute a left inverse. Proposition 6.5. Suppose that A is an m × n matrix of rank r = n (so A = (A|Im ) of size m × m + n. that m ≥ n). Form an augmented matrix A Perform Gaussian elimination: Gauss A = (A|Im ) − −−−→ (A' |L) A with A' the matrix in (6.4) and L the m × m matrix which is the product of all the elementary row matrices used to reduce A. Write B for the n × m matrix consisting of the first n rows of L. Then LA = A' , BA = In . In particular, B is a left inverse of A. 20