Square Matrix Row Equivalent to Triangular Matrix

Theorem

Let $\mathbf A = \left[{a}\right]_{n}$ be a square matrix of order $n$.

Then $\mathbf A$ can be converted to an upper or lower triangular matrix by elementary row operations of type 2: $r_i \to r_i + ar_j$.

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$. Assume all $n \times n$-matrices can be diagonalised by elementary row operations of type 2.

This forms our induction hypothesis.

Induction Step

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

When the first column of $\mathbf A$ contains only zeroes, it is upper triangularisable iff the submatrix $\mathbf A \left({1; 1}\right)$ is.

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

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

Furthermore, suppose $a_{11} \ne 0$. We use the following operations of type 2:

$\forall j \in \left[{2 .. n}\right]: r_j \to r_j - \dfrac {a_{j1}} {a_{11}} r_1$

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

It follows that $\mathbf A$ can be upper triangularised precisely when the submatrix $\mathbf A \left({1; 1}\right)$ can.

Again, the induction hypothesis renders $\mathbf A$ upper triangularisable.

The remaining case is when $a_{11} = 0$.

We will reduce this to the above case by type 2 operations.

Let $j$ be the smallest index such that $a_{j1} \ne 0$. Note that $j$ exists by assumption.

Now apply the following type 2 operation:

$r_1 \to r_1 + r_j$

As $a_{j1} \ne 0$, this enforces $a_{11} \ne 0$, and we reduce to above case.

So again $\mathbf A$ is upper triangularisable by elementary row operations of type 2.

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 row and the last diagonal element $a_{nn}$.

$\blacksquare$