Elementary operations, echelon form and rank – Transformation of Matrices (Senior 6 Mathematics) | Ganzaa

Transformation of Matrices

Lessons

Senior 6 · Mathematics

Transformation of Matrices

5 lessons

Lesson 1 of 5

Elementary operations, echelon form and rank

35 min

One method for every matrix

In S5 you solved three equations in three unknowns with determinants and Cramer's rule. That method needs a square matrix with a non-zero determinant, and it grows heavy quickly: a $4 \times 4$ determinant expanded by cofactors needs four $3 \times 3$ determinants. Computers that solve systems of thousands of equations (in weather models, electricity grids and image processing) use instead the method of this lesson, elimination: change the matrix one simple step at a time until its structure is obvious.

The steps are called elementary operations. They work on a matrix of any shape, and they never change the facts you are trying to find: the rank of the matrix, and the solutions of the system it stands for.

Definition

Elementary row operations on a matrix are the three moves

swap two rows: $R_i \leftrightarrow R_j$ ;
scale a row by a non-zero number: $R_i \to kR_i$ , $k \ne 0$ ;
replace a row by itself plus a multiple of another row: $R_i \to R_i + kR_j$ , $j \ne i$ .

The elementary column operations are the same moves on columns, written $C_i \leftrightarrow C_j$ , $C_i \to kC_i$ and $C_i \to C_i + kC_j$ .

Two matrices are equivalent, written $A \sim B$ , when one can be turned into the other by a finite sequence of elementary operations. Example: $\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \xrightarrow{R_2 \to R_2 - 3R_1} \begin{pmatrix} 1 & 2 \\ 0 & -2 \end{pmatrix}$ , so the two matrices are equivalent.

Important

Every elementary operation can be undone by another one. A swap is undone by the same swap, $R_i \to kR_i$ by $R_i \to \frac{1}{k}R_i$ , and $R_i \to R_i + kR_j$ by $R_i \to R_i - kR_j$ . This is why $k \ne 0$ in a scaling: multiplying a row by 0 destroys it and cannot be undone.

Because each step is reversible, row operations on the augmented matrix of a linear system give a system with exactly the same solutions, and row or column operations on any matrix leave its rank unchanged.

Elementary matrices

Each row operation is a matrix multiplication in disguise. Do the operation on the identity matrix $I_{m}$ : the result $E$ is an elementary matrix, and doing the operation on any $m \times n$ matrix $A$ gives $E A$ . For $3 \times 3$ matrices:

Operation	Elementary matrix $E$	Effect on a determinant
$R_1 \leftrightarrow R_2$	$\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$	changes its sign: $\det E = -1$
$R_3 \to 5R_3$	$\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 5 \end{pmatrix}$	multiplies it by 5: $\det E = 5$
$R_2 \to R_2 - 2R_1$	$\begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$	none: $\det E = 1$

Check the last one: $\begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & -1 \\ 2 & 5 & 1 \\ 3 & 7 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 2 & -1 \\ 0 & 1 & 3 \\ 3 & 7 & 0 \end{pmatrix}$ , which is the original matrix with $R_{2}$ replaced by $R_{2} - 2 R_{1}$ . A column operation is done by multiplying on the right, $A E$ , with $E$ built from the identity $I_{n}$ by the same column move.

Since $\det(EA) = \det E \cdot \det A$ , the table gives the rule for determinants: a swap changes the sign, scaling a row by $k$ multiplies the determinant by $k$ , and a replacement changes nothing.

Definition

Row echelon form. A matrix is in row echelon form when

every zero row (a row of zeros only) is below all the non-zero rows, and
the first non-zero entry of each non-zero row, its pivot (or leading entry), is in a column strictly to the right of the pivot of the row above.

It follows that every entry below a pivot is 0. The matrix is in reduced row echelon form when, in addition, every pivot is 1 and is the only non-zero entry of its column. Example: $\begin{pmatrix} 1 & 0 & -7 \\ 0 & 1 & 3 \\ 0 & 0 & 0 \end{pmatrix}$ is in reduced row echelon form.

Row echelon form. The pivots (circled) step down and to the right; below the staircase every entry is zero.

Definition

