Gaussian Elimination — Solving Linear Syst

m equations in n unknowns \( (m \times n) \)

\[ \begin{cases} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 & (1) \\[2mm] a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 & (2) \\[2mm] a_{32} x_1 + a_{32} x_2 + \cdots + a_{3n} x_1 = b_3 & (3) \\[4mm] a_{i1} x_1 + \cdots + a_{ij} x_j + \cdots + a_{in} x_n = b_i & (i) \\[2mm] \vdots \qquad\quad \vdots \qquad\quad \vdots & \\[2mm] a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m & (m) \end{cases} \]

Gaussian Elimination – Solving Linear Systems

m equations in n unknowns \( (m \times n) \)

\[ \begin{cases} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 & (1) \\[2mm] a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 & (2) \\[2mm] a_{32} x_1 + a_{32} x_2 + \cdots + a_{3n} x_1 = b_3 & (3) \\[4mm] a_{i1} x_1 + \cdots + a_{ij} x_j + \cdots + a_{in} x_n = b_i & (i) \\[2mm] \vdots \qquad\quad \vdots \qquad\quad \vdots & \\[2mm] a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn} x_n = b_m & (m) \end{cases} \]

The coefficient \( a_{ij} \) is annotated to show its subscript meaning:

\[ a_{ij} \quad \underset{\text{row no.}}{\;i\;} \; \underset{\text{column number}}{\;j\;} \]

Gaussian Elimination – Solving Linear Systems

m equations in n unknowns \( (m \times n) \)

\[ \left[\begin{array}{ccccc|c} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n} & b_2 \\ a_{31} & a_{32} & a_{33} & \cdots & a_{3n} & b_3 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} & b_n \end{array}\right] \] coeff. matrix vs augmented matrix

Elementary Row Operations

(to eliminate variables)

  1. Interchange 2 rows (equations)

    \[ \begin{array}{c} (\text{---} \; R_i \; \text{---}) \\ (\text{---} \; R_j \; \text{---}) \end{array} \quad\longrightarrow\quad \begin{array}{c} (\text{---} \; R_j \; \text{---}) \\ (\text{---} \; R_i \; \text{---}) \end{array} \]

  2. Multiply 1 row (eqn) by a non-zero no.

    \[ (\text{---} \; R_i \; \text{---}) \quad \underset{(\alpha \ne 0)}{\xrightarrow{\;\times \alpha\;}} \quad (\text{---} \; \alpha R_i \; \text{---}) \]

  3. Add a multiple of 1 row (eqn) to another

    \[ \left. \begin{array}{c} (\text{---} \; R_i \; \text{---}) \\ (\text{---} \; R_j \; \text{---}) \end{array} \right\} + \alpha R_i \;\longrightarrow\; \begin{array}{c} (\text{---} \; R_i \; \text{---}) \\ (\text{---} \; \alpha R_i + R_j \; \text{---}) \end{array} \]

Elementary Row Operations (to eliminate variables)

Note: elementary row op. can be reversed.

Hence: the new system is equivalent to the original one in the sense that they have the same set of solutions.

\( \left[\; \text{System 1} \;\right] \;\rightleftarrows\; \left[\; \text{System 2} \;\right] \)

Row Echelon Form (REF) (to facilitate backward substitution)

  1. make this no. to be 1
  2. Use it to make all the no.s below it to be zero
Matrix schematic showing first pivot circled with instructions to make it 1 and zero out entries below it.
Figure 1
A hand-drawn matrix depicted with asterisks standing in for entries. The top-left entry of the matrix is circled in red, and a red arrow points to it labeled with instruction 1: make this number to be 1. The entire first column of entries below the circled pivot is highlighted in yellow, and a second red arrow points to this column labeled with instruction 2: use it to make all the numbers below it to be zero. The matrix is drawn with large square brackets, the first row showing entries followed by a dashed horizontal line indicating continuation, and a separate rightmost column of entries with a vertical dashed line indicating omitted rows.

