Motivation: How to Solve a Linear System

Section 1.1 Motivation: How to Solve a Linear System

Which linear system is easier to solve?

🔗

\begin{equation*} \begin{aligned} 3y + 4z &= 11\\ 3x - 7y + 4z &= 4\\ 3x - 9y + 6z &= 6 \end{aligned} \end{equation*}

Figure 1.1.1. Linear System I

🔗

\begin{equation*} \begin{aligned} 3x - 7y + 4z &= 4\\ 3y + 4z &= 11\\ z &= 2 \end{aligned} \end{equation*}

Figure 1.1.2. Linear System II

🔗

Clearly, Linear System II is easier to solve because the last equation directly gives us the value of \(z\text{.}\) We can then substitute this value back into the second equation to find \(y\text{,}\) and finally use both \(y\) and \(z\) in the first equation to solve for \(x\text{.}\) This step-by-step substitution process is straightforward and efficient.

🔗

In contrast, Linear System I does not provide any immediate values for the variables. We would need to use methods such as substitution or elimination, which can be more complex and time-consuming. Therefore, having a system in a form where variables can be easily isolated, as seen in Linear System II, significantly simplifies the solving process.

🔗

In this chapter, we will explore how to systematically transform any linear system into an equivalent form that is as straightforward to solve as Linear System II. This transformation is achieved through equation operations, leading us to the concept of reduced row echelon form (RREF), which allows us to read off solutions directly.

🔗

Subsection 1.1.1 Three equation Operations

There are three elementary equation operations that can be performed on the linear system without changing the solution of the corresponding linear system:

Interchange two equations. For example, swapping Row 1 and Row 2:

\begin{equation*} \begin{aligned} 3y + 4z &= 11\\ 3x - 7y + 4z &= 4\\ 3x - 9y + 6z &= 6 \end{aligned}\stackrel{R_1 \leftrightarrow R_2}{\longrightarrow} \begin{aligned} 3x - 7y + 4z &= 4\\ 3y + 4z &= 11\\ 3x - 9y + 6z &= 6 \end{aligned} \end{equation*}

🔗

🔗
Scale an equation by a non-zero constant. For example, multiplying Row 2 by \(\frac{1}{3}\text{:}\)

\begin{equation*} \begin{aligned} 3x - 7y + 4z &= 4\\ 3y + 4z &= 11\\ 3x - 9y + 6z &= 6 \end{aligned}\stackrel{\frac{1}{3}R_1}{\longrightarrow}\quad \begin{aligned} x - \frac{7}{3}y + \frac{4}{3}z &= \frac{4}{3}\\ 3y + 4z &= 11\\ 3x - 9y + 6z &= 6 \end{aligned} \end{equation*}

🔗

🔗
Replace an \(k\) times \(i\)-th equation to the \(j\)-th equation. For example, replacing Row 3 with \(3\) times row 1 to Row 3:

\begin{equation*} \begin{aligned} x - \frac{7}{3}y + \frac{4}{3}z &= \frac{4}{3}\\ 3y + 4z &= 11\\ 3x - 9y + 6z &= 6 \end{aligned}\stackrel{-R_1 + R_3}{\longrightarrow} \begin{aligned} x - \frac{7}{3}y + \frac{4}{3}z &= \frac{4}{3}\\ 3y + 4z &= 11\\ -2y + 2z &= 2 \end{aligned} \end{equation*}

🔗

🔗

🔗

Checkpoint 1.1.3.

Complete the blank:

🔗

\begin{equation*} \begin{aligned} 3y + 4z &= 11\\ 3x - 7y + 4z &= 3\\ -2y + 2z &= 2 \end{aligned}\longrightarrow \begin{aligned} x - \frac{7}{3}y + \frac{4}{3}z &= \underline{\qquad}\\ 3y + 4z &= 11\\ z &= \underline{\qquad} \end{aligned} \end{equation*}

🔗

