Skip to main content

Linear Algebra For Undergraduate Students

Yilan(Peter) Tan

Section 1.3 Gaussian-Jordan Elimination

Subsection 1.3.1 Gaussian-Jordan Elimination in Linear System

Gaussian-Jordan elimination is a systematic method for solving linear systems by using elementary equation operations to transform the system into an echelon form where the solution can be read directly as we saw in [sidebyside]  of Section 1.
🔗
The Gaussian-Jordan elimination involves the following steps:
  1. Step 1: Forward Phase (Creating Echelon Form)
    🔗
    • Start with the leftmost variable that has a non-zero coefficient in some equation
      🔗
      🔗
    • If necessary, interchange equations to move an equation with a non-zero coefficient for this variable to the top position (this variable becomes the pivot variable)
      🔗
      🔗
    • Multiply the pivot equation by a constant to make the coefficient of the pivot variable equal to 1 (this is called rescale the pivot equation)
      🔗
      🔗
    • Add multiples of the pivot equation to the equations below to eliminate this variable from all equations below (make their coefficients zero)
      🔗
      🔗
    • Set aside the pivot equation and all equations above it.
      🔗
      🔗
    • Repeat these sub-steps for the next variable to the right, working with the remaining equations below
      🔗
      🔗
    • Continue until the system is in echelon form: each pivot variable appears with coefficient 1, and all coefficients below each pivot are zero
      🔗
      🔗
    🔗
  2. Step 2: Backward Phase (Creating Reduced Echelon Form)
    🔗
    • Starting from the rightmost pivot variable, use replacement to eliminate this variable from all equations above (make their coefficients zero)
      🔗
      🔗
    • Move to the next pivot variable to the left and repeat
      🔗
      🔗
    • Continue until the system is in reduced echelon form: each pivot variable has coefficient 1 and is the only variable with a non-zero coefficient in its equation
      🔗
      🔗
    🔗
  3. Step 3: Read the Solution
    🔗
    • Variables that appear as pivots are leading variables
      🔗
      🔗
    • Variables that do not appear as pivots are free variables
      🔗
      🔗
    • Express each leading variable in terms of the free variables and constants
      🔗
      🔗
    • Write the general solution in vector form if needed
      🔗
      🔗
    🔗
🔗
Key Points to Remember:
  • Always work systematically from left to right, top to bottom
    🔗
    🔗
  • Each pivot variable should have coefficient 1
    🔗
    🔗
  • Below each pivot (forward phase) and above each pivot (backward phase), the coefficients should be zeros
    🔗
    🔗
  • The three elementary equation operations preserve the solution set
    🔗
    🔗
🔗

Example 1.3.1. Solving a System Using Gaussian-Jordan Elimination.