Row Echelon Form (REF)

(to facilitate backward substitution)

Augmented matrix with first pivot 1 circled and zeros below it; red dashed box marks the remaining (m-1) by (n-1) subsystem to repeat.
Figure 2
A large square-bracket matrix. The first column contains a circled 1 at top, followed by 0, 0, a vertical dotted ellipsis, and 0 at the bottom, representing the pivot column after elimination. To the right of the first row are entries marked with asterisks and a dashed line indicating continuing entries. A red curved arrow from the left labeled 'x_1 is eliminated' points to the zeros in the first column. A red dashed rectangle encloses the lower-right block of the matrix (excluding the first row and first column), and a red brace beneath it is labeled '(m-1) x (n-1) system.' The word 'REPEAT!' appears in black to the right, indicating the procedure is repeated on this smaller submatrix. Asterisk entries also appear in the rightmost augmented column.

\( x_1 \) is eliminated

\( (m-1) \times (n-1) \) system. REPEAT!

Row Echelon Form (REF)

(to facilitate backward substitution)

Augmented matrix in row echelon form with circled 1s on the diagonal, zeros below, stars above, labeled upper triangular matrix.
Figure 3
An augmented matrix illustrating Row Echelon Form. The left block is a square coefficient matrix whose main diagonal entries are all circled 1s. Above the diagonal are asterisk symbols representing arbitrary nonzero entries, with a horizontal dashed line indicating continuation across the top row and a diagonal dashed line running from the third pivot down to the last pivot. Below the diagonal all entries are zero, indicated by handwritten zeros in the first column and the label O with an apostrophe s meaning zeros in the lower-left region. A vertical bar separates the coefficient block from an augmenting column on the right, which contains asterisks and a vertical dashed line indicating continuation. A red arrow at the bottom left points to the matrix with the label upper triangular matrix.

upper triangular matrix

Backward Substitution: Start from the last

Columns labeled \( x_1 \), \( x_2 \), \( x_3 \), \( x_4 \).

\[ \left[\begin{array}{cccc|c} 1 & 2 & -1 & 0 & 1 \\ 0 & 1 & 7 & 5 & 0 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 & -3 \end{array}\right] \]

Backward Substitution: Start from the last

Columns labeled \( x_1 \), \( x_2 \), \( x_3 \), \( x_4 \).

\[ \left[\begin{array}{cccc|c} 1 & 2 & -1 & 0 & 1 \\ 0 & 1 & 7 & 5 & 0 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 & -3 \end{array}\right] \]

\( x_3 + x_4 = 2 \)

\( x_3 = 5 \)

\( x_4 = -3 \)

\( x_2 + 7x_3 + 3x_4 = 0 \)

\( x_2 = -20 \)

\( x_1 + 2x_2 - x_3 = 1 \)

\( x_1 = 46 \)

Solution:

\[ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \begin{pmatrix} 46 \\ -20 \\ 5 \\ -3 \end{pmatrix} \]

Pivot vs Free Variables

It can happen that not all variables are "leading" in the row echelon form.

Staircase row echelon matrix with circled leading 1s on descending steps, stars to their right, and 0s below.
Figure 4
A large bracketed matrix drawn as a descending staircase. Along the diagonal are four circled leading 1s, each stepping down and to the right. To the right of each circled 1 are asterisks (stars) representing nonzero entries: the first row shows one star, the second row two stars, the third row one star, and the fourth row two stars. Below the staircase the region is filled with zeros, labeled O's. A dashed vertical line near the right side suggests an augmented column. Red arrows from the highlighted word 'leading' point to each circled 1, indicating these are the leading entries.
  • The variables corresponding to the 1's in the REF are called pivot variables.
  • The rest, non-leading, are called free variables.

Examples: Express pivot var. in terms of free var.

(a)

\( (3 \times 4) \)