Subsection 1.1.2 Linear System and Equivalent systems

Definition 1.1.4.

A linear system (or system of linear equations) is a collection of linear equations involving the same set of variables.

\begin{equation*} \begin{aligned} a_{11}x_1 + a_{12}x_2 +&\ldots+ a_{1n}x_n = b_1\\ a_{21}x_1 + a_{22}x_2 +&\ldots+ a_{2n}x_n = b_2\\ &\quad \vdots & \\ a_{m1}x_1 + a_{m2}x_2 +&\ldots+ a_{mn}x_n = b_m\\ \end{aligned} \end{equation*}

🔗

A solution to the linear system is an ordered n-tuple \((x_1, x_2, \dots, x_n)\) that satisfies all equations in the system simultaneously. A solution set of the linear system is the collection of all possible solutions. A Linear system is called consistent if it has at least one solution; otherwise, it is called inconsistent.

🔗

For example, consider the following system of three equations in three variables:

\begin{equation*} \begin{aligned} 2x + 3y - z &= 7\\ x - y + 2z &= 4\\ 3x + y + z &= 8 \end{aligned} \end{equation*}

🔗

Study Goal of the chapter.

Our goal of this chapter is to find the solution set of a linear system.

🔗

Two linear systems are called equivalent if they have exactly the same set of solutions. The key insight in solving linear systems is that we can transform a given system into an equivalent system that is easier to solve, without changing the solution set.

🔗

The transformation from one system to an equivalent system is accomplished through elementary equation operations:

Multiply an equation by a non-zero constant.
🔗

🔗
Add a multiple of one equation to another equation.
🔗

🔗
Interchange two equations.
🔗

🔗

🔗

These operations preserve the solution set, meaning that if we apply any combination of these operations to a linear system, the resulting system will be equivalent to the original system, that is, they have the same solution set.

🔗

Example 1.1.5. Elementary Equation Operations and Equivalent Systems.

Let’s demonstrate each elementary equation operation using the system:

\begin{equation*} \begin{aligned} x + 2y &= 5\\ 2x + 3y &= 7 \end{aligned} \end{equation*}

🔗

Operation 1: Multiply an equation by a non-zero constant

🔗

We can multiply the first equation by 2 to get an equivalent system:

\begin{equation*} \begin{aligned} 2x + 4y &= 10\\ 2x + 3y &= 7 \end{aligned} \end{equation*}

🔗

Notice that we can reverse this operation by dividing the first equation by 2 to return to the original system. The transformation works both ways.

🔗

Operation 2: Add a multiple of one equation to another

🔗

Starting from our original system, we subtract twice the first equation from the second equation:

\begin{equation*} \begin{aligned} x + 2y &= 5\\ -y &= -3 \end{aligned} \end{equation*}

🔗

We can reverse this by adding twice the first equation to the second equation. Again, the transformation is reversible.

🔗

Operation 3: Interchange two equations

🔗

We can swap the order of the equations:

\begin{equation*} \begin{aligned} 2x + 3y &= 7\\ x + 2y &= 5 \end{aligned} \end{equation*}

🔗

Obviously, we can interchange them back to the original order. This operation is clearly reversible.

🔗

The key insight is that every elementary equation operation can be undone. This guarantees that when we transform one system into another using these operations, we can always transform back, ensuring the systems are truly equivalent with the same solution set.

🔗

Subsection 1.1.3 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:

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
  🔗
  
  🔗
🔗
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
  🔗
  
  🔗
🔗
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.1.6. 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:

Each leading variable has coefficient 1
🔗

🔗
Each leading variable is the only non-zero entry in its column
🔗

🔗
Leading variables appear in order from left to right
🔗

🔗
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.1.4 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. 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.1.6 using matrix notation instead of writing out full equations at each step.

🔗

Example 1.1.7. Solving Using Matrix Operations.

Solve the system from Example Example 1.1.6 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*}

🔗

Prev Top Next