Let’s solve the following system using Gaussian-Jordan elimination:
🔗
\begin{equation*} \begin{alignedat}{5} && x_2 &- 3x_3 &- 4x_4 &= 15\\ x_1 & & &+ 3x_3 &+ 2x_4 &= -3\\ 3x_1 & & &+ 5x_3 &+ 6x_4 &= -17\\ && -x_2 &+ 3x_3 &+ 10x_4 &= -39 \end{alignedat} \end{equation*}
Step 1: Interchange equations to get \(x_1\) in the leading position:
🔗
\begin{equation*} \begin{alignedat}{5} x_1 & & &+ 3x_3 &+ 2x_4 &= -3\\ && x_2 &- 3x_3 &- 4x_4 &= 15\\ 3x_1 & & &+ 5x_3 &+ 6x_4 &= -17\\ && -x_2 &+ 3x_3 &+ 10x_4 &= -39 \end{alignedat} \end{equation*}
Step 2: Eliminate \(x_1\) from equation 3 by adding \(-3 \times \text{equation 1}\) to equation 3:
🔗
\begin{equation*} \begin{alignedat}{5} x_1 & & &+ 3x_3 &+ 2x_4 &= -3\\ && x_2 &- 3x_3 &- 4x_4 &= 15\\ && &- 4x_3 & &= -8\\ && -x_2 &+ 3x_3 &+ 10x_4 &= -39 \end{alignedat} \end{equation*}
Step 3: Eliminate \(x_2\) from equation 4 by adding equation 2 to equation 4:
🔗
\begin{equation*} \begin{alignedat}{5} x_1 & & &+ 3x_3 &+ 2x_4 &= -3\\ && x_2 &- 3x_3 &- 4x_4 &= 15\\ && &- 4x_3 & &= -8\\ && & &+ 6x_4 &= -24 \end{alignedat} \end{equation*}
Step 4: Normalize equations 3 and 4 by multiplying by appropriate constants:
🔗
\begin{equation*} \begin{alignedat}{5} x_1 & & &+ 3x_3 &+ 2x_4 &= -3\\ && x_2 &- 3x_3 &- 4x_4 &= 15\\ && &+ x_3 & &= 2\\ && & &+ x_4 &= -4 \end{alignedat} \end{equation*}
Step 5: Eliminate \(x_4\) from equations 1 and 2:
🔗
\begin{equation*} \begin{alignedat}{5} x_1 & & &+ 3x_3 & &= 5\\ && x_2 &- 3x_3 & &= -1\\ && &+ x_3 & &= 2\\ && & &+ x_4 &= -4 \end{alignedat} \end{equation*}
Step 6: Eliminate \(x_3\) from equations 1 and 2:
🔗
\begin{equation*} \begin{alignedat}{3} && x_1 &= -1\\ && x_2 &= 5\\ && x_3 &= 2\\ && x_4 &= -4 \end{alignedat} \end{equation*}
Therefore, the solution is \(x_1 = -1\text{,}\) \(x_2 = 5\text{,}\) \(x_3 = 2\text{,}\) and \(x_4 = -4\text{.}\)
🔗
🔗
The Gaussian-Jordan elimination process systematically transforms any linear system into reduced row echelon form, where:
  1. Each leading variable has coefficient 1
    🔗
    🔗
  2. Each leading variable is the only non-zero entry in its column
    🔗
    🔗
  3. Leading variables appear in order from left to right
    🔗
    🔗
  4. Any zero rows appear at the bottom
    🔗
    🔗
🔗
This method is particularly powerful because it works for any linear system and clearly reveals when a system has no solution, exactly one solution, or infinitely many solutions.
🔗

Exercises Exercises

1.
Use Gaussian-Jordan elimination to solve the following system:
\begin{equation*} \begin{aligned} 2x + 3y - z &= 7\\ x - y + 2z &= 4\\ 3x + y + z &= 8 \end{aligned} \end{equation*}
🔗
Solution.
The reduced echelon form of the linear system is
\begin{equation*} \begin{aligned} x &= 2\\ y &= 1\\ z &= 3 \end{aligned} \end{equation*}
Thus, the solution is \(x = 2\text{,}\) \(y = 1\text{,}\) and \(z = 3\text{.}\)
🔗
🔗
🔗
2.
Use Gaussian-Jordan elimination to solve the following system:
\begin{equation*} \begin{alignedat}{5} & 4x_2 &+x_3 &+x_4 &= 5\\ 2x_1 &+3x_2 & &+ 2x_4 &= 0\\ 3x_1 & +4x_2& + x_3 &+ 2x_4 &= 4\\ x_1&+x_2 &- x_3 &+ x_4 &= 0 \end{alignedat} \end{equation*}
🔗
🔗
🔗
🔗

Subsection 1.3.2 A More Compact Representation: Matrices

While writing out linear systems equation by equation is straightforward, there is a more compact and powerful way to represent them: using matrices.
🔗

Definition 1.3.2. Matrix.

