5. In a matrix, the number of leading zeros in Row 2' is the number of zeros in that row to the left of the rst non-zero entry of that row (if the row contains any nonzero entry). A matrix A is called a row echelon if the number of leading zeros strictly increases row by row until reaching maximum: Row 1' + 1 contains weakly more leading zeros than ROW '5' and strictly so unless Row '5' has no non-zero entry. The following matrix is a row echelon: 0 3 0 5 0 0 3 1 0 0 0 0 0 0 0 0 The following matrix is not a row echelon because the third row contains no leading zero: 3 0 5 0 2 3 1 0 0 Gaussian elimination is a procedure that reduces the augmented matrix of a linear system to a row echelon using the three elementary row operations. In a linear system A1: = b where A is a row echelon, a pivot in a row of A is the rst nonzero entry (if any) of that row; if a column of A does not contain a pivot, the corresponding unknown is called a free unknown. The goal of this question is to prove the following claim: Proposition 1. Assume that a linear system Ass 2 5 satises the following two conditions: (1) A is a row echelon. (2) If all entries in the jth row ofA are zero, then the jth row ofb is also zero. (This holds for all j.) Then for any values assigned to the free unknowns of the system, the system has a unique solution in which the values of the free unknowns are as assigned. (a) [5 marks] Does the proposition hold without Condition (2)? (b) [5 marks] Daniel suggests the following proof of the proposition. Proof. Assume that the proposition holds when A has at most n columns. Consider the case where A has n + 1 columns. Denote the submatrix of A consisting of its rst n columns by A, the last column of A by u, the rst n rows of s: by ft, and the last row (entry) of x by In+1. Then the linear system can be rewritten as ALT: + $n+1u = h. (1) (This should be clear from the column picture of matrix multiplication. For the purpose of this question, you are assured that Eq. (1) is correct.) We show that only one value of $n+1 works. Case 1 Column n + 1 of A does not contain a pivot. In this case, $n+1 is a free variable and has to take the value assigned to it. Case 2 Column n + 1 of A contains a pivot. Assume that the pivot of this column is in Row 3'. Then by the denition of pivots, all entries in the jth row of A must be zero. The jth row of both sides of Eq. (1) now reads UjIn+1 = bj, where uj and 5;; are the jth components of u and b, respectively. By the denition of pivots again, by 75 0. Therefore, $n+1 = bj/uj. Now let xf,+1 be the unique $n+1 found above. Then Eq. (1) implies that Ai = b 33:; +11\" Notice that A has only n columns. By induction hypothesis, there is a unique :7: that works. Combining that i with 33;+1 yields the unique 33. El