Square Matrix is Row Equivalent to Triangular Matrix
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 1
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$
Proof 2
This proof assumes that $R$ is a field, which makes the triangulation process slightly quicker.
By this assumptions, all elements of $\mathbf A$ have multiplicative inverses.
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 $\mathbf 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 of type $2$:
- $\forall j \in \set {2, \ldots, n + 1}: r_j \to r_j - \dfrac {a_{j 1}} {a_{1 1}} 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$