Rank of a matrix $A$ , written $\operatorname{rank} A$ (or $r (A)$ ): the number of non-zero rows in any row echelon form of $A$ , that is, the number of pivots. Example: the matrix in the figure has rank 3.

Different sequences of operations can give different echelon forms, but they always have the same number of pivots, so the rank is well defined. For an $m \times n$ matrix, $\operatorname{rank} A \le \min(m, n)$ , because there is at most one pivot in each row and in each column.

The elimination algorithm

Find the first column (from the left) that is not all zeros. If its top entry is 0, swap in a row with a non-zero entry there. That entry is the pivot.
Use replacements $R_i \to R_i - \frac{a_{i}}{p}R_1$ to make every entry below the pivot $p$ equal to 0.
Cover the pivot's row and repeat on the rows below it, until no non-zero rows remain.
For the reduced form, scale each pivot to 1 and clear the entries above it, working from the last pivot upwards.

Write each operation beside the arrow, so that you, and an examiner, can check every step.

Worked example 1: echelon form, reduced form and rank

Reduce $A = \begin{pmatrix} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 4 \\ 3 & 7 & 0 & 7 \end{pmatrix}$ to row echelon form, then to reduced row echelon form, and state its rank.

Solution. The pivot of column 1 is the 1 in row 1. Clear below it:

A \xrightarrow[R_3 \to R_3 - 3R_1]{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & -2 \\ 0 & 1 & 3 & -2 \end{pmatrix} \xrightarrow{R_3 \to R_3 - R_2} \begin{pmatrix} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & -2 \\ 0 & 0 & 0 & 0 \end{pmatrix} .

This is a row echelon form with two pivots, so $\operatorname{rank} A = 2$ . Row 3 became zero because $R_{3} = R_{1} + R_{2}$ in the original matrix: the rows are linearly dependent. For the reduced form, clear the 2 above the second pivot:

\xrightarrow{R_1 \to R_1 - 2R_2} \begin{pmatrix} 1 & 0 & -7 & 7 \\ 0 & 1 & 3 & -2 \\ 0 & 0 & 0 & 0 \end{pmatrix} .

Worked example 2: a rank that depends on a parameter

For which values of the real number $k$ does $B = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 1 & 3 & k \end{pmatrix}$ have rank 3? What is its rank otherwise?

Solution.

B \xrightarrow[R_3 \to R_3 - R_1]{R_2 \to R_2 - R_1} \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 2 & k-1 \end{pmatrix} \xrightarrow{R_3 \to R_3 - 2R_2} \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & k-5 \end{pmatrix} .

If $k \ne 5$ , the entry $k - 5$ is a third pivot and $\operatorname{rank} B = 3$ . If $k = 5$ , row 3 is zero and $\operatorname{rank} B = 2$ .

Check with a determinant. Only replacements were used, so $\det B$ equals the product of the diagonal of the triangular matrix: $1 \times 1 \times (k - 5) = k - 5$ . A square matrix has full rank exactly when its determinant is not zero, which agrees.

Worked example 3: a determinant by row reduction

Evaluate $\det \begin{pmatrix} 0 & 2 & 4 \\ 1 & 3 & 2 \\ 2 & 1 & 5 \end{pmatrix}$ by reducing to triangular form.

Solution. Keep a record of every operation that changes the determinant.

\begin{pmatrix} 0 & 2 & 4 \\ 1 & 3 & 2 \\ 2 & 1 & 5 \end{pmatrix} \xrightarrow{R_1 \leftrightarrow R_2} \begin{pmatrix} 1 & 3 & 2 \\ 0 & 2 & 4 \\ 2 & 1 & 5 \end{pmatrix} \xrightarrow{R_3 \to R_3 - 2R_1} \begin{pmatrix} 1 & 3 & 2 \\ 0 & 2 & 4 \\ 0 & -5 & 1 \end{pmatrix} \xrightarrow{R_3 \to R_3 + \frac{5}{2}R_2} \begin{pmatrix} 1 & 3 & 2 \\ 0 & 2 & 4 \\ 0 & 0 & 11 \end{pmatrix} .

The triangular matrix has determinant $1 \times 2 \times 11 = 22$ . One swap was made, which changed the sign, and the replacements changed nothing, so the original determinant is $- 22$ . (Cofactor expansion along row 1 gives $0 - 2 (5 - 4) + 4 (1 - 6) = - 22$ , the same.)

Warning

One operation at a time, each using rows as they are now. Writing $R_1 \to R_1 - R_2$ and $R_2 \to R_2 - R_1$ in the same step is a mistake: the second operation needs the new $R_{1}$ , and doing both at once can wipe out information. Several replacements may share a step only if they all use the same unchanged pivot row, as in worked example 1.

Do not use column operations on an augmented matrix. A column operation mixes the unknowns, so the solutions change. Columns may be used freely when you only want the rank.

Tip

To find a rank quickly, look for rows that are multiples or sums of other rows before you compute: in $\begin{pmatrix} 2 & 4 & 6 \\ 1 & 2 & 3 \\ 3 & 6 & 9 \end{pmatrix}$ every row is a multiple of $(1, 2, 3)$ , so the rank is 1 at sight.

MIT OpenCourseWare: Lecture 2 of 18.06 Linear Algebra, Elimination with Matrices, with Gilbert Strang (about 48 min). Watch how each elimination step is written as an elementary matrix, the same idea as the table in this lesson.

✦

Practice

Questions 1 to 4 are routine; 5 and 6 need more care; 7 asks for a reason.

Reduce $\begin{pmatrix} 1 & -1 & 2 \\ 2 & -1 & 5 \\ -1 & 3 & 0 \end{pmatrix}$ to row echelon form and state its rank.
Write the $3 \times 3$ elementary matrices for (a) $R_1 \leftrightarrow R_3$ and (b) $R_3 \to R_3 + 4R_2$ .
Find the rank of $\begin{pmatrix} 1 & 2 & 0 & 1 \\ 2 & 4 & 1 & 4 \\ 1 & 2 & 1 & 3 \end{pmatrix}$ . In which columns are the pivots?
Evaluate $\det \begin{pmatrix} 2 & 1 & 3 \\ 4 & 5 & 7 \\ -2 & 4 & 1 \end{pmatrix}$ by reducing to triangular form.
Find the reduced row echelon form of $\begin{pmatrix} 2 & 4 & -2 \\ 1 & 3 & 1 \\ 3 & 7 & -1 \end{pmatrix}$ .
Find the rank of $\begin{pmatrix} k & 1 & 1 \\ 1 & k & 1 \\ 1 & 1 & k \end{pmatrix}$ for every real $k$ . (Hint: start with $R_1 \leftrightarrow R_3$ .)
A $3 \times 5$ matrix has rank $r$ . What values can $r$ take? Explain why it cannot be 4.

Show answersHide answers

$R_2 \to R_2 - 2R_1$ , $R_3 \to R_3 + R_1$ , then $R_3 \to R_3 - 2R_2$ : $\begin{pmatrix} 1 & -1 & 2 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}$ , rank 2.
(a) $\begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}$ (b) $\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 4 & 1 \end{pmatrix}$
$R_2 \to R_2 - 2R_1$ , $R_3 \to R_3 - R_1$ , $R_3 \to R_3 - R_2$ give $\begin{pmatrix} 1 & 2 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}$ : rank 2, pivots in columns 1 and 3.
$R_2 \to R_2 - 2R_1$ , $R_3 \to R_3 + R_1$ , $R_3 \to R_3 - \frac{5}{3}R_2$ give the diagonal $2, 3, \frac{7}{3}$ : $\det = 14$ .
$\begin{pmatrix} 1 & 0 & -5 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{pmatrix}$ (rank 2).
The determinant is $(k - 1)^{2} (k + 2)$ . Rank 3 if $k \ne 1$ and $k \ne -2$ ; rank 1 if $k = 1$ (all rows equal); rank 2 if $k = - 2$ .
$r \in \{0, 1, 2, 3\}$ . There is at most one pivot per row and only 3 rows, so $r \le \min(3, 5) = 3$ .

Sources and credits

Written by Ganzaa: the explanations, the diagram, the worked examples, the practice items and the quiz questions. Every reduction, rank and determinant was checked with exact fraction arithmetic.
Video: 2. Elimination with Matrices, MIT 18.06 Linear Algebra, Gilbert Strang, MIT OpenCourseWare, embedded from YouTube.

1One method for every matrix

2Elementary matrices

3The elimination algorithm

One method for every matrix

Elementary matrices

The elimination algorithm