\[ \begin{cases} x + y + z + w = 5 \\ x + y - z + w = 7 \\ x + y + 2z - w = 0 \end{cases} \]\[ \left[\begin{array}{cccc|c} 1 & 1 & 1 & 1 & 5 \\ 1 & 1 & -1 & 1 & 7 \\ 1 & 1 & 2 & -1 & 0 \end{array}\right] \longrightarrow \left[\begin{array}{cccc|c} 1 & 1 & 1 & 1 & 5 \\ 0 & 0 & 1 & -2 & -5 \\ 0 & 0 & 0 & 1 & 2 \end{array}\right] \]

\( x, z, w \) are pivot, \( y \) is free

Examples:

Express pivot var. in terms of free var.

(a)

\[ \left[\begin{array}{cccc|c} 1 & 1 & 1 & 1 & 5 \\ 0 & 0 & 1 & -2 & -5 \\ 0 & 0 & 0 & 1 & 2 \end{array}\right] \]

\( w = 2 \)

\( z - 2w = -5 \Rightarrow z = -1 \)

\( y = t \) (free)

\[ \begin{aligned} x &= -y - z - w + 5 \\ &= -t + 1 - 2 + 5 \\ &= 4 - t \end{aligned} \]

Solution:

\[ \begin{pmatrix} x \\ y \\ z \\ w \end{pmatrix} = \begin{pmatrix} 4 - t \\ t \\ -1 \\ 2 \end{pmatrix} = \begin{pmatrix} 4 \\ 0 \\ -1 \\ 2 \end{pmatrix} + t \begin{pmatrix} -1 \\ 1 \\ 0 \\ 0 \end{pmatrix} \]

Examples:

Express pivot var. in terms of free var.

(b)

\[ \begin{cases} x + 2y + 5z + 3w = 0 \\ z - w = 7 \end{cases} \qquad (2 \times 4) \] \[ \left[\begin{array}{cccc|c} 1 & 2 & 5 & 3 & 0 \\ 0 & 0 & 1 & -1 & 7 \end{array}\right] \]

\( x, z \) are pivot, \( y, w \) are free

\( w = t \) (free)

\( z = w + 7 = t + 7 \)

\( y = s \) (free)

\[ \begin{aligned} x &= -2y - 5z - 3w \\ &= -2s - 5(t+7) - 3t \\ &= -35 - 2s - 8t \end{aligned} \]

Solution

\[ \begin{pmatrix} x \\ y \\ z \\ w \end{pmatrix} = \begin{pmatrix} -35 - 2s - 8t \\ s \\ t + 7 \\ t \end{pmatrix} = \begin{pmatrix} -35 \\ 0 \\ 7 \\ 0 \end{pmatrix} + s \begin{pmatrix} -2 \\ 1 \\ 0 \\ 0 \end{pmatrix} + t \begin{pmatrix} -8 \\ 0 \\ 1 \\ 0 \end{pmatrix} \]

Examples:

Express pivot var. in terms of free var.

(c)

\[ x - y + z = 5 \qquad (1 \times 3) \] \[ \left[\begin{array}{ccc|c} 1 & -1 & 1 & 5 \end{array}\right] \]

(\( x \) is pivot, \( y, z \) are free)

\( y = s \) (free)

\( z = t \) (free)

\[ \begin{aligned} x &= y - z + 5 \\ &= s - t + 5 \end{aligned} \]

Solution:

\[ \begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} s - t + 5 \\ s \\ t \end{pmatrix} = \begin{pmatrix} 5 \\ 0 \\ 0 \end{pmatrix} + s \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} + t \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix} \]

Reduced Row Echelon Form (RREF)

(Backward substitution can also be achieved using elementary row ops.)

