Skip to content
VidiMaster it, module by module
Module 2/Systems & Gaussian Elimination

Row-Echelon Form & the Gauss Algorithm

The staircase shape at the heart of Gaussian elimination: what row-echelon form means, how the recursive Gauss algorithm produces it step by step, and how counting pivots gives you the rank of any matrix.

Before you start — give these a try

Attempting first primes your brain for the lesson — even if you miss. Nothing is graded or saved; it's just a warm-up.

Find rank(A)\text{rank}(A) for A=[123246111]A=\begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 1 & 1 & 1 \end{bmatrix} by reducing it to row-echelon form.

Apply the first stage of the Gauss algorithm to A=[121354233]A=\begin{bmatrix} 1 & 2 & 1 \\ 3 & 5 & 4 \\ 2 & 3 & 3 \end{bmatrix}: using the pivot a11=1a_{11}=1, create zeros below it (clear the first column). Enter the resulting matrix.

What you’ll be able to do

  • State the two conditions of Definition 5.3 and decide whether a given matrix is in row-echelon form.
  • Identify the leading entry (pivot) of each row and the pivot columns of a matrix.
  • Carry out the Gaussian elimination algorithm gauss(i,j)\text{gauss}(i,j) — including row swaps and clearing below pivots — to reduce a matrix to row-echelon form.
  • Determine the rank of a matrix by counting the pivots in a row-echelon form.
  • Explain why elementary row operations leave the rank unchanged (Theorem 5.1) and why the pivot count is well-defined (Remark 5.2).

In your course

