Part A: Warmup

Implement the functionis upper triangle(a)that determines ifa(annnmatrix) is an upper triangle.

The function should returnTrueif all the elements above the main diagonal are non-zeros and everything

below it is zero otherwise returnFalse.

Part B: Row Echelon Form

A matrixAis said to be in 'row echelon form' if its non-zero entries describe a flipped staircase pattern.

Formally this means that:

-All rows ofAconsisting of only zeroes are at the bottom.

-The leading coefficient (also called the pivot) of a non-zero row ofAis always strictly to the right of the leading coefficient of the row above it.

Part C: General Forward Elimination

In practice, we might often encounter linear systems that do not have a unique solution. Based on the above proposition, we know that in these cases forward elimination, at least as defined in the lecture, must run into a situation where it cannot find a pivot row. Depending on how thepivot indexfunction and other details are implemented, this means that the algorithm either crashes or stops without simplifying subsequent rows. However, in fact even non-singular matrices can be further simplified to be in row echelon form.

-A functionechelon(a, b)which performs a modified form of forward elimination that transforms general input systems (including singular systems) into row echelon form.

Part D: General Back Substitution

If the advanced forward elimination algorithm from Part B found a pivot element in columnj, it will be the edge of a stair in the staircase pattern of the output matrix (which was therefore also called 'pivot' in the definition of row echelon form).

All variables (columns) in the linear system can be classified as either 'pivot variables' (if they have a pivot/edge in their column) or 'free variable' if they have not.

A modified version of the functionsolve by back substutionfrom the lecture that accepts a matrixuin row echelon form and a right-hand-side vectorband returns as output:

-None, if the system has no solution (Hint:This can be determined simply by checking whether the right-hand-side vector has a non-zero entry in any of the all-zero rows of the matrix)

-Implement a solution where all entries corresponding to free variables are 0 (Hint:All other values are then uniquely determined).