Gaussian Elimination for solving systems of linear equations is an algorithm that should be very familiar to you. We will have need of it later in the course, and so it is nice for you to actually prove some basic properties that you already know that Gaussian Elimination satisfies. We will prove the termination of Gaussian Elimination Algorithm for input augmented matrix A ER"X(n+1). Let Ai[j] denote the entry of A in the ith row and jth column. Let A[i] denote the ith row of A, where i can range from 1 to n. The first equation of the system of linear equations is: A[1][1] X1 +A[1][2] . x2 + ... +A[1][n] Xn=A[1] [n+ 1] In general, for 1 r and A[i][c] +0, and swap it with row A[r]. If no such A[i] exists, increment c by 1 and skip the following three steps. 2. Scale row A[r] by multiplying it by Act, so A[r][c] becomes a 1. 3. For each value of r 1: 1. Use the values Xr. . Xn and plug them into the linear equation corresponding to Ar 1] = Ar 1] (n + 1]. 2. Solve the resulting linear equation for xr-1 3. Decrement r by 1. This gives us the unique solution if one exists. (a) Prove using induction that the forward pass of this algorithm always terminates for augmented matrix A E Rnx(n+1). (b) Prove using induction that the backward pass of the algorithm terminates if reached. (c) Prove using induction that the downward pass of the algorithm terminates with an upper- triangular matrix all the entries below the diagonal are zero. (d) Prove that the algorithm is correct for augmented matrix A E Rnx(n+1) for the case when a unique solution exists. To do this, you should first prove a lemma that shows that any solution to the original system of equations remains a solution to the modified system of equations at all iterations of the downward pass of the algorithm, and vice-versa: all solutions of the modified system of equations at all iterations are valid solutions to the original system of equations. Gaussian Elimination for solving systems of linear equations is an algorithm that should be very familiar to you. We will have need of it later in the course, and so it is nice for you to actually prove some basic properties that you already know that Gaussian Elimination satisfies. We will prove the termination of Gaussian Elimination Algorithm for input augmented matrix A ER"X(n+1). Let Ai[j] denote the entry of A in the ith row and jth column. Let A[i] denote the ith row of A, where i can range from 1 to n. The first equation of the system of linear equations is: A[1][1] X1 +A[1][2] . x2 + ... +A[1][n] Xn=A[1] [n+ 1] In general, for 1 r and A[i][c] +0, and swap it with row A[r]. If no such A[i] exists, increment c by 1 and skip the following three steps. 2. Scale row A[r] by multiplying it by Act, so A[r][c] becomes a 1. 3. For each value of r 1: 1. Use the values Xr. . Xn and plug them into the linear equation corresponding to Ar 1] = Ar 1] (n + 1]. 2. Solve the resulting linear equation for xr-1 3. Decrement r by 1. This gives us the unique solution if one exists. (a) Prove using induction that the forward pass of this algorithm always terminates for augmented matrix A E Rnx(n+1). (b) Prove using induction that the backward pass of the algorithm terminates if reached. (c) Prove using induction that the downward pass of the algorithm terminates with an upper- triangular matrix all the entries below the diagonal are zero. (d) Prove that the algorithm is correct for augmented matrix A E Rnx(n+1) for the case when a unique solution exists. To do this, you should first prove a lemma that shows that any solution to the original system of equations remains a solution to the modified system of equations at all iterations of the downward pass of the algorithm, and vice-versa: all solutions of the modified system of equations at all iterations are valid solutions to the original system of equations