# Square Matrix is Row Equivalent to Triangular Matrix/Proof 2

## Theorem

Let $\mathbf A = \left[{a}\right]_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

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 = \left[{a}\right]_{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 $\mathbf A \left({1; 1}\right)$ is.

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

So when $\mathbf A \left({1; 1}\right)$ 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_{11} = 0$.

Let $j$ be the smallest row index such that $a_{j1} \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_{j1} \ne 0$, this enforces $a_{11} \ne 0$, and we continue as in the case below.

Suppose $a_{11} \ne 0$.

We use the following operations of type 2:

- $\forall j \in \left\{{2, \ldots, n+1}\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 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$