Staircase matrix showing pivot 1s with entries above pivots highlighted for elimination
Figure 5
A large bracketed matrix drawn as a staircase pattern illustrating reduced row echelon form. The top row begins with a leading 1 followed by asterisks. Below and to the right, a red staircase line steps down through successive leading 1s (pivots), each starting a new row further right. Several columns of asterisk entries lying directly above the pivot 1s are highlighted with orange shading, indicating the entries that must be made zero. Additional pivot 1s appear lower in the staircase, also highlighted at their base. The overall shape shows the characteristic descending step pattern of echelon form, with pivots normalized to 1 and the entries above each pivot column marked for elimination.

Use the pivot 1's to make all the numbers above them to be zero. (start from the last ro

Reduced Row Echelon Form (RREF)

(Backward substitution can also be achieved using elementary row ops.)

Staircase RREF matrix with pivot 1s and columns above pivots highlighted to be zeroed
Figure 6
A large bracketed matrix drawn in a staircase pattern illustrating reduced row echelon form. The first row shows a leading pivot 1 followed by two starred entries and then zeros. A red staircase line descends from left to right marking the pivot positions: a pivot 1 in the first row, another pivot 1 one row down and one column right, another pivot 1 further right, and lower pivot 1s in the last rows toward the right side. Several columns of entries lying above the pivot 1s are shaded in orange highlight, all containing zeros, indicating the entries that are made zero using the pivot 1s. Below the matrix is the note that the pivot 1s are used to make all the numbers above them equal to zero, starting from the last row.

Use the pivot 1's to make all the numbers above them to be zero. (start from the last row)

Three Scenarios of Solving Linear Systems

  1. Unique Solution (only pivot variables, i.e. no free variables, and in REF, no. of non-zero rows in the coefficient matrix is the same as the no. of non-zero rows in the augmented matrix.)

    Augmented staircase matrix with pivot 1s on the diagonal, asterisks above, zeros below
    Figure 7
    A large augmented matrix drawn with square brackets and a vertical bar separating the coefficient part from the augmenting column. The coefficient part shows a staircase of pivot entries equal to 1 running down the main diagonal, with asterisks marking arbitrary nonzero entries above and to the right of each pivot. The lower-left region is labeled O's indicating zero entries. To the right of the vertical bar is a single augmenting column filled with asterisks, one for each row. This depicts the row echelon form of a system with a unique solution, having only pivot variables and no free variables.

  1. Infinitely many solutions ( There are free variables, and in REF, no. of non-zero rows in the coefficient matrix is the same as the no. of non-zero rows in the augmented matrix. )

    Augmented staircase matrix with pivot 1s on the diagonal, asterisks above and to the right, zeros below
    Figure 8
    A large augmented matrix drawn as a staircase pattern. Along the main diagonal are pivot entries equal to 1. Just above and to the right of several pivots are asterisks (highlighted), representing nonzero entries such as single asterisks and pairs of asterisks. Below the diagonal the region is labelled O's, indicating all zeros. A vertical bar separates the coefficient part from the augmenting column on the right, which is a column of asterisks representing the constant terms. This illustrates the row echelon form for a system with infinitely many solutions.

Three Scenarios of Solving Linear Systems

  1. No Solution (inconsistent)

    ( in REF, no. of non-zero rows in the coefficient matrix is less than the no. of non-zero rows in the augmented matrix. )

    Augmented staircase matrix with pivot 1s, asterisk top right, and a final row of zeros equal to a nonzero entry
    Figure 9
    A large augmented matrix shown in row echelon form. The left coefficient block contains pivot entries of 1 arranged along a descending staircase, with the label 0s indicating zeros below the pivots. A red brace on the left labels this coefficient portion as the number of non-zero rows in the coefficient matrix. A vertical bar separates the coefficient columns from the augmenting column on the right, which contains asterisks. The last rows of the coefficient block are shown as 1, 0, 0 while the corresponding augmenting entries are asterisks, so a row of zeros in the coefficient part corresponds to a nonzero augmenting entry. A red brace on the right labels the augmenting portion as the number of non-zero rows in the augmented matrix, illustrating that the coefficient matrix has fewer non-zero rows than the augmented matrix, giving no solution.