Exercise 2.6. In this problem we will look at the problem of solving a system of linear equa- tions over Fg. That is, one needs to solve for unknowns X1,..., Xn given the following m linear equations (where ai,j,b Fg for lsism and 1sjsn): a1,1x1 + a1,2X2++ a1,nxn = b. 22,1X1 + a2,2X2 + ... + 22,n Xn = b2. = : Am,1%] + am,2X2 + ... + am,nxn = bm. 1. (Warm-up) Convince yourself that the above problem can be stated as A x = b", where A is an mx n matrix over Fq, XEF, and be 2. (Upper Triangular Matrix) Assume n= m and that A is upper triangular, i.e. all diagonal elements (01,i) are non-zero and all lower triangular elements (di,j, i > j) are 0. Then present an O(n) time algorithm to compute the unknown vector x. 3. (Gaussian Elimination) Assume that A has full rank (or equivalently a rank of n.) (a) Prove that the following algorithm due to Gauss converts A into an upper triangular matrix. By permuting the columns if necessary make sure that 01,1 +0. (Why can one assume w.l.o.g. that this can be done?) Multiply all rows 1 j) are 0. Then present an O(n) time algorithm to compute the unknown vector x. 3. (Gaussian Elimination) Assume that A has full rank (or equivalently a rank of n.) (a) Prove that the following algorithm due to Gauss converts A into an upper triangular matrix. By permuting the columns if necessary make sure that 01,1 +0. (Why can one assume w.l.o.g. that this can be done?) Multiply all rows 1