Row reduction

Row reduction (also called Gaussian elimination) is the easiest way to solve systems of linear equations by hand. We can use three elementary operations to manually compute the rank of a matrix and the inverse of an invertible matrix.

Elementary operations

Our three fundamental elementary row operations are to:

• Interchange two rows.
• Multiply one row by a non-zero number.
• Replace a row by: itself plus or minus a multiple of a different row.

We say a matrix is in row echelon form (REF) if:

• All the zeros are in the bottom.
• The leading entry in each row is to the right of the leading entry of the row above.
• All entries below a leading entry are zero.

We further say a matrix is in reduced row echelon form (RREF) if it is in REF form and:

• All the leading entries are ones (pivots).
• Each pivot is the only non-zero entry in its column.

Solutions can be consistent (with a unique or infinitely many solutions) or inconsistent.

Determinants

We can relate these operations to determinants. Say $A$ is a square matrix, and $B$ is obtained from some manipulation of $A$.

• If we divide a row of $A$ by a scalar $k$, then $\text{det}(B)=\frac{1}{k}\text{det}(A)$.
• If we swap a row, then $\text{det}(B)=-\text{det}(A)$.
• If we add a multiple of $A$ to another row, then $\text{det}(B)=\text{det}(A)$.

Computer assisted

We can compute the row-reduced echelon form of matrices quickly in MATLAB and NumPy. We first set a matrix A and optionally a vector b, for $A\vec{x}=\vec{b}$.

In NumPy, we can use np.linalg.solve(A, b), which outputs a NumPy array.

In MATLAB

• linsolve(A, b) can only solve systems of linear equations. Its execution time is faster than other methods, and outputs a solution vector.
• A\b, the backslash operator, similarly outputs a solution vector for a system of linear equations. If A is $m\times n$, and b has m rows, then it returns a least squares solution. It typically runs slower than linspace.
• rref([A, b]) (or rref(A) for a non-augmented matrix) returns the row-reduced echelon form of the matrix, and can be used to row reduce augmented matrices.