An \(m \times n\) matrix is a rectangular array of numbers arranged in \(m\) rows and \(n\) columns:
\begin{equation*} A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}. \end{equation*}
The number \(a_{ij}\) is called the entry (or element) in row \(i\) and column \(j\) of \(A\text{.}\) We write \(A = [a_{ij}]\) as shorthand. The size of the matrix is described as \(m \times n\) (read “\(m\) by \(n\)”), where \(m\) is the number of rows and \(n\) is the number of columns.
🔗
🔗
This matrix representation not only saves space but also enables us to use systematic computational techniques to solve systems efficiently.
🔗
Consider our linear system:
\begin{align*} 3x_2 - 6x_3 + 6x_4 + 4x_5 &= -5\\ 3x_1 - 7x_2 + 8x_3 - 5x_4 + 8x_5 &= 9\\ 3x_1 - 9x_2 + 12x_3 - 9x_4 + 6x_5 &= 15 \end{align*}
🔗
We can organize the coefficients of the variables into a rectangular array called the coefficient matrix:
\begin{equation*} A = \begin{bmatrix} 0 & 3 & -6 & 6 & 4 \\ 3 & -7 & 8 & -5 & 8 \\ 3 & -9 & 12 & -9 & 6 \end{bmatrix}. \end{equation*}
Each row of this matrix corresponds to one equation, and each column corresponds to one variable. The entry in row \(i\) and column \(j\) is the coefficient of \(x_j\) in equation \(i\text{.}\) Note that the entry in row 1 and column 1 is zero because \(x_1\) does not appear in the first equation.
🔗
To capture all the information from our linear system, including the constants on the right-hand side, we form the augmented matrix by appending the constants as an additional column:
\begin{equation*} [A\,|\,\mathbf{b}] = \begin{bmatrix} 0 & 3 & -6 & 6 & 4 & | & -5\\ 3 & -7 & 8 & -5 & 8 & | & 9\\ 3 & -9 & 12 & -9 & 6 & | & 15 \end{bmatrix}. \end{equation*}
The vertical line is a visual separator to distinguish the coefficient matrix. Sometimes, we simply write the augmented matrix without the line for brevity if we know it is an augmented matrix.
🔗
The augmented matrix contains exactly the same information as the original system of equations, but in a more organized form. We can recover the original equations by reading each row: the entries before the vertical line give the coefficients, and the entry after the line gives the constant term.
🔗

Matrix Representation.

  • The coefficient matrix \(A\) contains only the coefficients of the variables.
    🔗
  • The augmented matrix \([A\,|\,\mathbf{b}]\) includes both coefficients and constants.
    🔗
  • Working with the augmented matrix is completely equivalent to working with the system of equations.
    🔗
🔗
🔗
Why use matrix notation? Working with the augmented matrix is much more convenient than writing out full equations. Instead of repeatedly writing variable names and equals signs, we simply manipulate a rectangular array of numbers. This compact representation:
  • Saves space and reduces clutter
    🔗
  • Makes patterns more visible
    🔗
  • Allows for systematic algorithms (like Gaussian elimination)
    🔗
  • Enables efficient computer implementation
    🔗
🔗
Let’s see this advantage by revisiting Example 1.3.1 using matrix notation instead of writing out full equations at each step.
🔗

Example 1.3.3. Solving Using Matrix Operations.

