Row Echelon Form

Reduce a matrix to row echelon form by Gaussian elimination.

A matrix is in row echelon form when every all-zero row sits at the bottom, and the leading non-zero entry of each row (its pivot) is strictly to the right of the pivot in the row above.

Use this convention so the answer is unique:

• Work left to right through the columns. For the current pivot row, pick the row at or below it whose entry in this column has the largest absolute value, and swap it up. Choosing the largest pivot is partial pivoting, and it is what keeps elimination numerically stable.
• If the whole column below the pivot row is zero (within 1e-12), move to the next column without advancing the pivot row.
• Divide the pivot row by its pivot so the leading entry is exactly 1.
• Subtract multiples of the pivot row from every row below it to zero out the rest of the column.

Do not modify the caller's array.

Function signature

def row_echelon_form(A):

Example

Input

row_echelon_form(np.array([[1.0, 2.0], [2.0, 4.0]]))

Output

array([[1., 2.],
       [0., 0.]])

Reasoning

Partial pivoting picks 2 as the first pivot, so the rows swap and the pivot row becomes [1, 2]. Subtracting it from [1, 2] leaves a zero row. The second column has no pivot left.

Constraints and notes

• Pick the row with the largest absolute value as the pivot.
• Scale each pivot row so its pivot is 1.
• Do not change the caller's array.