· MATH2015 · Linear Algebra & Probability
§5.2 Gauss elimination algorithm§5.1 Elementary Row Operations & Elementary Matrices
  • Definition 5.3Row-echelon form
    A matrix is in row-echelon form if (1) all rows consisting only of zeros are at the bottom, and (2) the leading entry (pivot) of every nonzero row is to the right of the leading entry of every row above it.
  • Definition 5.1Elementary row transformations
    (1) Interchange two rows; (2) multiply a row by a scalar λ≠0\lambda\neq 0; (3) add λ\lambda times row rjr_j to row rir_i (with i≠ji\neq j).
  • Theorem 5.1Row operations preserve rank
    Elementary row transformations do not change the row rank of a matrix.
  • Example 5.3Gauss elimination on a 4×3 matrix
    The matrix [01234567891011]\begin{bmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \\ 9 & 10 & 11 \end{bmatrix} reduces to a row-echelon form with two pivots, so its rank is 2.
  • Remark 5.2Uniqueness of pivot positions
    The row-echelon form is not unique, but all row-echelon forms and the (unique) reduced row-echelon form have the same number of zero rows, with pivots in the same rows and columns.
This lesson covers §5.2, reducing a matrix to row-echelon form via Gaussian elimination and reading off its rank. The Gauss–Jordan refinement to reduced row-echelon form (Definition 5.4) and its use for computing matrix inverses (§5.3) build directly on this same algorithm.
1

Row-echelon form (Definition 5.3)

A matrix is in row-echelon form (REF) when two conditions hold. First, every row of all zeros sits at the bottom of the matrix. Second, the leading entry (pivot) of each nonzero row — its left-most nonzero entry — lies strictly to the right of the pivot in the row above. The result is a staircase pattern descending to the right. For instance [345012000]\begin{bmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{bmatrix} is in REF: pivots in columns 1 and 2, with the zero row last.

2

Leading entries and pivots

The leading entry, or pivot, of a nonzero row is its left-most nonzero entry. Pivots anchor the whole method: in REF every pivot has only zeros beneath it in its column, and the columns that contain pivots are called pivot columns. Counting pivots is exactly how we read off the rank. A pivot need not equal 11; normalizing each pivot to 11 (and also clearing the entries above it) is the extra step that produces the reduced row-echelon form.

3

The Gauss elimination algorithm $\text{gauss}(i,j)$

Gaussian elimination applies elementary row operations systematically to reach REF. It is the recursive procedure gauss(i,j)\text{gauss}(i,j), started at i=j=1i=j=1: (1) if ii equals the number of rows or jj exceeds the number of columns, stop; (2) if aij=0a_{ij}=0, search for a row k>ik>i with akj≠0a_{kj}\neq 0 — if none exists, move right by calling gauss(i,j+1)\text{gauss}(i,j+1), otherwise swap that row up into row ii; (3) with a nonzero pivot aija_{ij} in place, for every row k>ik>i subtract akjaij\frac{a_{kj}}{a_{ij}} times row ii from row kk, creating zeros below the pivot; (4) recurse on the sub-matrix by calling gauss(i+1,j+1)\text{gauss}(i+1,j+1). Apart from the occasional swap, the entire algorithm is a single repeated move: subtract akjaij\frac{a_{kj}}{a_{ij}} times the pivot row from each lower row.

4

Reading off the rank

Once AA is in row-echelon form, its rank is the number of pivots, equivalently the number of nonzero rows. This is valid because elementary row operations preserve rank (Theorem 5.1) and the nonzero rows of an REF are linearly independent. In Example 5.3 a 4×34\times 3 matrix reduces to an REF with 22 pivots, so rank(A)=2\text{rank}(A)=2: the two all-zero rows contribute nothing to the rank.

Theorem 5.1 — Row operations preserve rank

The elementary row transformations — (1) interchanging two rows, (2) multiplying a row by a scalar λ≠0\lambda\neq 0, and (3) adding λ\lambda times one row to another — do not change the row rank of a matrix.

Intuition. Each elementary operation only re-describes the same row space with different combinations of the same rows; it never creates or destroys linear independence. So the number of independent rows (the rank) is unchanged, which is precisely what lets us compute the rank by simplifying all the way down to a row-echelon form.
Rank equals the number of pivots

If RR is any row-echelon form of AA produced by Gaussian elimination, then rank(A)\text{rank}(A) equals the number of pivots of RR (equivalently, the number of nonzero rows of RR).

Intuition. In an REF the nonzero rows form a staircase: each pivot sits in a column where every row below it is zero, so no nonzero row can be built from the others. The pivot rows are therefore linearly independent, and because row operations preserved the rank, their count is exactly the rank of the original matrix.
Remark 5.2 — Pivots are well-defined

The row-echelon form of a matrix is not unique, but every row-echelon form (and the unique reduced row-echelon form) has the same number of zero rows, and the pivots occur in the same rows and columns.

Intuition. Different choices of operations can give different-looking echelon forms, yet the shape of the staircase — how many steps there are and where they sit — is forced by the matrix itself. That is why counting pivots yields one well-defined rank, no matter how you run the elimination.

Worked examples

Example 1

(Example 5.3) Find a row-echelon form of A=[01234567891011]A=\begin{bmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \\ 9 & 10 & 11 \end{bmatrix} and then determine rank(A)\text{rank}(A).

  1. 1

    Step 1 (first column, gauss(1,1)\text{gauss}(1,1)). The pivot candidate a11=0a_{11}=0, so look below it for a nonzero entry. Since a21=3≠0a_{21}=3\neq 0, swap rows 1 and 2: [01234567891011]→r1↔r2[34501267891011]\begin{bmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \\ 9 & 10 & 11 \end{bmatrix} \xrightarrow{r_1\leftrightarrow r_2} \begin{bmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 6 & 7 & 8 \\ 9 & 10 & 11 \end{bmatrix}. The entry 33 at position (1,1)(1,1) is the first pivot.

  2. 2

    Clear below the first pivot. Subtract 63=2\frac{6}{3}=2 times row 1 from row 3, and 93=3\frac{9}{3}=3 times row 1 from row 4: →−2r1+r3−3r1+r4[3450120−1−20−2−4]\xrightarrow{\substack{-2r_1+r_3\\ -3r_1+r_4}} \begin{bmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 0 & -1 & -2 \\ 0 & -2 & -4 \end{bmatrix}. (Check: (6,7,8)−2(3,4,5)=(0,−1,−2)(6,7,8)-2(3,4,5)=(0,-1,-2) and (9,10,11)−3(3,4,5)=(0,−2,−4)(9,10,11)-3(3,4,5)=(0,-2,-4).)

  3. 3

    Step 2 (gauss(2,2)\text{gauss}(2,2)). Move down one row and right one column. The entry a22=1≠0a_{22}=1\neq 0 is the second pivot. Clear below it by adding row 2 to row 3 (multiplier −11=−1\frac{-1}{1}=-1) and twice row 2 to row 4 (multiplier −21=−2\frac{-2}{1}=-2): →r2+r32r2+r4[345012000000]=ref(A)\xrightarrow{\substack{r_2+r_3\\ 2r_2+r_4}} \begin{bmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} = \text{ref}(A). (Check: (0,−1,−2)+(0,1,2)=(0,0,0)(0,-1,-2)+(0,1,2)=(0,0,0) and (0,−2,−4)+2(0,1,2)=(0,0,0)(0,-2,-4)+2(0,1,2)=(0,0,0).)

  4. 4

    Step 3 (termination). The remaining sub-matrix (rows 3 and 4) is all zeros, so the algorithm stops. The REF has pivots in positions (1,1)(1,1) and (2,2)(2,2).

Answer. A row-echelon form is [345012000000]\begin{bmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}, which has 22 pivots, so rank(A)=2\text{rank}(A)=2.
Example 2

Use the Gauss algorithm to reduce B=[011123258]B=\begin{bmatrix} 0 & 1 & 1 \\ 1 & 2 & 3 \\ 2 & 5 & 8 \end{bmatrix} to row-echelon form, and find its rank.

Example 3

Reduce C=[121243122]C=\begin{bmatrix} 1 & 2 & 1 \\ 2 & 4 & 3 \\ 1 & 2 & 2 \end{bmatrix} to row-echelon form and state its rank. Watch for a column with no available pivot.