Row Reduction & Echelon Forms PDF

II. Row reduction and echelon forms Definition 1 The leading entry of a non-zero row of a matrix is the first non-zero entry (counting left to right). It is also called a leading coefficient or pivot. 1 −...

II. Row reduction and echelon forms Definition 1 The leading entry of a non-zero row of a matrix is the first non-zero entry (counting left to right). It is also called a leading coefficient or pivot. 1 −1 10 1 leading entry: 1   A = 0 0 0 3 leading entry: 3 0 0 0 0 leading entry: none Definition 2 A matrix A is said to be in (row) echelon form if: (1) the non-zero rows of A precede the zero rows; (2) the column indexes of the leading entries of the non-zero rows form a strictly increasing sequence; Note: (2) implies that all entries in a column below a leading entry are zeros. For A given above: (1) A is 3 × 4 and the only zero row is the third one: ✓ (2) The columns indexes of the leading entries are 1 < 4: ✓ Example 0 0 0 0 0   0 0 0 0 0 A= 0 0 0 0 0  0 0 0 0 0 is in row echelon form. Example 0 −1 0 1 leading entry: −1 in column no. 2   A= 0 2 00 leading entry: 2 in column no. 2 So (2) doesn’t hold. Hence A is not in row echelon form. Example 0 0 0 0   A= 0 2 0 0 is not in row echelon form: (1) is not satisfied. Definition 3 A matrix R is in reduced (row) echelon form (RREF) if 1. it is in row echelon form 2. each leading entry is a 1 3. each leading entry has only zeros above it. 1  Example 1 −1 10 1 leading entry: 1   A = 0 0 0 3 leading entry: 3 0 0 0 0 leading entry: none (which we know to be in row echelon form) is however not in reduced row echelon form: (2) and (3) both fail. Example 1 1 10 1 leading entry: 1   A = 0 1 0 3 leading entry: 1 00 0 0 leading entry: none is not in reduced row echelon form: (2): ✓ but (3): ✗. Example 1 0 0 1 leading entry: 1   0 0 1 3 leading entry: 1 A= 0 0 0 0 leading entry: none  0 0 0 0 leading entry: none is in reduced row echelon form. A matrix in (reduced) row echelon form is sometimes called a row (reduced) echelon matrix. The point of this is that the solution set of an augmented matrix which is in reduced echelon form is very easy to read off. Example 1 0 0 1   0 0 1 3 A= 0 0 0 0   0 0 0 0 If we view A as the augmented matrix of a linear system, then it is a system in 3 variables which we will denote by x1 , x2 , x3. From the second row we get x3 = 3; from the first row we get x1 = 1. There is no non-trivial equation involving x2 , which means that x2 can take any value. Thus the solution set is {(1, α, 3) : α ∈ R}. Definition 4 The process of transforming the augmented matrix of a linear system to reduced row echelon form (using elementary row operations) is called Gaussian (Gauss–Jordan) elimination. Example (row echelon form is not unique) 1 1 10 1 1 0 10 −2     0 1 0 3 − E21 (−1) both row echelon; −−−−→ 0 1 0 3  one on the right also reduced 00 0 0 00 0 0 In contrast, Theorem 1 Every matrix can be reduced by a sequence of elementary row operations to one and only one reduced (row) echelon form. 2  The row reduction algorithm This algorithm brings a matrix into the row echelon form. 1. Starting on the left, find the first column that contains a leading entry (pivot). If there are several leading entries in this column, choose one of them. 2. Interchange the rows by applying the first elementary row operation (that is Eij ) until the row with the chosen pivot is on top. 3. Use the third elementary row operation (that is Eij (c)) to make the entries below the chosen pivot zero. 4. Find the column ≥ 2 that has a non-zero entry in a row ≥ 2 and repeat the first three steps. 5. Repeat these steps until you reach a matrix with zero entries below every pivot entry. By making the pivot entries 1 and making the entries above each pivot zero, one can obtain the reduced row echelon form. At the end the matrix in reduced row echelon form will look like this 0 ··· 0 1 ⋆ ··· ⋆ 0 ⋆ ··· ⋆ 0 ⋆   0 · · · 0 0 0 · · · 0 1 ⋆ · · · ⋆ 0 ⋆  0 · · · 0 0 0 · · · 0 0 0 · · · 0 1 ⋆ · · ·   ................   ........ 0 0  ....................  .......... Example Compute the row reduced echelon form of the matrix 31 2 5   2 0 4 6 . 0 3 −14 −12 3  Back to our chemical example Example Find the positive integers x1 , x2 , x3 , x4 such that the chemical equation is balanced: x1 CH4 + x2 O2 → x3 CO2 + x4 H2 O. Balancing this equation is equivalent to finding positive integers x1 , x2 , x3 , x4 such that the following holds: If x1 molecules of methane react with x2 molecules of stable oxygen, then they form x3 molecules of carbon dioxide and x4 molecules of water. By comparing the number of atoms of each element we obtain the system   x1 = x3  carbon x 1 − x 3 = 0  4x1 = 2x4 hydrogen ⇔ 4x1 − 2x4 = 0 2x2 = 2x3 + x4 oxygen 2x2 − 2x3 − x4 = 0     The augmented matrix of the system is 1 0 −1 0 0   à =  4 0 0 −2 0  0 2 −2 −1 0 Let’s use EROs to reduce à to its RREF: 1 0 −1 0 0 E3 (1/2) 1 0 −1 0 0     E12 (−4) E23 à −−−−−→  0 0 4 −2 0  −−−− −→  0 1 −1 −1/2 0  0 2 −2 −1 0 0 0 4 −2 0 1 0 −1 0 0 E31 (1) 1 0 0 −1/2 0     E3 (1/4) E32 (1) −−−−−→  0 1 −1 −1/2 0  −−−−→  0 1 0 −1 0  0 0 1 −1/2 0 0 0 1 −1/2 0 Let’s read off the solution from the RREF: 1 0 0 −1/2 0    0 1 0 −1 0  0 0 1 −1/2 0 Start from the variable corresponding to variable most on the right: x4. There is no row with a leading entry in the 4th column, so x4 is a free variable. This means that x4 can take any value. Reading the matrix from below we then get x3 = 21 x4 , x2 = x4 , x1 = 21 x4. Therefore the solution set is 1 1 :α∈R. 
2 α, α, 2 α, α Every solution to our linear system is of the form 12 α, α, 12 α, α where α ∈ R is free.
But.. how do we balance the chemical equation? Here is what we have done: EROs chemical problem → linear system −−−→ RREF → solution of the system ? → solution of the chemical problem − 4  The variables x1 , x2 , x3 , x4 are numbers of molecules. In particular they are non- negative integers (and let’s assume positive to get something non-trivial)! We are only interested in the following subset of solutions: {(m, 2m, m, 2m) : m ∈ N} Taking m = 1 gives the smallest positive integer solution and the balanced equation is CH4 + 2O2 → CO2 + 2H2 O Generic rules to use the RREF to read the solution set Let A be the RREF of the coefficient matrix and let à be the RREF of the aug- mented matrix. (1) Ignore the zero rows: they correspond to the equation 0 · x1 + · · · + 0 · xn = 0, which is always satisfied. (2) If à has a row of the form 0 0 0 ··· 0 □ where □ is a number different from zero, then the system is inconsistent and there are no solutions. (3) If every column of A has a pivot then there is exactly one solution. (4) If there are columns of A without pivots then there are infinitely many solutions. In particular, we deduce that a linear system always falls into one of the following cases: is inconsistent; is consistent with exactly one solution; is consistent with infinitely many solutions. While it may be easier to read the solution set from a matrix in RREF, but some- times it is already easy to determine the solution from a matrix in row echelon form: e.g 1 −4 3 2 −1/2   0 0 1 10 7  0 0 0 1 1 The technique is to start from the bottom of the matrix and move our way up. This is called back substitution. row 3: x4 = 1 row 2: x3 + 10x4 = 7, hence substituting x4 = 1 we get x3 = −3. row 1: x1 = 4x2 − 3x3 − 2x4 − 1 2 = 4x2 − 3 · (−3) − 2 · 1 − 1 2 = 4x2 + 13 2. Note x2 is free. The solution set is: 4α + 2 , α, −3, 1 13 :α∈R. 
5  Algorithm: using row reduction to solve a linear system Linear system S Augmented matrix à S is inconsistent Does R have a R = RREF leading entry in the S is consistent of à rightmost column? Are there free variables? Infinitely many Exactly one solutions solution Systems with more unknowns (variables) than equations We now look into the linear systems with more variables than equations. This means that the number of columns is more than the number of rows in the augmented matrix of this system. Example Solve ( x3 − x4 = 2 x1 + 2x2 − x3 + 2x4 = 1 Sometimes you can tell that a system is inconsistent before reaching the RREF: Example Solve ( 2x1 + x2 − x3 = 10 2 x1 − 4 x2 + 4 x3 = 0 − 13 13 13 6 As we can also see from the examples there are columns in the RREF of the coefficient matrix without a pivot. So if there exists a solution then we necessarily have at least one free variable, which implies that the system has infinitely many solutions. Therefore, if a system of linear equations has more unknowns than equations, then there are only two possibilities. Namely, it either has no solutions; or infinitely many solutions. In the other cases, more equations than unknowns or the same number of equations and unknowns, all three cases are possible. Tutorial exercises II. Class discussion: Exercise 1. (i) Suppose a 3 × 5 coefficient matrix for a system has three pivot columns. Is the system consistent? Why or why not? (ii) Suppose a system of linear equations has a 3 × 5 augmented matrix whose fifth column is a pivot column. Is the system consistent? Why or why not? (iii) (True/False) The echelon form of a matrix is unique. Work in groups: Exercise 2. Consider the augmented matrix 111 1   0 2 1 −1. 001 1 a) Is this augmented matrix in row echelon form? Is it in RREF? 7  b) Write down the linear system in the variables x1 , x2 , x3 corresponding to this augmented matrix. c) Find the solution set of this linear system. Is this system consistent? Exercise 3. Use EROs to compute the RREF of the following matrices 0 150 0 1 5 0      1 2 3 1  1 2 3 1 . −1 0 7 1 −1 0 7 −1 In each case write down the solution set of the corresponding linear system in the variables x1 , x2 , x3. [Note the matrices are nearly identical] Exercise 4. Determine all λ ∈ C such that (1 + i)2 1 λ   −4 2i 11i is the augmented matrix of a consistent linear system. For each such λ compute the solution set (over C) of the system. Exercise 5. Determine the values of parameter t such that the following augmented matrices correspond to consistent systems of linear equations: 1 t 4 2 −3 t −2 4 6       a) , b) , c) 368 −6 9 5 1 t −3 Exercise 6. Consider the following augmented matrix: 1 −4 7 a    0 3 −5 b . −2 5 −9 c Describe the set of values of (a, b, c) for which the linear system determined by this matrix is consistent. Exercise 7. (Network flow) In this exercise we consider an interesting application of systems of linear equations, namely network flow analysis. A network consists of branches through which a medium flows (think water through pipes, or cars down streets). Different branches meet at nodes or junctions. The key property of a net- work is that at each junction the same amount comes in as comes out. The basic problem of network analysis is determining the flow of each branch when only partial information is known. Below is an illustrated example of a network, with partial flow information in some unspecified units (e.g. litres per minute or cars per hour). Flow through each branch is either an unknown variable or a known constant. Determine the set of all possible values for (x1 , x2 , x3 , x4 , x5 ). Note: The values are not allowed to be negative, otherwise the flow is in the opposite direction to what is depicted. 8  50 x5 30 60 x2 x4 30 40 x3 x1 10 Take-home problems: Exercise 8. (i) Write down a linear system to solve the following problem: Find all polynomials p(x) in x with coefficients in R and of degree ≤ 2 such that p(1) = 0, p(−1) = −2 p(0) = 11. (0.1) [Hint: p(x) = a2 x2 + a1 x + a0 for some a2 , a1 , a0 ∈ R.] (ii) Write down the augmented matrix of the system. (iii) Solve the system by performing EROs. (iv) Deduce the answer to the initial question and conclude that there are no polyno- mials of degree ≤ 1 satisfying (0.1). (v) How about polynomials of degree ≤ 3? Exercise 9. Anoek wishes to make a salad with three ingredients: avocado, broccoli, and chicken. The table below shows the nutrition information of these three foods (per serving). Ingredient Avocado Broccoli Chicken Calories 240 50 70 Protein (g) 5 5 15 Fiber (g) 10 6 0 If Anoek wants her salad to have 750 calories, while also having 45g of protein and 44g of fibre, what proportions of avocado, broccoli, and chicken should she use? Past exam problems: Exercise 10. (Midterm exam 2022: Linear Algebra for LST) Let k ∈ R. Consider the linear system x1 − x2 + x3 = k, x1 + kx2 + x3 = 1, kx1 + x2 = 1. (a) Write the augmented matrix of this linear system. 9  (b) Determine the values of k for which the linear system has (i) a unique solution, (ii) infinitely many solutions, (iii) no solution. Answers 1 (i) Consistent; (ii) Inconsistent; (iii) False 2 (i) in echelon form but not reduced echelon form (ii) x1 + x2 + x3 = 1, 2x2 + x3 = −1, x3 = 1 (iii) the system is consistent with the unique solution (x1 , x2 , x3 ) = (1, −1, 1). 1 0 −7 0 1 0 −7 1 " # " # 3 Reducing the first matrix gives 0 1 5 0 , while the second matrix is 01 5 0. 00 0 1 00 0 0 The first linear system has no solutions, while the second linear system’s solution set is {(7t + 1, −5t, t) : t ∈ R}.   2 −i −iλ 4 The matrix is row-equivalent to so only λ = 11 2 gives a consistent system 0 0 2λ − 11 and the solution set is − 4 i + 2i α, α : α ∈ C.  11
5 a) t ̸= 2 b) t = − 53 c) t ∈ R 6 {(a, b, c) | 2a + b + c = 0}. 7 {(40, 80 − t, t − 10, 60 − t, t) : t ∈ [10, 60]} (there are other ways to write the same set depending on which variable is chosen as the free parameter) 8 (i) With p(x) = a0 + a1 x + a2 x2 : a0 + a1 + a2 = 0, a0 − a1 + a2 = −2, a0 = 11. " 1 1 1 0 # (ii) à = 1 −1 1 −2 1 0 0 11 " 1 0 0 11 # (iii) Applying EROs to the augmented matrix à becomes 010 1 so there is a 0 0 1 −12 unique solution for the system: (a0 , a1 , a2 ) = (11, 1, −12) (iv) p(x) = 11 + x − 12x2 ; since a2 = −12 and cannot be zero, there are no solutions with deg ≤ 1 10  (v) Every solution of degree ≤ 3 is of the form p(x) = tx3 − 12x2 + (1 − t)x + 11 for some t ∈ R. 9 2 servings of avocado, 4 servings of broccoli, and 1 serving of chicken 10 a) The augmented matrix 1 −1 1 k   à = 1 k 1 1. k 1 0 1 b) (i) no solution if k = −1; (ii) infinitely many solutions if k = 0; (iii) unique solution if k ̸= 0, −1. 11