Square Matrix is Row Equivalent to Triangular Matrix/Proof 1

Theorem

Let $\mathbf A = \sqbrk a_n$ be a square matrix of order $n$ over a commutative ring $R$.

Then $\mathbf A$ can be converted to an upper or lower triangular matrix by elementary row operations.

Proof

Let $\mathbf A$ be a square matrix of order $n$.

We proceed by induction on $n$, the number of rows of $\mathbf A$.

Basis for the Induction

For $n = 1$, we have a matrix of just one element, which is trivially diagonal, hence both upper and lower triangular.

This is the basis for the induction.

Induction Hypothesis

Fix $n \in \N$, and assume all $n \times n$-matrices can be upper triangularised by elementary row operations.

If $R$ is a field, assume all $n \times n$-matrices can be upper triangularised by elementary row operations of type $2$.

This forms our induction hypothesis.

Induction Step

Let $\mathbf A = \sqbrk a_{n + 1}$ be a square matrix of order $n + 1$.

When the first column of $\mathbf A$ contains only zeroes, it is upper triangularisable if and only if the submatrix $\map {\mathbf A} {1; 1}$ is.

Each elementary row operation used in triangularisation process of the submatrix $\map {\mathbf A} {1; 1}$ will not change the zeros of the first column of $\mathbf A$.

So when $\map {\mathbf A} {1; 1}$ is upper triangularised, then $A$ will also be upper triangularised.

From the induction hypothesis, we conclude that $\mathbf A$ can be upper triangularised by elementary row operations.

Now suppose that its first column contains a non-zero value.

Suppose that $a_{1 1} = 0$.

Let $j$ be the smallest row index such that $a_{j 1} \ne 0$, and note that $j$ exists by assumption.

Now apply the following operation of type $2$:

$r_1 \to r_1 + r_j$

As $a_{j 1} \ne 0$, this enforces $a_{1 1} \ne 0$, and we continue as in the case below.

Suppose $a_{1 1} \ne 0$.

We use the following operations for all $j \in \set {2, \ldots, n + 1}$:

$(1): \quad$ Put $c = a_{j 1}$.

$(2): \quad r_j \to a_{1 1} r_j$

$(3): \quad r_j \to r_j - c r_1$

This will put the first column to zero (except for the first element, $a_{1 1}$).

It follows that $\mathbf A$ can be upper triangularised if and only if the submatrix $\map {\mathbf A} {1; 1}$ can.

Again, the induction hypothesis renders $\mathbf A$ upper triangularisable by elementary row operations.

This completes the case distinction, and hence the result follows by induction.

To put the matrix $\mathbf A$ into lower triangular form, just do the same thing, but start with the last column and the last diagonal element $a_{n + 1 \; n + 1}$.

$\blacksquare$