\( \definecolor{colordef}{RGB}{249,49,84} \definecolor{colorprop}{RGB}{18,102,241} \)

Systems of Linear Equations

We have previously seen methods for solving systems of two linear equations in two unknowns. We now look at more general systems and how they can be represented using augmented matrices. This is a first step into the branch of mathematics called linear algebra, which underpins much of modern technology (computer science, engineering, physics, economics, etc.).

Systems of Linear Equations

Definition Linear Equation
A linear equation in the variables \(x_1, x_2, \dots, x_n\) is an equation that can be written in the form$$ a_1x_1 + a_2x_2 + \dots + a_nx_n = b $$where \(a_1, a_2, \dots, a_n\) and \(b\) are constants. A solution to the equation is a set of values for the variables that makes the equation true.
Definition System of Linear Equations
A system of \(m\) linear equations in \(n\) unknowns, \(x_1,x_2,\dots,x_n\), can be written in the form$$\left\{\begin{array}{rcrcrcrcl}a_{11}x_1 & + & a_{12}x_2 &+& \dots &+ & a_{1n}x_n &=& b_1 \\ a_{21}x_1 & + & a_{22}x_2 &+& \dots &+ & a_{2n}x_n &=& b_2 \\ \vdots & & \vdots & & \dots & & \vdots & & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 &+& \dots &+ & a_{mn}x_n &=& b_m \\ \end{array}\right.$$A solution to the system is a set of values for the variables that satisfies every equation in the system.

Representations of Solution Sets

The set of all solutions to a system of linear equations can be represented in several ways. The most common forms are:
  • the Cartesian (or explicit) equation,
  • the parametric form,
  • the vector form.
Definition Consistent/Inconsistent System
A system of linear equations is:
  • consistent if it has at least one solution,
  • inconsistent if it has no solution.
Example
Show that the following system of equations is inconsistent:$$\left\{\begin{array}{rcrcr}x & + & y & = & 3 \\ 2x & + & 2y & = & 8\end{array}\right.$$

If we take the second equation and divide it by 2, we get$$ \frac{2x+2y}{2} = \frac{8}{2} \implies x+y = 4. $$The system is therefore equivalent to$$\left\{\begin{array}{rcrcr}x & + & y & = & 3 \\ x & + & y & = & 4\end{array}\right.$$This is a contradiction, since \(x+y\) cannot be equal to both 3 and 4. Therefore, the system has no solution and is inconsistent.

Proposition Geometric Interpretation of Solutions in 2D
In a 2-dimensional space with variables \((x, y)\):
  • The solution set of a single linear equation is a line. The solutions can be described using one parameter.
  • The solution set of a system of two non-parallel linear equations is a point. The solution is unique.
Example
Consider the linear equation \(2x+y=1\). Geometrically, its solution set is a line in the 2D plane.
  1. Parametric Form
    We introduce a parameter \(t\) and let \(x=t\). Substituting into the equation,$$ 2t+y=1 \implies y=1-2t. $$The general solution in parametric form is$$ \boldsymbol{(x, y) = (t, 1-2t)}, \quad t \in \mathbb{R}. $$
  2. Vector Form
    We write the solution as a vector equation:$$\begin{aligned}\begin{pmatrix} x \\ y \end{pmatrix}&= \begin{pmatrix} t \\ 1-2t \end{pmatrix} \\ &= \begin{pmatrix} 0 \\ 1 \end{pmatrix} + \begin{pmatrix} t \\ -2t \end{pmatrix} \\ &= \underbrace{\begin{pmatrix} 0 \\ 1 \end{pmatrix}}_{\text{position vector}} + t \underbrace{\begin{pmatrix} 1 \\ -2 \end{pmatrix}}_{\text{direction vector}}.\end{aligned}$$Any point \(\begin{pmatrix} x \\ y \end{pmatrix}\) on the line is obtained by starting from the fixed point \((0,1)\) and moving \(t\) times along the direction vector \(\begin{pmatrix}1\\-2\end{pmatrix}\).
Proposition Geometric Interpretation of Solutions in 3D
In a 3-dimensional space with variables \((x, y, z)\):
  • The solution set of a single linear equation is a plane. The solutions can be described using two parameters.
  • The solution set of a system of two non-parallel, non-coincident linear equations is a line: the intersection of the two planes. The solutions can be described using one parameter.
Example
Consider the equation \(x + 2y + 3z = 6\). Geometrically, this represents a plane in 3D space.
  1. Parametric Form
    We need two parameters. Let \(y=s\) and \(z=t\). Then$$ x + 2s + 3t = 6 \implies x = 6 - 2s - 3t. $$The general solution in parametric form is$$ \boldsymbol{(x, y, z) = (6 - 2s - 3t, s, t)}, \quad s,t \in \mathbb{R}. $$
  2. Vector Form
    We write the solution as a vector equation:$$\begin{aligned}\begin{pmatrix} x \\ y \\ z \end{pmatrix}&= \begin{pmatrix} 6 - 2s - 3t \\ s \\ t \end{pmatrix} \\ &= \begin{pmatrix} 6 \\ 0 \\ 0 \end{pmatrix} + s \begin{pmatrix} -2 \\ 1 \\ 0 \end{pmatrix} + t \begin{pmatrix} -3 \\ 0 \\ 1 \end{pmatrix} \\ &= \underbrace{\begin{pmatrix} 6 \\ 0 \\ 0 \end{pmatrix}}_{\text{position vector}} + s \underbrace{\begin{pmatrix} -2 \\ 1 \\ 0 \end{pmatrix}}_{\text{direction vector 1}} + t \underbrace{\begin{pmatrix} -3 \\ 0 \\ 1 \end{pmatrix}}_{\text{direction vector 2}}.\end{aligned}$$Any point on the plane is obtained by starting at \((6,0,0)\) and moving along a combination of the two direction vectors.
Example
Consider the system$$\left\{\begin{array}{rcrcrcl}x &+& y &+& z &=& 3 \\ x &-& y &+& 2z &=& 2\end{array}\right.$$Geometrically, these are two planes in 3D. If they are not parallel and not the same plane, their solution set is the line where they intersect.
  1. Parametric Form
    Add the two equations to eliminate \(y\):$$ (x+y+z) + (x-y+2z) = 3+2 \implies 2x + 3z = 5. $$Introduce a parameter \(t\) by letting \(z=t\):$$ 2x + 3t = 5 \implies x = \frac{5}{2} - \frac{3}{2}t. $$Substitute \(x\) and \(z\) into the first equation to find \(y\):$$ \left(\frac{5}{2} - \frac{3}{2}t\right) + y + t = 3 \implies y = \frac{1}{2} + \frac{1}{2}t. $$The parametric solution is$$ \boldsymbol{(x, y, z) = \left(\frac{5}{2} - \frac{3}{2}t,\ \frac{1}{2} + \frac{1}{2}t,\ t\right)}, \quad t \in \mathbb{R}. $$
  2. Vector Form
    We write the solution as a vector equation:$$\begin{aligned}\begin{pmatrix} x \\ y \\ z \end{pmatrix}&= \begin{pmatrix} 5/2 - 3/2 t \\ 1/2 + 1/2 t \\ t \end{pmatrix} \\ &= \underbrace{\begin{pmatrix} 5/2 \\ 1/2 \\ 0 \end{pmatrix}}_{\text{position vector}} + t \underbrace{\begin{pmatrix} -3/2 \\ 1/2 \\ 1 \end{pmatrix}}_{\text{direction vector}}.\end{aligned}$$This is the vector equation of the line of intersection.

Augmented Matrices

An augmented matrix is a compact way to record a linear system so that we can perform fast, systematic calculations.
Definition Augmented Matrix
A system of \(m\) linear equations in \(n\) unknowns can be represented by a rectangular array of numbers called an augmented matrix. For the general system$$\left\{\begin{array}{rcrcrcrcl}a_{11}x_1 & + & a_{12}x_2 &+& \dots &+ & a_{1n}x_n &=& b_1 \\ a_{21}x_1 & + & a_{22}x_2 &+& \dots &+ & a_{2n}x_n &=& b_2 \\ \vdots & & \vdots & & \dots & & \vdots & & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 &+& \dots &+ & a_{mn}x_n &=& b_m \\ \end{array}\right.$$the augmented matrix is$$\left[ \begin{array}{cccc|c}a_{11} & a_{12} & \dots & a_{1n} & b_1 \\ a_{21} & a_{22} & \dots & a_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} & b_m\end{array} \right].$$
Example
Write down the augmented matrix for the following system of linear equations:$$\left\{\begin{array}{rcrcrcr}2x &-& y &+& z &=& -1 \\ x & & &+& 3z &=& 4 \\ -x &+& 2y &-& z &=& 0\end{array}\right.$$

The system has three variables (\(x, y, z\)) and three equations. Each column corresponds to the coefficients of one variable. If a variable is missing from an equation, its coefficient is 0.
The augmented matrix is$$\left[ \begin{array}{ccc|c}2 & -1 & 1 & -1 \\ 1 & 0 & 3 & 4 \\ -1 & 2 & -1 & 0\end{array} \right].$$

Elementary Row Operations

From our work with simultaneous equations, we know we can perform certain operations without changing the solution set of the system:
  • Interchange the equations
    For example, \(\left\{ \begin{array}{rcrcrc} 2x&+& y &=& -1 \\ x &-& 3y &=& 2 \\ \end{array}\right.\) has the same solutions as \(\left\{ \begin{array}{rcrcrc} x &-& 3y &=& 2 \\ 2x&+& y &=& -1 \qquad \scriptstyle (R_1 \leftrightarrow R_2) \end{array}\right.\)
  • Replace an equation by a non-zero multiple of itself
    For example, \(\left\{ \begin{array}{rcrcrc} x &-& 3y &=& 2 \\ 2x&+& y &=& -1 \end{array}\right.\) has the same solutions as \(\left\{ \begin{array}{rcrcrc} 2x &-& 6y &=& 4 \qquad \scriptstyle (R_1 \leftarrow 2R_1) \\ 2x&+& y &=& -1 \end{array}\right.\)
  • Replace an equation by the sum of itself and a multiple of another equation
    For example, \(\left\{ \begin{array}{rcrcrc} x &-& 3y &=& 2 \\ 2x&+& y &=& -1 \end{array}\right.\) has the same solutions as \(\left\{ \begin{array}{rcrcrc} x &-& 3y &=& 2 \\ & & 7y &=& -5 \qquad \scriptstyle (R_2 \leftarrow R_2 - 2R_1) \end{array}\right.\), as shown by $$\begin{array}{rcrl} 2x + y &=& -1 &\scriptstyle R_2 \\ -2x + 6y &=& -4& \scriptstyle -2 R_1 \\ \hline 7y &=& -5 & \scriptstyle R_2-2R_1 \end{array}$$
These are called elementary row operations.
Proposition Elementary Row Operations
To solve a system using its augmented matrix, we use elementary row operations to transform the matrix into a simpler, equivalent form. These operations do not change the solution set of the system.
  1. Interchange two rows (\(R_i \leftrightarrow R_j\)).
  2. Multiply a row by a non-zero constant (\(R_i \leftarrow kR_i\)).
  3. Add a multiple of one row to another row (\( R_i \leftarrow R_i + kR_j\)).

Gaussian Elimination

Gaussian elimination is the process of using elementary row operations to systematically solve a system of linear equations. The aim is to transform the augmented matrix into row-echelon form.
Method Solving a System with Gaussian Elimination
  1. Augmented Matrix: Write the system of linear equations as an augmented matrix.
  2. Row-Echelon Form: Use row operations to create a “triangle” of zeros in the bottom-left corner of the matrix (zeros below each pivot).
  3. Reduced Row-Echelon Form (optional): Continue using row operations to create zeros above the pivots and make each pivot equal to 1. The coefficient matrix becomes the identity matrix.
  4. Read the solution: The final matrix gives the solution directly:
Example
Use Gaussian elimination to solve:$$\left\{\begin{array}{rcrcr}x & + & y & = & -1 \\ 2x & + & 4y & = & 6\end{array}\right.$$

$$\begin{aligned} & \left\{\begin{array}{rcrcr}x & + & y & = & -1 \\ 2x & + & 4y & = & 6\end{array}\right.\\ \sim\;&\left[ \begin{array}{cc|c}1 & 1 & -1 \\ 2 & 4 & 6\end{array} \right]\quad (\text{write the augmented matrix})\\ \sim\;&\left[ \begin{array}{cc|c}1 & 1 & -1 \\ 0 & 2 & 8\end{array} \right]\begin{array}{l} \\ \scriptstyle R_2 \leftarrow R_2 - 2R_1\end{array}\quad (\text{create a zero below the pivot})\\ \sim\;&\left[ \begin{array}{cc|c}1 & 1 & -1 \\ 0 & 1 & 4\end{array} \right]\begin{array}{l} \\ \scriptstyle R_2 \leftarrow \frac{1}{2}R_2\end{array}\quad (\text{make the pivot in Row 2 equal to 1})\\ \sim\;&\left[ \begin{array}{cc|c}1 & 0 & -5 \\ 0 & 1 & 4\end{array} \right]\begin{array}{l}\scriptstyle R_1 \leftarrow R_1-R_2 \\ \;\end{array}\quad (\text{create a zero above the pivot in Row 2}) \\ \sim\;&\left\{\begin{array}{rcrcr}x & & & = & -5 \\ & & y & = & 4\end{array}\right.\quad (\text{read off the solution})\end{aligned}$$

Analyzing Solutions from Row-Echelon Form

After reducing an augmented matrix to row-echelon form, we can determine the type of solution set without necessarily going all the way to reduced row-echelon form. The key is to look at the pivots and the last column.
In a row-echelon matrix:
  • A pivot is the first non-zero entry in a row.
  • A pivot variable is a variable whose column contains a pivot.
  • A free variable is a variable whose column does not contain a pivot.
From this, we can decide whether the system has no solution, a unique solution, or infinitely many solutions.
Proposition Types of Solutions from Row-Echelon Form
When a system is in row-echelon form, there are three possibilities for its solution set.
  1. No Solution (Inconsistent System)
    This occurs if there is a row of the form $$\begin{bmatrix} 0 & 0 & \dots & 0 & | & b \end{bmatrix}, \quad b \neq 0.$$ This row represents the equation \(0=b\), which is a contradiction.
  2. Unique Solution
    This occurs if the system is consistent (there is no contradiction row) and there are no free variables. Every variable is a pivot variable.
  3. Infinitely Many Solutions
    This occurs if the system is consistent (no contradiction row) and there is at least one free variable.
Example
  1. No Solution (Inconsistent System)
    $$ \left[ \begin{array}{ccc|c} 1 & 2 & -1 & 4 \\ 0 & 1 & 3 & 5 \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{2} \end{array} \right] \quad\Longrightarrow\quad \text{no solution, since this row means } 0=2. $$
  2. Unique Solution
    $$ \left[ \begin{array}{ccc|c} \mathbf{1} & 2 & -1 & 4 \\ 0 & \mathbf{1} & 3 & 5 \\ 0 & 0 & \mathbf{4} & 8 \end{array} \right] \quad\Longrightarrow\quad \text{unique solution.} $$ From the last row, \(4z=8 \implies z=2\). Then we can use back-substitution to find \(y\) and \(x\). Geometrically, the three planes intersect at a single point.
  3. Infinitely Many Solutions
    $$ \left[ \begin{array}{ccc|c} \mathbf{1} & 2 & -1 & 4 \\ 0 & \mathbf{1} & 3 & 5 \\ 0 & 0 & 0 & 0 \end{array} \right] \quad\Longrightarrow\quad \text{infinitely many solutions.} $$ The last row corresponds to \(0=0\), so the system is consistent. The variables \(x\) and \(y\) are pivot variables, but \(z\) is a free variable. We can set \(z=t\) with \(t \in \mathbb{R}\), then use back-substitution to express \(x\) and \(y\) in terms of \(t\). Geometrically, the planes intersect along a line.