This is a beta course, so its structure, chapters, and examples may continue to change.

Gaussian Elimination

Elementary Row Operations

The Definition of Elementary Row Operations

The following three transformations of a matrix are called elementary row operations:

Interchanging two rows: interchange row $i$ and row $j$ of the matrix
Multiplying a row by a scalar: multiply a row of the matrix by a nonzero constant $k$
Adding a multiple of one row to another: add $k$ times row $j$ to row $i$ , written $R_i + kR_j$

Properties of Elementary Row Operations

Elementary Row Operations Do Not Change the Rank of a Matrix

Elementary row operations do not change the rank of the matrix.

Proof

Proof:

Interchanging two rows: does not change linear dependence
Multiplying by a scalar: does not change linear dependence
Adding a multiple: does not change linear dependence

The Matrix Representation of Elementary Row Operations

An elementary row operation is equivalent to left-multiplication by an elementary matrix.

Elementary matrices:

Interchange matrix: $E_{ij}$ denotes the matrix that interchanges row i and row j
Scaling matrix: $E_i(k)$ denotes the matrix that multiplies row i by k
Shear matrix: $E_{ij}(k)$ denotes the matrix that adds k times row j to row i

Gaussian Elimination

The Basic Idea of Gaussian Elimination

Idea: use elementary row operations to reduce the augmented matrix to row echelon form, then solve by back substitution.

Row Echelon Form Matrices

A matrix satisfying the following conditions is called a row echelon form matrix:

The zero rows (rows consisting entirely of zeros) lie below the nonzero rows
The first nonzero entry of each nonzero row (called the pivot) lies to the right of the pivot of the row above
The entries below each pivot are zero

Example:

\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 1 \end{array} \right)

The Steps of Gaussian Elimination

Steps:

Forward elimination: use elementary row operations to reduce the augmented matrix to row echelon form
Back substitution: start from the last row and solve for the unknowns one row at a time

An Example of Gaussian Elimination

Example 1: solve the system by Gaussian elimination: $\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 13 \\ x - y + 2z = 4 \end{cases}$

Solution:

Write down the augmented matrix:
$\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & 3 & 1 & 13 \\ 1 & -1 & 2 & 4 \end{array} \right)$
Forward elimination:
- $R_2 - 2R_1$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 1 \\ 1 & -1 & 2 & 4 \end{array} \right)$
- $R_3 - R_1$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 1 \\ 0 & -2 & 1 & -2 \end{array} \right)$
- $R_3 + 2R_2$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & -1 & 0 \end{array} \right)$
Back substitution:
- From the third row: $-z = 0$ , so $z = 0$
- From the second row: $y - z = 1$ , so $y = 1$
- From the first row: $x + y + z = 6$ , so $x = 5$
Solution: $x = 5$ , $y = 1$ , $z = 0$

Gauss-Jordan Elimination

The Idea of Gauss-Jordan Elimination

Idea: starting from row echelon form, go further and reduce the matrix to reduced row echelon form (the Jordan canonical form).

Reduced Row Echelon Form Matrices

A matrix satisfying the following conditions is called a reduced row echelon form matrix:

It is in row echelon form
Every pivot is 1
All the other entries in the column containing a pivot are zero

Example:

\left( \begin{array}{cccc} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 2 \end{array} \right)

The Steps of Gauss-Jordan Elimination

Steps:

Reduce to row echelon form by Gaussian elimination
Turn each pivot into 1
Turn the entries above each pivot into zero

Analysis of the Structure of the Solution

The Unique Solution

Condition: the system has a unique solution when the rank of the coefficient matrix equals the rank of the augmented matrix, and that common rank equals the number of unknowns.

Infinitely Many Solutions

Condition: the system has infinitely many solutions when the rank of the coefficient matrix equals the rank of the augmented matrix, and that common rank is less than the number of unknowns.

Form of the general solution: a particular solution plus the general solution of the homogeneous system

No Solution

Condition: the system has no solution when the rank of the coefficient matrix is less than the rank of the augmented matrix.

The Advantages and Disadvantages of Gaussian Elimination

Advantages

Universality: it applies to systems of linear equations of any size
Numerical stability: the numerical error accumulated during the computation is small
Ease of implementation: the algorithm is simple and easy to program
The structure of the solution can be analysed: the rank analysis tells you which case you are in

Disadvantages

Heavy computation: for large systems the amount of computation is considerable
Storage requirements: the whole augmented matrix has to be stored
Unsuitable for sparse matrices: for sparse matrices the efficiency is not high

Exercises

Exercise 1

Solve the system $\begin{cases} x + 2y = 5 \\ 3x - y = 4 \end{cases}$ by Gaussian elimination.

Reference Answer

Gaussian eliminationelementary row operationsaugmented matrixmatrix

Approach: Follow the steps of Gaussian elimination.

Steps:

The augmented matrix:
$\left( \begin{array}{cc|c} 1 & 2 & 5 \\ 3 & -1 & 4 \end{array} \right)$
Forward elimination: $R_2 - 3R_1$ : $\left( \begin{array}{cc|c} 1 & 2 & 5 \\ 0 & -7 & -11 \end{array} \right)$
Back substitution:
- From the second row: $-7y = -11$ , so $y = \frac{11}{7}$
- From the first row: $x + 2y = 5$ , so $x = 5 - 2 \times \frac{11}{7} = \frac{13}{7}$