Solve the system from Example Example 1.3.1 using augmented matrix notation:
\begin{align*} x_2 - 3x_3 - 4x_4 &= 15\\ x_1 + 3x_3 + 2x_4 &= -3\\ 3x_1 + 5x_3 + 6x_4 &= -17\\ -x_2 + 3x_3 + 10x_4 &= -39 \end{align*}
🔗
Solution.
We form the augmented matrix and perform row operations:
\begin{equation*} \begin{bmatrix} 0 & 1 & -3 & -4 & | & 15\\ 1 & 0 & 3 & 2 & | & -3\\ 3 & 0 & 5 & 6 & | & -17\\ 0 & -1 & 3 & 10 & | & -39 \end{bmatrix}. \end{equation*}
🔗
Step 1: Swap rows 1 and 2: \(R_1\leftrightarrow R_2\text{:}\)
\begin{equation*} \begin{bmatrix} 1 & 0 & 3 & 2 & | & -3\\ 0 & 1 & -3 & -4 & | & 15\\ 3 & 0 & 5 & 6 & | & -17\\ 0 & -1 & 3 & 10 & | & -39 \end{bmatrix}. \end{equation*}
🔗
Step 2: Add \(-4\)times Row 1 to Row 3: \(- 3R_1 + R_3 \text{:}\)
\begin{equation*} \begin{bmatrix} 1 & 0 & 3 & 2 & | & -3\\ 0 & 1 & -3 & -4 & | & 15\\ 0 & 0 & -4 & 0 & | & -8\\ 0 & -1 & 3 & 10 & | & -39 \end{bmatrix}. \end{equation*}
🔗
Step 3:Add \(1\)times Row 2 to Row 4: \(R_2+R_4\text{:}\)
\begin{equation*} \begin{bmatrix} 1 & 0 & 3 & 2 & | & -3\\ 0 & 1 & -3 & -4 & | & 15\\ 0 & 0 & -4 & 0 & | & -8\\ 0 & 0 & 0 & 6 & | & -24 \end{bmatrix}. \end{equation*}
🔗
Step 4: Rescale Row 3 by \(-\frac{1}{4}\) and Row 4 by \(\frac{1}{6}\text{,}\) respectively(分别的): \(R_3 \leftarrow -\frac{1}{4}R_3\) and \(R_4 \leftarrow \frac{1}{6}R_4\text{:}\)
\begin{equation*} \begin{bmatrix} 1 & 0 & 3 & 2 & | & -3\\ 0 & 1 & -3 & -4 & | & 15\\ 0 & 0 & 1 & 0 & | & 2\\ 0 & 0 & 0 & 1 & | & -4 \end{bmatrix}. \end{equation*}
🔗
Step 5: Add \(-2\)times Row 4 to Row 1 and \(4\)times Row 4 to Row 2, respectively: \(-2R_4+R_1 \) and \(4R_4 + R_2 \text{:}\)
\begin{equation*} \begin{bmatrix} 1 & 0 & 3 & 0 & | & 5\\ 0 & 1 & -3 & 0 & | & -1\\ 0 & 0 & 1 & 0 & | & 2\\ 0 & 0 & 0 & 1 & | & -4 \end{bmatrix}. \end{equation*}
🔗
Step 6: Add \(-3\)times Row 3 to Row 1 and \(3\)times Row 3 to Row 2, respectively: \(-3R_3 + R_1 \) and \(3R_3 + R_2 \text{:}\)
\begin{equation*} \begin{bmatrix} 1 & 0 & 0 & 0 & | & -1\\ 0 & 1 & 0 & 0 & | & 5\\ 0 & 0 & 1 & 0 & | & 2\\ 0 & 0 & 0 & 1 & | & -4 \end{bmatrix}. \end{equation*}
🔗
From this RREF, we can immediately read: \(x_1 = -1, x_2 = 5, x_3 = 2, x_4 = -4\text{.}\)
🔗
🔗
🔗
Notice how much cleaner and more systematic the solution process becomes using matrix notation. Each step is concise, the pattern is clear, and we avoid the tedium of writing out variable names repeatedly.
🔗
The advantages of using matrices become even more pronounced when dealing with larger systems, where writing out each equation would be cumbersome. Matrix notation allows us to focus on the structure of the system and the operations needed to solve it, making it easier to implement algorithms both by hand and in computer programs.
🔗
We can summarize the steps of the Gaussian-Jordan elimination on the augmented matrix as follows:
\begin{equation*} \begin{bmatrix} 0 & 1 & -3 & -4 & | & 15\\ 1 & 0 & 3 & 2 & | & -3\\ 3 & 0 & 5 & 6 & | & -17\\ 0 & -1 & 3 & 10 & | & -39 \end{bmatrix}\stackrel{R_1\leftrightarrow R_2}{\longrightarrow} \begin{bmatrix} 1 & 0 & 3 & 2 & | & -3\\ 0 & 1 & -3 & -4 & | & 15\\ 3 & 0 & 5 & 6 & | & -17\\ 0 & -1 & 3 & 10 & | & -39 \end{bmatrix}\stackrel{\ldots}{\longrightarrow} \end{equation*}
🔗

Exercises Exercises

1.
Use matrix notation to solve the following system:
\begin{align*} 2x + 3y - z &= 7\\ x - y + 2z &= 4\\ 3x + y + z &= 8 \end{align*}
🔗
🔗
2.
Use matrix notation to solve the following system:
\begin{align*} 3x_2 - 6x_3 + 6x_4 + 4x_5 &= -5\\ 3x_1 - 9x_2 + 12x_3 - 9x_4 + 6x_5 &= 15\\ 3x_1 - 7x_2 + 8x_3 - 5x_4 + 8x_5 &= 9 \end{align*}
🔗
🔗
🔗
🔗
🔗
PrevTopNext