Answer: $x = \frac{13}{7}$ , $y = \frac{11}{7}$

Exercise 2

Solve the system $\begin{cases} x + y + z = 0 \\ 2x + 2y + 2z = 0 \end{cases}$ by Gaussian elimination.

Reference Answer

Gaussian eliminationelementary row operationsaugmented matrixmatrix

Approach: Follow the steps of Gaussian elimination, noting that this is a homogeneous system.

Steps:

The augmented matrix:
$\left( \begin{array}{ccc|c} 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 0 \end{array} \right)$
Forward elimination: $R_2 - 2R_1$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right)$
Analyse the structure of the solution:
- The rank of the coefficient matrix is 1, and the number of unknowns is 3
- The number of free variables is 3-1=2
- Let $y = t$ and $z = s$ , then $x = -t - s$

Answer: $x = -t - s$ , $y = t$ , $z = s$ (where $t, s$ are arbitrary constants)

Exercise 3

Decide which case the system $\begin{cases} x + y = 1 \\ x + y = 2 \end{cases}$ falls into.

Reference Answer

Gaussian eliminationelementary row operationsaugmented matrixstructure of solutions

Approach: Use Gaussian elimination to analyse the structure of the solution.

Steps:

The augmented matrix:
$\left( \begin{array}{cc|c} 1 & 1 & 1 \\ 1 & 1 & 2 \end{array} \right)$
Forward elimination: $R_2 - R_1$ : $\left( \begin{array}{cc|c} 1 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right)$
Analysis:
- The rank of the coefficient matrix is 1
- The rank of the augmented matrix is 2
- The rank of the coefficient matrix is less than the rank of the augmented matrix

Answer: there is no solution

Exercise 4

Solve the system $\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 13 \\ x - y + 2z = 4 \end{cases}$ by Gauss-Jordan elimination.

Reference Answer

Gaussian eliminationelementary row operationsaugmented matrixmatrix

Approach: First reduce to row echelon form by Gaussian elimination, then reduce to reduced row echelon form by Gauss-Jordan elimination.

Steps:

The augmented matrix:
$\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & 3 & 1 & 13 \\ 1 & -1 & 2 & 4 \end{array} \right)$
Gaussian elimination:
- $R_2 - 2R_1$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 1 \\ 1 & -1 & 2 & 4 \end{array} \right)$
- $R_3 - R_1$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 1 \\ 0 & -2 & 1 & -2 \end{array} \right)$
- $R_3 + 2R_2$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & -1 & 0 \end{array} \right)$
Gauss-Jordan elimination:
- $R_3 \times (-1)$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right)$
- $R_2 + R_3$ : $\left( \begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right)$
- $R_1 - R_2 - R_3$ : $\left( \begin{array}{ccc|c} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right)$
Read off the solution directly: $x = 5$ , $y = 1$ , $z = 0$

Answer: $x = 5$ , $y = 1$ , $z = 0$

Exercise 5

Prove that: elementary row operations do not change the rank of a matrix.

Reference Answer

Gaussian eliminationelementary row operationsaugmented matrixrank of a matrix

Approach: Prove separately that each of the three elementary row operations leaves the rank unchanged.

Steps:

Interchanging two rows: does not change linear dependence, so it does not change the rank
Multiplying by a scalar: does not change linear dependence, so it does not change the rank
Adding a multiple: does not change linear dependence, so it does not change the rank

Answer: the proof is complete

Summary

Symbols Used in This Article

Symbol	Type	Pronunciation / Note	Meaning in This Article
$R_i + kR_j$	Mathematical symbol	row i plus k row j	The shear operation: add $k$ times row $j$ to row $i$
$E_{ij}$	Mathematical symbol	E sub i j	The elementary matrix that interchanges rows $i$ and $j$
$E_i(k)$	Mathematical symbol	E sub i of k	The elementary matrix that multiplies row $i$ by the nonzero constant $k$
$E_{ij}(k)$	Mathematical symbol	E sub i j of k	The elementary matrix for the shear operation
$k$	Mathematical symbol	k	The nonzero scalar multiplier used in a row operation

Basic Concepts of Systems of Linear Equations

Cramer's Rule

Found an issue with this content?

Tell us what could be improved.

Unlock Full Course ·

Your membership covers this course — no need to buy it again.

Login Required to Purchase

Payment Failed

Payment Successful!

Price History

Gaussian Elimination

Elementary Row Operations

The Definition of Elementary Row Operations

Properties of Elementary Row Operations

The Matrix Representation of Elementary Row Operations

Gaussian Elimination

The Basic Idea of Gaussian Elimination

Row Echelon Form Matrices

The Steps of Gaussian Elimination

An Example of Gaussian Elimination

Gauss-Jordan Elimination

The Idea of Gauss-Jordan Elimination

Reduced Row Echelon Form Matrices

The Steps of Gauss-Jordan Elimination

Analysis of the Structure of the Solution

The Unique Solution

Infinitely Many Solutions

No Solution

The Advantages and Disadvantages of Gaussian Elimination

Advantages

Disadvantages

Exercises

Exercise 1

Exercise 2

Exercise 3

Exercise 4

Exercise 5

Summary

Symbols Used in This Article

Send feedback