Skip to main content

MATH 345: Linear Algebra and Optimization

Sebastien Roch with Jacob Denson and Kaitlyn Phillipson

Section 2.2 Linear systems

The preview examples had different stories: reachable outputs, invisible changes, redundant features. Algebraically, they all ask the same question: can a list of linear equations in the unknown input coordinates be solved?
🔗

Subsection Definitions and examples

Definition 2.2.1. Linear equations.

An equation of the form
\begin{equation*} a_1x_1 + a_2x_2 + \cdots + a_nx_n = b \end{equation*}
where \(a_1,\dots,a_n,b\) are scalars, and \(x_1,\dots,x_n\) are variables is called a linear equation. The real quantities \(a_1,\ldots,a_n\) are called coefficients, \(b\) is called a constant, while the variables \(x_1,\ldots,x_n\) are called unknowns.
🔗
🔗

Definition 2.2.2. Systems of linear equations.

A system of linear equations or linear system is a set of \(m\) linear equations each in \(n\) unknowns. A linear system has the form
\begin{equation} \begin{array}{ccccccccc} a_{11}x_1 \amp + \amp a_{12}x_2 \amp + \amp \cdots \amp + \amp a_{1n}x_n \amp = \amp b_1 \\ a_{21}x_1 \amp + \amp a_{22}x_2 \amp + \amp \cdots \amp + \amp a_{2n}x_n \amp = \amp b_2 \\ \vdots \amp \amp \vdots \amp \amp \amp \amp \vdots \amp \amp \vdots \\ a_{m1}x_1 \amp + \amp a_{m2}x_2 \amp + \amp \cdots \amp + \amp a_{mn}x_n \amp = \amp b_m \end{array}\tag{2.2.1} \end{equation}
where \(a_{11},\dots,a_{mn}\) and \(b_1,\dots,b_m\) are constants.
🔗
A solution to the linear system (2.2.1) is a sequence of \(n\) numbers \(s_1,\ldots,s_n\) so that each equation in (2.2.1) is satisfied when the substitutions \(x_1 = s_1\text{,}\) \(x_2=s_2,\ldots,x_n=s_n\) are made.
🔗
🔗

Warning 2.2.3. Variable names.

We use \(x,y,z\) in geometric examples and \(x_1,\dots,x_n\) for general systems.
🔗
🔗

Activity 2.2.4. Nonlinear equations (U2-LO1).

What are some equations that are not linear equations?
🔗
Solution.
Here are four examples:
🔗
  • \(x^2 + y = 1\) is nonlinear because of the squared term \(x^2\text{.}\)
    🔗
    🔗
  • \(xy = 2\) is nonlinear because of the product of variables \(xy\text{.}\)
    🔗
    🔗
  • \(\sin(x) + y = 0\) is nonlinear because of the sine function \(\sin\text{.}\)
    🔗
    🔗
  • \(\sqrt{x} + y = 1\) is nonlinear because of the square root \(\sqrt{x}\text{.}\)
    🔗
    🔗
🔗
🔗
Before introducing a general algorithm, we look at a few small systems where the equations can be analyzed directly.
🔗

Activity 2.2.5. Forest animals (U2-LO1, U2-LO2).

In a Wisconsin forest, there are robins and badgers. Together they have \(18\) heads and \(56\) legs. How many robins and badgers are in the forest?
🔗
Solution.
Let \(x\) be the number of robins, and \(y\) the number of badgers.
🔗
Heads
🔗
\(x + y = 18\)
Legs
🔗
\(2x + 4y = 56\)
Rearranging the first equation, we find \(y = 18-x\text{.}\) Substituting this into the second equation:
🔗
\begin{align*} 2x + 4(18-x) \amp = 56\\ 2x + 72 - 4x \amp = 56\\ -2x \amp = -16\\ x \amp = 8 \end{align*}
🔗
Since \(y = 18 - x\) and \(x = 8\text{,}\) \(y = 10\text{.}\)
🔗
So there are \(8\) robins in the forest, and \(10\) badgers in the forest.
🔗
🔗
🔗

Activity 2.2.6. Identifying coefficients, constants, and unknowns (U2-LO1).

Identify the coefficients, the constants and the unknowns in each linear equation in Activity 2.2.5.
🔗
Solution.
Table 2.2.7. Table of coefficients, constants, and unknowns.
🔗
Equation Coefficients Constants Unknowns
\(x + y = 18\) \(1,1\) \(18\) \(x,y\)
\(2x + 4y = 56\) \(2,4\) \(56\) \(x,y\)
🔗
🔗

Definition 2.2.8. Consistency and equivalence.

  • If a linear system has no solution, it is called inconsistent.
    🔗
    🔗
  • If a linear system has at least one solution, it is called consistent. Note that an equation with infinitely many solutions is still consistent!
    🔗
    🔗
  • If two linear systems have exactly the same solutions, they are called equivalent.
    🔗
    🔗
🔗

Activity 2.2.9. Yet another forest problem (U2-LO1, U2-LO2).

In another Wisconsin forest, there are deer and badgers. Together they have \(18\) heads and \(56\) legs. How many deer and badgers are in the forest? Is the resulting linear system consistent or inconsistent?
🔗
Solution.
Let \(x\) be the number of deer, and \(y\) the number of badgers.
🔗
Heads
🔗
\(x + y = 18\)
Legs
🔗
\(4x + 4y = 56\)
From the second equation:
🔗
\begin{align*} 4(x + y) \amp = 56\\ x + y \amp = 56/4 = 14 \end{align*}
This system is inconsistent, since the first equation gives \(x + y = 18\) but the second gives \(x + y = 14\text{.}\) Try substituting the first equation into the second one.
🔗
🔗
🔗

Subsubsection Geometric examples in \(\mathbb R^2\) and \(\mathbb R^3\text{:}\) building intuition

Recall that a line in the plane which passes through a point \(P_0(x_0,y_0)\text{,}\) and has slope \(m\text{,}\) can be written in point-slope form, as a set of points \(P(x,y)\) which solve the equation
\begin{equation*} y - y_0 = m(x - x_0). \end{equation*}
🔗
Example 2.2.10. The geometric point of view (U2-LO1, U2-LO2).
Consider the following three systems, inspired by our forest examples. Let’s graph the lines defined by these equations and check how this reflects the number of solutions in each case.
🔗
(a)
System 1
\begin{align*} x + y \amp = 18\\ 2x + 4y \amp = 56 \end{align*}
🔗
Two lines intersect at the unique solution (8,10).
The solid blue line is \(x+y=18\text{,}\) and the dashed orange line is \(2x+4y=56\text{.}\) On axes with equal scales, the lines cross at the marked point \((8,10)\text{,}\) the system’s only solution.
🔗
Figure 2.2.11. System 1: the two lines intersect at \((8,10)\text{.}\)
🔗
🔗
(b)
System 2
\begin{align*} x + y \amp = 18\\ 4x + 4y \amp = 56 \end{align*}
🔗
Two distinct parallel lines show that the system has no solution.
The solid blue line \(x+y=18\) crosses the axes at \((18,0)\) and \((0,18)\text{.}\) The dashed orange line \(4x+4y=56\text{,}\) equivalently \(x+y=14\text{,}\) crosses them at \((14,0)\) and \((0,14)\text{.}\) Both lines have slope \(-1\text{,}\) so they never intersect.
🔗
Figure 2.2.12. System 2: the two lines are parallel and distinct, so there is no solution.
🔗
🔗
(c)
System 3
\begin{align*} x + y \amp = 18\\ 4x + 4y \amp = 72 \end{align*}
🔗
Two coincident lines show infinitely many solutions.
The solid blue line \(x+y=18\) and the dashed orange line \(4x+4y=72\) lie exactly on top of one another. The orange dashes are drawn over the wider blue line so both remain visible. Every point on this common line is a solution.
🔗
Figure 2.2.13. System 3: the two lines coincide, giving infinitely many solutions.
🔗
🔗
System 1 has one intersection point: subtracting \(x+y=18\) from \(x+2y=28\) gives \(y=10\text{,}\) so \(x=8\text{.}\) System 2 gives \(x+y=18\) and \(x+y=14\text{,}\) so the two lines are parallel and the system has no solution. System 3 is the same line twice, since \(4x+4y=72\) is equivalent to \(x+y=18\text{,}\) so it has infinitely many solutions.
🔗
🔗
The same word “solution” also has a geometric meaning. A solution set can be a point, a line, a plane, empty, or higher-dimensional. In three dimensions, the solution set of a linear equation is a plane, provided at least one variable has a nonzero coefficient. To obtain an equation for such a plane, we take a different approach from the point-slope form used for lines in two dimensions. We use a normal vector, which points at right angles to the plane and thus gives a direction in which the plane does not travel.
🔗
Definition 2.2.14. Normal vector equation for planes.
The plane passing through \(P_0(x_0,y_0,z_0)\) with normal vector \(\mathbf{n}\) is the set of all points \(P(x,y,z)\) such that \(\mathbf{x} - \mathbf{x}_0\) is orthogonal to \(\mathbf{n}\text{.}\) That is,
\begin{equation*} \mathbf{n} \cdot (\mathbf{x} - \mathbf{x}_0) = 0, \end{equation*}
or in scalar form, if \(\mathbf{n}=\begin{bmatrix}n_1\\n_2\\n_3\end{bmatrix}\) and \(\mathbf{x}_0=\begin{bmatrix}x_0\\y_0\\z_0\end{bmatrix}\text{,}\)
\begin{equation*} n_1(x - x_0) + n_2(y - y_0) + n_3(z - z_0) = 0. \end{equation*}
🔗
In general form, this equation is written as
\begin{equation*} ax+by+cz=d, \end{equation*}
where \(a=n_1\text{,}\) \(b=n_2\text{,}\) \(c=n_3\text{,}\) and
\begin{equation*} d=n_1x_0+n_2y_0+n_3z_0. \end{equation*}
🔗
🔗
A plane passing through a point with a given normal vector
A pale blue parallelogram tilted upward to the right represents a plane, with a red point labeled \(\mathbf{x}_0\) lying on it. A thick arrow labeled \(\mathbf{n}\) starts at that point and points upward and to the left, perpendicular to the plane. A small right-angle marker near the base of the arrow indicates the perpendicular relationship.
🔗
Figure 2.2.15. A plane passing through a point \(\mathbf{x}_0\) with normal vector \(\mathbf{n}\text{.}\)
🔗
Activity 2.2.16. A plane from a point and a normal vector (U2-LO1).
Find the equation in general form of the plane passing through the point \(P(1,0,3)\text{,}\) normal to the vector \(\mathbf{n}=\begin{bmatrix}2\\6\\4\end{bmatrix}\text{.}\)
🔗
Solution.
The equation describing the plane is
\begin{equation*} \mathbf{n}\cdot(\mathbf{x}-\mathbf{x}_0)=0, \end{equation*}
which expands as
\begin{equation*} 2(x - 1) + 6y + 4(z - 3) = 0 \end{equation*}
and simplifies to
\begin{equation*} 2x + 6y + 4z = 14. \end{equation*}
🔗
🔗
🔗
Shapes in three-dimensional space described as the zeros of a single equation are typically two-dimensional. Lines are described as points which satisfy two different equations. If a line in three-dimensional space is equal to the intersection of two planes passing through a point \(\mathbf{x}_0\) (see Figure 2.2.17), with normal vectors \(\mathbf{n}_1\) and \(\mathbf{n}_2\text{,}\) then the line is precisely the set of points \(\mathbf{x}\) which satisfy the two equations
\begin{equation*} \mathbf{n}_1 \cdot (\mathbf{x} - \mathbf{x}_0) = 0 \end{equation*}
and
\begin{equation*} \mathbf{n}_2 \cdot (\mathbf{x} - \mathbf{x}_0) = 0. \end{equation*}
🔗
A line defined as the intersection of two planes passing through a common point.
Two translucent parallelograms, one blue and one red, cross each other in space. Their overlap is a dark slanted line that passes through a red point labeled \(\mathbf{x}_0\text{.}\) Arrows labeled \(\mathbf{n}_1\) and \(\mathbf{n}_2\) show normal directions for the two planes.
🔗
Figure 2.2.17. A line defined as the intersection of two planes, with normal vectors \(\mathbf{n}_1\) and \(\mathbf{n}_2\text{,}\) passing through a common point \(\mathbf{x}_0\text{.}\)
🔗
Definition 2.2.18. Parametric equation for a line.
The line through \(P_0(x_0,y_0,z_0)\) with direction vector \(\mathbf{d}\) is the set of points \(P(x,y,z)\) of the form
\begin{equation*} \mathbf{x}=\mathbf{x}_0+t\mathbf{d}, \end{equation*}
where \(\mathbf{x}_0\) is the vector corresponding to \(P_0\text{.}\) In coordinates, if \(\mathbf{d}=\begin{bmatrix}d_1\\d_2\\d_3\end{bmatrix}\text{,}\) this says
\begin{equation*} (x,y,z)=(x_0+td_1,y_0+td_2,z_0+td_3). \end{equation*}
If \(d_1,d_2,d_3\) are all nonzero, we can also write the line in symmetric form as the set of points \(P(x,y,z)\) such that
\begin{equation*} \frac{x - x_0}{d_1} = \frac{y - y_0}{d_2} = \frac{z - z_0}{d_3}. \end{equation*}
All three values in this equation are equal to the scalar \(t\) which occurs in the first equations.
🔗
🔗
A line defined by a direction vector, a point, and its corresponding vector.
A slanted black line passes through a red point labeled \(P_0\text{.}\) From that point, a red arrow labeled \(\mathbf{d}\) points along the line’s direction. A nearby label \(\mathbf{x}_0+t\mathbf{d}\) marks the parametric form for points on the line.
🔗
Figure 2.2.19. A line defined by a direction vector \(\mathbf{d}\) and a point \(P_0\text{,}\) with corresponding vector \(\mathbf{x}_0\text{.}\)
🔗
Activity 2.2.20. A parametric line through two points (U2-LO1).
Find a parametric equation for the line passing through the two points \((3,1,0)\) and \((-3,1,4)\text{.}\)
🔗
Solution.
We may choose \(\mathbf{d}\) to be equal to
\begin{equation*} \begin{bmatrix}3\\1\\0\end{bmatrix} - \begin{bmatrix}-3\\1\\4\end{bmatrix} = \begin{bmatrix}6\\0\\-4\end{bmatrix}. \end{equation*}
If we let \(\mathbf{x}_0=\begin{bmatrix}3\\1\\0\end{bmatrix}\text{,}\) then the parametric equation is
\begin{equation*} \mathbf{x}= \begin{bmatrix}3\\1\\0\end{bmatrix} +t\begin{bmatrix}6\\0\\-4\end{bmatrix}. \end{equation*}
If we let \(\mathbf{x}_0=\begin{bmatrix}-3\\1\\4\end{bmatrix}\text{,}\) then we obtain a different parameterization, namely
\begin{equation*} \mathbf{x}= \begin{bmatrix}-3\\1\\4\end{bmatrix} +t\begin{bmatrix}6\\0\\-4\end{bmatrix}. \end{equation*}
Both parameterizations define the same line. Because the second component of the direction vector is zero, a symmetric-equation form would need a separate caveat; the parametric form above is the clean description of the line.
🔗
🔗
🔗
Activity 2.2.21. A plane perpendicular to a line (U2-LO1).
Find the scalar equation of the plane through \(P=(4,2,1)\) and perpendicular to the line
\begin{equation*} x=1+5t,\qquad y=-1+4t,\qquad z=2+3t. \end{equation*}
🔗
Solution.
The direction vector of the line is
\begin{equation*} \mathbf{d}=\begin{bmatrix}5\\4\\3\end{bmatrix}. \end{equation*}
Because the plane is perpendicular to the line, \(\mathbf{d}\) is a normal vector for the plane. Therefore
\begin{equation*} 5(x-4)+4(y-2)+3(z-1)=0. \end{equation*}
🔗
🔗
🔗
Example 2.2.22. A line of intersection from two planes.
We seek to find a parametric equation for the line of intersection of
\begin{equation*} x+y+z=1,\qquad -x+2y-3z=-1. \end{equation*}
🔗
First set \(z=0\text{.}\) Then
\begin{equation*} x+y=1,\qquad -x+2y=-1. \end{equation*}
Adding the two equations eliminates \(x\) and gives \(3y=1+(-1)=0\text{,}\) so \(y=0\text{.}\) Substituting into the first equation gives \(x=1-y=1\text{.}\) Thus \(P(1,0,0)\) is on the line.
🔗
Next set \(z=1\text{.}\) Then
\begin{equation*} x+y=0,\qquad -x+2y=2. \end{equation*}
Adding the two equations eliminates \(x\) and gives \(3y=0+2=2\text{,}\) so \(y=\frac23\text{.}\) Substituting into the first equation gives \(x=-y=-\frac23\text{.}\) Thus \(Q(-\frac23,\frac23,1)\) is also on the line.
🔗
Hence a direction vector is
\begin{equation*} \mathbf{v}=\overrightarrow{PQ} =\begin{bmatrix}-\frac23-1\\\frac23-0\\1-0\end{bmatrix} =\begin{bmatrix}-\frac53\\\frac23\\1\end{bmatrix}. \end{equation*}
Thus one parametrization is
\begin{equation*} \mathbf{x}=\begin{bmatrix}1\\0\\0\end{bmatrix}+t\begin{bmatrix}-\frac53\\\frac23\\1\end{bmatrix}. \end{equation*}
🔗
This example shows how finding the intersection of planes leads naturally to solving systems of linear equations.
🔗
🔗
Warning 2.2.23. Parallel planes.
The method above assumes the two planes intersect in a line. If the normal vectors are parallel, then the planes are either identical or have no intersection.
🔗
🔗
🔗
In Section 2.1, the question “can this output be produced?” became a question about whether a system can be solved.
🔗

Activity 2.2.24. Revisiting a requested output as equations (U2-LO1, U2-LO3).

Return to Activity 2.1.3:
\begin{equation*} A= \begin{bmatrix} 1\amp0\\ 0\amp1\\ 1\amp1 \end{bmatrix}. \end{equation*}
Write \(A\mathbf{x}=\mathbf{b}\) for the two targets
\begin{equation*} \mathbf{b}_1=\begin{bmatrix}1\\2\\3\end{bmatrix}, \qquad \mathbf{b}_2=\begin{bmatrix}1\\2\\4\end{bmatrix}. \end{equation*}
What equations do these two targets produce? Which target is reachable?
🔗
Solution.
For \(\mathbf{b}_1\text{,}\) the equations are
\begin{equation*} x_1=1,\qquad x_2=2,\qquad x_1+x_2=3. \end{equation*}
These equations can all hold at the same time, so \(\mathbf{b}_1\) is reachable.
🔗
For \(\mathbf{b}_2\text{,}\) the equations are
\begin{equation*} x_1=1,\qquad x_2=2,\qquad x_1+x_2=4. \end{equation*}
The first two equations force \(x_1+x_2=3\text{,}\) not \(4\text{.}\) So \(\mathbf{b}_2\) is not reachable.
🔗
🔗
🔗
🔗

Subsection Matrix form and row operations

A linear system of \(m\) equations in \(n\) unknowns can be written as one matrix equation
\begin{equation*} A\mathbf{x}=\mathbf{b}. \end{equation*}
The coefficients form the matrix \(A\text{,}\) the unknowns form the vector \(\mathbf{x}\text{,}\) and the constants form the vector \(\mathbf{b}\text{.}\) By the definition of the matrix-vector product (Definition 1.3.1), the system is consistent exactly when \(\mathbf{b}\) is a linear combination of the columns of \(A\text{.}\)
🔗

Activity 2.2.25. Matrix equation for a linear system (U2-LO1).

For
\begin{equation*} \begin{array}{ccccccccc} x_1 \amp + \amp 2x_2 \amp + \amp 3x_3 \amp = \amp 6\\ 2x_1 \amp - \amp 3x_2 \amp + \amp 2x_3 \amp = \amp 14\\ 3x_1 \amp + \amp x_2 \amp - \amp x_3 \amp = \amp -2, \end{array} \end{equation*}
write the system as \(A\mathbf{x}=\mathbf{b}\text{.}\)
🔗
Solution.
The matrix equation is
\begin{equation*} \begin{bmatrix}1 \amp 2 \amp 3\\2 \amp -3 \amp 2\\3 \amp 1 \amp -1\end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix} = \begin{bmatrix}6\\14\\-2\end{bmatrix}. \end{equation*}
🔗
🔗
🔗

Definition 2.2.26. Matrices corresponding to linear equations.

The coefficient matrix of a linear system of the form (2.2.1) is the \(m\times n\) matrix
🔗
\begin{equation*} A = \begin{bmatrix} a_{11} \amp a_{12} \amp \cdots \amp a_{1n} \\ a_{21} \amp a_{22} \amp \cdots \amp a_{2n} \\ \vdots \amp \vdots \amp \ddots \amp \vdots \\ a_{m1} \amp a_{m2} \amp \cdots \amp a_{mn} \end{bmatrix} \end{equation*}
The constant vector is
🔗
\begin{equation*} \mathbf{b}=\begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m\end{bmatrix} \end{equation*}
We can adjoin \(\mathbf{b}\) to matrix \(A\) to create the augmented matrix representing our linear system:
🔗
\begin{align*} [A \mid \mathbf{b}] \amp = \left[\begin{array}{cccc|c} a_{11} \amp a_{12} \amp \cdots \amp a_{1n} \amp b_1 \\ a_{21} \amp a_{22} \amp \cdots \amp a_{2n} \amp b_2 \\ \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\ a_{m1} \amp a_{m2} \amp \cdots \amp a_{mn} \amp b_m \end{array}\right] \end{align*}
🔗
🔗
We will build a method of efficiently solving a large system of linear equations by applying one of several elementary operations to the system, which do not change the solutions to the system, with the hope of eventually simplifying the system to one in which the set of solutions is obvious.
🔗

Definition 2.2.27. Elementary operations.

The following operations, called elementary operations, can be performed on systems of linear equations, and produce equivalent systems.
🔗
  1. Interchanging the \(i\)-th and \(j\)-th equations.
    🔗
  2. Multiplying an equation by a nonzero constant.
    🔗
  3. Replacing the \(i\)-th equation by \(c\) times the \(j\)-th equation plus the \(i\)-th equation, where \(i \ne j\text{,}\) for some real quantity \(c\text{.}\)
    🔗
🔗
We can track these operations more easily using an array/matrix to record the coefficients and constants.
🔗

Example 2.2.28. Elementary operations with matrices (U2-LO1, U2-LO2).

Consider the linear system
\begin{equation*} \begin{array}{cccccccccc} \amp \amp y \amp \amp - \amp z \amp = \amp 4 \amp \\ 2x \amp \amp \amp \amp + \amp 6z \amp = \amp 4 \amp \\ 3x \amp + \amp 2y \amp \amp + \amp 2z \amp = \amp -1 \amp \end{array} \end{equation*}
This system is reduced to a simpler system using elementary operations. We find the augmented matrix for each linear system and describe the operation used to obtain it from the previous one.
🔗
The initial system and augmented matrix are
🔗
\begin{equation*} \begin{array}{cccccccccc} \amp \amp y \amp \amp - \amp z \amp = \amp 4 \amp \\ 2x \amp \amp \amp \amp + \amp 6z \amp = \amp 4 \amp \\ 3x \amp + \amp 2y \amp \amp + \amp 2z \amp = \amp -1 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 0 \amp 1 \amp -1 \amp 4 \\ 2 \amp 0 \amp 6 \amp 4 \\ 3 \amp 2 \amp 2 \amp -1 \end{array}\right] \end{equation*}
🔗
Interchange rows \(1\) and \(2\text{:}\)
🔗
\begin{equation*} \begin{array}{cccccccccc} 2x \amp \amp \amp \amp + \amp 6z \amp = \amp 4 \amp \\ \amp \amp y \amp \amp - \amp z \amp = \amp 4 \amp \\ 3x \amp + \amp 2y \amp \amp + \amp 2z \amp = \amp -1 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 2 \amp 0 \amp 6 \amp 4 \\ 0 \amp 1 \amp -1 \amp 4 \\ 3 \amp 2 \amp 2 \amp -1 \end{array}\right] \end{equation*}
🔗
Divide first row by \(2\text{:}\)
🔗
\begin{equation*} \begin{array}{cccccccccc} x \amp \amp \amp \amp + \amp 3z \amp = \amp 2 \amp \\ \amp \amp y \amp \amp - \amp z \amp = \amp 4 \amp \\ 3x \amp + \amp 2y \amp \amp + \amp 2z \amp = \amp -1 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 3 \amp 2 \\ 0 \amp 1 \amp -1 \amp 4 \\ 3 \amp 2 \amp 2 \amp -1 \end{array}\right] \end{equation*}
🔗
Replace row \(3\) by row \(3 - 3(\text{row}\ 1)\text{:}\)
🔗
\begin{equation*} \begin{array}{cccccccccc} x \amp \amp \amp \amp + \amp 3z \amp = \amp 2 \amp \\ \amp \amp y \amp \amp - \amp z \amp = \amp 4 \amp \\ \amp \amp 2y \amp \amp - \amp 7z \amp = \amp -7 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 3 \amp 2 \\ 0 \amp 1 \amp -1 \amp 4 \\ 0 \amp 2 \amp -7 \amp -7 \end{array}\right] \end{equation*}
🔗
Replace row \(3\) by row \(3 - 2(\text{row}\ 2)\text{:}\)
🔗
\begin{equation*} \begin{array}{cccccccccc} x \amp \amp \amp \amp + \amp 3z \amp = \amp 2 \amp \\ \amp \amp y \amp \amp - \amp z \amp = \amp 4 \amp \\ \amp \amp \amp \amp \amp -5z \amp = \amp -15 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 3 \amp 2 \\ 0 \amp 1 \amp -1 \amp 4 \\ 0 \amp 0 \amp -5 \amp -15 \end{array}\right] \end{equation*}
🔗
Multiply row \(3\) by \(-1/5\text{:}\)
🔗
\begin{equation*} \begin{array}{cccccccccc} x \amp \amp \amp \amp + \amp 3z \amp = \amp 2 \amp \\ \amp \amp y \amp \amp - \amp z \amp = \amp 4 \amp \\ \amp \amp \amp \amp \amp z \amp = \amp 3 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 3 \amp 2 \\ 0 \amp 1 \amp -1 \amp 4 \\ 0 \amp 0 \amp 1 \amp 3 \end{array}\right] \end{equation*}
🔗
Replace row \(2\) by \(\text{row}\ 2 + \text{row}\ 3\text{:}\)
🔗
\begin{equation*} \begin{array}{cccccccccc} x \amp \amp \amp \amp + \amp 3z \amp = \amp 2 \amp \\ \amp \amp y \amp \amp \amp \amp = \amp 7 \amp \\ \amp \amp \amp \amp \amp z \amp = \amp 3 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 3 \amp 2 \\ 0 \amp 1 \amp 0 \amp 7 \\ 0 \amp 0 \amp 1 \amp 3 \end{array}\right] \end{equation*}
🔗
Replace row \(1\) by \(\text{row}\ 1 - 3(\text{row}\ 3)\text{:}\)
🔗
\begin{equation*} \begin{array}{cccccccccc} x \amp \amp \amp \amp \amp \amp = \amp -7 \amp \\ \amp \amp y \amp \amp \amp \amp = \amp 7 \amp \\ \amp \amp \amp \amp \amp z \amp = \amp 3 \amp \end{array} \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 0 \amp -7 \\ 0 \amp 1 \amp 0 \amp 7 \\ 0 \amp 0 \amp 1 \amp 3 \end{array}\right] \end{equation*}
🔗
🔗
Notice that when we apply elementary operations to a system of linear equations, the corresponding rows of their corresponding matrices also change in an analogous way.
🔗

Definition 2.2.29. Elementary row operations.

An elementary row operation on a matrix \(M\) is any one of the following operations:
🔗
  1. Interchange two rows.
    🔗
  2. Multiply a row by a nonzero scalar.
    🔗
  3. Add a multiple of one row to a different row.
    🔗
🔗

Definition 2.2.30. Row equivalence.

Two matrices \(M\) and \(N\) of the same size are row equivalent if \(N\) can be obtained from \(M\) by a finite sequence of elementary row operations.
🔗
🔗

Warning 2.2.31. Augmented matrices.

In the previous two definitions, the matrices \(M\) and \(N\) can be augmented matrices. In that case, row operations act on every column, including the right-hand-side column.
🔗
🔗
The next step is to choose row operations systematically.
🔗
🔗

Subsection Gaussian elimination

Substitution works for small examples. Gaussian elimination is the systematic version: replace a system by an equivalent, simpler system.
🔗

Activity 2.2.33. Reading a solution from an augmented matrix (U2-LO1, U2-LO2).

The following augmented matrix (see Definition 2.2.26) represents a system of linear equations in three unknowns \(x\text{,}\) \(y\text{,}\) and \(z\text{.}\) Write the corresponding equations, then solve the system.
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 0 \amp -5\\ 0 \amp 1 \amp 0 \amp 2\\ 0 \amp 0 \amp 1 \amp 4 \end{array}\right] \end{equation*}
🔗
Solution.
Rewrite as:
\begin{align*} x \amp \amp \amp \amp \amp \amp = \amp \amp -5\\ \amp \amp y \amp \amp \amp \amp = \amp \amp 2\\ \amp \amp \amp \amp z \amp \amp = \amp \amp 4 \end{align*}
🔗
Solution: \(x = -5\text{,}\) \(y = 2\text{,}\) \(z = 4\text{.}\)
🔗
🔗
🔗

Example 2.2.34. Solving a system using back substitution (U2-LO1, U2-LO2).

We solve the system represented by the following augmented matrix using back substitution.
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 2 \amp 1 \amp 4\\ 0 \amp 1 \amp 2 \amp 2\\ 0 \amp 0 \amp 1 \amp -3 \end{array}\right] \end{equation*}
🔗
We write the corresponding equations:
🔗
\begin{equation*} \begin{array}{ccccccc} x \amp + \amp 2y \amp + \amp z \amp = \amp 4\\ \amp \amp y \amp + \amp 2z \amp = \amp 2\\ \amp \amp \amp \amp z \amp = \amp -3 \end{array} \end{equation*}
🔗
Substitute \(z = -3\) into the second equation:
🔗
\begin{equation*} \begin{array}{ccccccc} \amp \amp y \amp + \amp 2(-3) \amp = \amp 2\\ \amp \amp y \amp \amp \amp = \amp 8 \end{array} \end{equation*}
🔗
Substitute \(y = 8\) and \(z = -3\) into the first equation:
🔗
\begin{equation*} \begin{array}{ccccccc} x \amp + \amp 2(8) \amp + \amp (-3) \amp = \amp 4\\ x \amp \amp \amp \amp \amp = \amp -9 \end{array} \end{equation*}
🔗
Solution: \(x = -9\text{,}\) \(y = 8\text{,}\) and \(z = -3\text{.}\)
🔗
🔗

Definition 2.2.35. Row echelon form and reduced row echelon form.

An \(m\times n\) matrix \(M\) is in row echelon form (REF) if it satisfies the following properties:
  1. All zero rows, if there are any, appear at the bottom of the matrix.
    🔗
  2. The leftmost nonzero entry in any nonzero row is a 1. This entry is called the leading one of its row.
    🔗
  3. For each nonzero row, the leading one appears to the right and below any leading ones in preceding rows.
    🔗
🔗
We say \(M\) is in reduced row echelon form (RREF) if \(M\) is in REF and also satisfies:
  • all columns containing leading ones contain no other non-zero entries.
    🔗
🔗
🔗
A matrix in row echelon form appears as a staircase (or echelon) pattern of leading ones descending from the upper left corner of the matrix. Figure 2.2.36 gives a schematic of a matrix in row echelon form, where the asterisks denote arbitrary constants.
🔗
A staircase schematic of a matrix in row echelon form.
The matrix is drawn with leading \(1\)s stepping down and to the right from row to row. A thick line connects the pivot positions, forming an irregular staircase shape, and asterisks to the right of the pivots represent arbitrary entries.
🔗
Figure 2.2.36. A schematic of a matrix in row echelon form.
🔗

Activity 2.2.37. Identifying REF and RREF matrices (U2-LO2).

For each of the following augmented matrices, determine whether it is in row echelon form, reduced row echelon form, both, or neither.
🔗
(a)
\begin{equation*} A = \left[\begin{array}{cccc|c} 1 \amp 3 \amp 0 \amp 0 \amp 1 \\ 0 \amp 0 \amp 1 \amp 3 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \end{array}\right] \end{equation*}
🔗
Solution.
Both REF and RREF (staircase pattern, 0s in columns with leading ones).
🔗
🔗
🔗
(b)
\begin{equation*} B = \left[\begin{array}{ccc|c} 1 \amp 4 \amp 0 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 1 \amp -2 \end{array}\right] \end{equation*}
🔗
Solution.
Not REF (zero row is not a bottom row).
🔗
🔗
🔗
(c)
\begin{equation*} C = \left[\begin{array}{ccc|c} 1 \amp 3 \amp 5 \amp 7 \\ 0 \amp 1 \amp -1 \amp 5 \\ 0 \amp 0 \amp 1 \amp 10 \\ 0 \amp 0 \amp 0 \amp 0 \end{array}\right] \end{equation*}
🔗
Solution.
REF but not RREF (has nonzero entries above leading ones).
🔗
🔗
🔗
(d)
\begin{equation*} D = \left[\begin{array}{cccc|c} 1 \amp 0 \amp 0 \amp 0 \amp -1 \\ 0 \amp 1 \amp 0 \amp 0 \amp 4 \\ 0 \amp 0 \amp 0 \amp 1 \amp 6 \end{array}\right] \end{equation*}
🔗
Solution.
Both REF and RREF (has zeros above and below leading ones).
🔗
🔗
🔗
(e)
\begin{equation*} E = \left[\begin{array}{ccc|c} 1 \amp 0 \amp 4 \amp 3 \\ 0 \amp 1 \amp 2 \amp 2 \\ 0 \amp 1 \amp -5 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \end{array}\right] \end{equation*}
🔗
Solution.
Not REF (third row has a leading one in same column as second row).
🔗
🔗
🔗
🔗

Definition 2.2.38. Pivot entries, positions, and columns.

For a matrix \(M\) in REF, each leading one is a pivot entry. Its location is a pivot position. A column containing a pivot position is a pivot column.
🔗
🔗
The Gaussian Algorithm gives a procedure to find a row-echelon matrix which is row equivalent to any given matrix. The heuristic is to move from top to bottom and outside in until you obtain a matrix in row-echelon form.
🔗

Note 2.2.41. Row-operation shorthand.

We often record row operations using the symbol \(R_i\) for row \(i\text{.}\) The notation \(R_i \to R_i + cR_j\) means to replace row \(i\) by row \(i\) plus \(c\) times row \(j\text{.}\) All rows not named on the left side stay the same.
🔗
  • \(R_3 \to R_3 - 2R_1\) means replace row \(3\) by row \(3\) minus twice row \(1\text{.}\)
    🔗
    🔗
  • \(R_2 \to \frac{1}{5}R_2\) means multiply row \(2\) by \(1/5\text{.}\)
    🔗
    🔗
  • \(R_1 \leftrightarrow R_2\) means interchange rows \(1\) and \(2\text{.}\)
    🔗
    🔗
🔗

Activity 2.2.42. Finding row echelon forms (U2-LO2).

Find a row echelon form of the augmented matrix \(M\text{.}\)
🔗
\begin{equation*} M = \left[\begin{array}{ccc|c} 0 \amp 0 \amp 1 \amp 2 \\ 3 \amp 3 \amp 6 \amp -9 \\ 2 \amp 3 \amp 0 \amp -2 \end{array}\right] \end{equation*}
Solution.
First nonzero column is column 1. Interchange rows 1 and 2: \(R_1 \leftrightarrow R_2\text{.}\)
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 3 \amp 3 \amp 6 \amp -9 \\ 0 \amp 0 \amp 1 \amp 2 \\ 2 \amp 3 \amp 0 \amp -2 \end{array}\right] \end{equation*}
Multiply first row by \(1/3\text{:}\) \(R_1 \to \frac{1}{3}R_1\text{.}\)
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 1 \amp 2 \amp -3 \\ 0 \amp 0 \amp 1 \amp 2 \\ 2 \amp 3 \amp 0 \amp -2 \end{array}\right] \end{equation*}
Subtract 2 times first row from Row 3: \(R_3 \to R_3 - 2R_1\text{.}\)
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 1 \amp 2 \amp -3 \\ 0 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp -4 \amp 4 \end{array}\right] \end{equation*}
Interchange rows 2 and 3: \(R_2 \leftrightarrow R_3\text{.}\)
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 1 \amp 2 \amp -3 \\ 0 \amp 1 \amp -4 \amp 4 \\ 0 \amp 0 \amp 1 \amp 2 \end{array}\right] \end{equation*}
This augmented matrix is row equivalent to \(M\) and is in REF with leading ones in variable columns 1, 2, and 3.
🔗
🔗
🔗
🔗

Subsection Solving a linear system

Since we can solve systems of linear equations whose augmented matrices are in row echelon form using back substitution as in Example 2.2.34, Algorithm 2.2.40 gives a practical method of solving any system of linear equations.
🔗

Activity 2.2.43. Solving a linear system using row echelon form (U2-LO2).

Solve the linear system
\begin{equation*} \begin{array}{ccccccccc} x \amp + \amp 2y \amp + \amp 3z \amp = \amp 9\\ 2x\amp - \amp y \amp + \amp z \amp = \amp 8\\ 3x\amp \amp \amp - \amp z \amp = \amp 3 \end{array} \end{equation*}
by using Algorithm 2.2.40 to find a matrix in row echelon form which is row equivalent to the augmented matrix \([A \mid \mathbf{b}]\text{.}\)
🔗
Solution.
Augmented matrix:
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 2 \amp 3 \amp 9 \\ 2 \amp -1 \amp 1 \amp 8 \\ 3 \amp 0 \amp -1 \amp 3 \end{array}\right] \end{equation*}
Subtract 2 times Row 1 from Row 2 and subtract 3 times Row 1 from Row 3:
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 2 \amp 3 \amp 9 \\ 0 \amp -5 \amp -5 \amp -10 \\ 0 \amp -6 \amp -10 \amp -24 \end{array}\right] \end{equation*}
Multiply Row 2 by \(-1/5\text{:}\)
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 2 \amp 3 \amp 9 \\ 0 \amp 1 \amp 1 \amp 2 \\ 0 \amp -6 \amp -10 \amp -24 \end{array}\right] \end{equation*}
Add 6 times Row 2 to Row 3:
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 2 \amp 3 \amp 9 \\ 0 \amp 1 \amp 1 \amp 2 \\ 0 \amp 0 \amp -4 \amp -12 \end{array}\right] \end{equation*}
Multiply Row 3 by \(-1/4\text{:}\)
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 2 \amp 3 \amp 9 \\ 0 \amp 1 \amp 1 \amp 2 \\ 0 \amp 0 \amp 1 \amp 3 \end{array}\right] \end{equation*}
This matrix is the augmented matrix of the system of linear equations
\begin{equation*} \begin{array}{ccccccccc} x \amp + \amp 2y \amp + \amp 3z \amp = \amp 9\\ \amp \amp y \amp + \amp z \amp = \amp 2\\ \amp \amp \amp \amp z \amp = \amp 3 \end{array} \end{equation*}
By Theorem 2.2.32, we know that this system is equivalent to the original system of equations specified by the problem. We now apply back substitution to solve the system:
Solving for \(z\)
🔗
Row 3 tells us \(z = 3\text{.}\)
Solving for \(y\)
🔗
Row 2 gives \(y + z = 2\text{,}\) and since \(z = 3\text{,}\) we calculate that \(y = -1\text{.}\)
Solving for \(x\)
🔗
Row 1 gives \(x + 2y + 3z = 9\text{,}\) and since \(y = -1\) and \(z = 3\text{,}\) we calculate that \(x = 2\text{.}\)
So the unique solution is given by \((x,y,z)=(2,-1,3)\text{.}\)
🔗
🔗
🔗

Note 2.2.44.

In Activity 2.2.43, every variable column has a pivot. This is why the system has a unique solution.
🔗
🔗

Definition 2.2.45. Echelon Forms for Linear Systems of Equations.

If the augmented matrix of a linear system is a matrix in row echelon form, we say the linear system is in echelon form. The variables corresponding to variable columns with leading entries are called leading variables (or basic variables), while the other variables are called free variables.
🔗
🔗
Back substitution allows us to write a general solution to a linear system by writing the basic variables in terms of the free variables.
🔗

Example 2.2.46. Solving a system in REF with free variables (U2-LO2).

Let
\begin{equation*} [C \mid \mathbf{d}] = \left[\begin{array}{ccccc|c} 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \\ 0 \amp 1 \amp 2 \amp 3 \amp -1 \amp 7 \\ 0 \amp 0 \amp 1 \amp 2 \amp 3 \amp 7 \\ 0 \amp 0 \amp 0 \amp 1 \amp 2 \amp 9 \end{array}\right] \end{equation*}
be the augmented matrix of a linear system. We solve the system using back substitution.
🔗
The matrix is already in row echelon form, and so we need only back substitute to solve the basic variables. Let \(x_1,x_2,x_3,x_4,x_5\) be the variables. Then the linear system with the corresponding augmented matrix is given by
\begin{equation*} \begin{array}{ccccccccccc} x_1 \amp + \amp 2x_2 \amp + \amp 3x_3 \amp + \amp 4x_4 \amp + \amp 5x_5 \amp = \amp 6\\ \amp \amp x_2 \amp + \amp 2x_3 \amp + \amp 3x_4 \amp - \amp x_5 \amp = \amp 7\\ \amp \amp \amp \amp x_3 \amp + \amp 2x_4 \amp + \amp 3x_5 \amp = \amp 7\\ \amp \amp \amp \amp \amp \amp x_4 \amp + \amp 2x_5 \amp = \amp 9 \end{array} \end{equation*}
The variables \(x_1\text{,}\) \(x_2\text{,}\) \(x_3\text{,}\) and \(x_4\) are the basic variables, and \(x_5\) is a free variable.
🔗
Write the free variable as a parameter \(t\text{,}\) i.e., write
\begin{equation*} x_5 = t \text{.} \end{equation*}
The last row states that \(x_4 + 2x_5 = 9\text{,}\) which, given that \(x_5 = t\text{,}\) can be rearranged to read that
\begin{equation*} x_4 = 9 - 2t\text{.} \end{equation*}
The third row states that \(x_3 + 2x_4 + 3x_5 = 7\text{.}\) Substituting \(x_4 = 9-2t\) and \(x_5 = t\) into this equation and rearranging, we find that
\begin{align*} x_3 + 2(9 - 2t) + 3(t) \amp = 7\\ x_3 + 18 - 4t + 3t \amp = 7\\ x_3 + 18 - t \amp = 7\\ x_3 \amp = -11 + t \end{align*}
The second row states that \(x_2 + 2x_3 + 3x_4 - x_5 = 7\text{.}\) Substituting \(x_3 = -11 + t\text{,}\) \(x_4 = 9-2t\text{,}\) and \(x_5 = t\) into this equation, and rearranging, we find that
\begin{align*} x_2 + 2(-11 + t) + 3(9 - 2t) - (t) \amp = 7\\ x_2 - 22 + 2t + 27 - 6t - t \amp = 7\\ x_2 + 5 - 5t \amp = 7\\ x_2 \amp = 2 + 5t \end{align*}
Finally, the first row says that \(x_1 + 2x_2 + 3x_3 + 4x_4 + 5x_5 = 6\text{.}\) Substituting \(x_2 = 2 + 5t\text{,}\) \(x_3 = -11 + t\text{,}\) \(x_4 = 9 - 2t\text{,}\) and \(x_5 = t\) into this equation and rearranging, we find that
\begin{align*} x_1 + 2(2 + 5t) + 3(-11 + t) \amp\\ \qquad{} + 4(9 - 2t) + 5(t) \amp = 6\\ x_1 + 4 + 10t - 33 + 3t \amp\\ \qquad{} + 36 - 8t + 5t \amp = 6\\ x_1 + 7 + 10t \amp = 6\\ x_1 \amp = -1 - 10t \end{align*}
We now have our solution. All solutions to the linear equation can be written as \(x_1 = -1 - 10t\text{,}\) \(x_2 = 2 + 5t\text{,}\) \(x_3 = -11 + t\text{,}\) \(x_4 = 9 - 2t\text{,}\) and \(x_5 = t\text{,}\) where \(t\) is any real number.
🔗
🔗

Example 2.2.47. Analyzing an inconsistent system (U2-LO2).

Consider a linear system with augmented matrix
\begin{equation*} [C \mid \mathbf{d}] = \left[\begin{array}{cccc|c} 1 \amp 2 \amp -3 \amp 4 \amp 5 \\ 0 \amp 1 \amp 2 \amp 1 \amp -6 \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \end{array}\right]\text{.} \end{equation*}
🔗
The last row has the form
\begin{equation*} [0\ 0\ 0\ 0\mid 1]. \end{equation*}
It represents the equation \(0=1\text{,}\) which is impossible. Therefore the system is inconsistent.
🔗
🔗

Note 2.2.49.

For an augmented matrix \([A\mid \mathbf{b}]\text{,}\) only columns to the left of the vertical line are variable columns. A pivot to the right of the vertical line means the system is inconsistent.
🔗
🔗
Row echelon matrices are not unique for a given starting matrix. For example,
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 3 \amp 9 \amp 1 \\ 0 \amp 1 \amp -6 \amp 2 \\ 0 \amp 0 \amp 1 \amp 0 \end{array}\right] \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 3 \amp 9 \amp 1 \\ 0 \amp 1 \amp 0 \amp 2 \\ 0 \amp 0 \amp 1 \amp 0 \end{array}\right] \end{equation*}
🔗
are row equivalent row echelon matrices, but they are not equal. However, the number of leading ones will be the same in each row equivalent row echelon matrix.
🔗
See Theorem 2.2.50. Together with the inconsistency test, it gives a method for finding the number of solutions to any given linear system.
🔗

Note 2.2.51. The Number of Solutions to a Linear System.

Any linear system belongs to exactly one of three categories.
🔗
  • No solution. This occurs when a row echelon form of \([A\mid \mathbf{b}]\) has a row
    \begin{equation*} [0\ 0\ \cdots\ 0\mid c],\qquad c\ne 0. \end{equation*}
    🔗
    🔗
  • A unique solution. This occurs when the system is consistent and every variable column, meaning every column to the left of the vertical line, is a pivot column.
    🔗
    🔗
  • Infinitely many solutions. This occurs when the system is consistent and at least one variable column, meaning a column to the left of the vertical line, is not a pivot column.
    🔗
    🔗
🔗

Activity 2.2.52. Analyzing solution sets using pivot columns (U2-LO2, U2-LO3).

If
\begin{equation*} C = \left[\begin{array}{ccc|c} 1 \amp 1 \amp 2 \amp 7 \\ 0 \amp 1 \amp 0 \amp 3 \\ 2 \amp 1 \amp 4 \amp 11 \end{array}\right] \end{equation*}
represents the augmented matrix for a system of 3 equations and 3 variables, what can we say about the solution set of the system?
🔗
Solution.
We apply the Gaussian elimination algorithm:
🔗
\begin{equation*} R_3 \to R_3 - 2R_1 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 1 \amp 2 \amp 7 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp -1 \amp 0 \amp -3 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_3 \to R_3 + R_2 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 1 \amp 2 \amp 7 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \end{array}\right] \end{equation*}
🔗
There are two pivot columns to the left of the vertical line and no pivot to the right of the vertical line. The system is consistent. Since there are three variable columns, there is one free variable. The system has infinitely many solutions, parameterized by the free variable.
🔗
🔗
🔗

Activity 2.2.53. Analyzing solution sets using pivot columns (continued) (U2-LO2, U2-LO3).

If
\begin{equation*} D = \left[\begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 2 \amp 1 \amp 2 \amp -1 \end{array}\right] \end{equation*}
represents the augmented matrix for a system of 3 equations and 3 variables, what can we say about the solution set of the system?
🔗
Solution.
We start by applying Gaussian elimination to convert the matrix to row echelon form:
🔗
\begin{equation*} R_3 \to R_3 - 2R_1 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 1 \amp 0 \amp -5 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_3 \to R_3 - R_2 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 0 \amp 0 \amp -8 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_3 \to (-1/8)R_3 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 0 \amp 0 \amp 1 \end{array}\right] \end{equation*}
🔗
The last row has the form
\begin{equation*} [0\ 0\ 0\mid 1]. \end{equation*}
This is a pivot to the right of the vertical line, so the system is inconsistent; there are no solutions to the system of linear equations.
🔗
🔗
🔗

Activity 2.2.54. Reading row reduction in code (U2-LO1, U2-LO2).

SymPy is a Python library for symbolic mathematics and exact arithmetic. Whereas NumPy is designed for numerical array computations, SymPy can, for instance, keep fractions exact during row reduction. We import it with import sympy as sp and create matrices with sp.Matrix, using integer entries to preserve exact arithmetic.
🔗
The following code row reduces the augmented matrix for the two planes
🔗
\begin{equation*} x+y+z=1, \qquad -x+2y-3z=-1. \end{equation*} 
import sympy as sp

M = sp.Matrix([
    [1, 1, 1, 1],
    [-1, 2, -3, -1],
])

M.rref()
Output:
🔗
(Matrix([
[1, 0,  5/3, 1],
[0, 1, -2/3, 0]]), (0, 1))
The output has the form
🔗
(reduced matrix, pivot columns)
SymPy numbers columns starting at \(0\text{.}\) Thus (0, 1) means the first and second columns.
🔗
Read \(M\) as an augmented matrix \([A\mid \mathbf{b}]\text{:}\) the first three columns are coefficient columns, and the last column is the right-hand side.
🔗
  1. Which variable columns are pivot columns?
    🔗
    🔗
  2. Which variable column is not a pivot column?
    🔗
    🔗
  3. Let \(z=t\text{.}\) Use the reduced matrix to write \(x\) and \(y\) in terms of \(t\text{.}\)
    🔗
    🔗
  4. Write the solution set in parametric vector form.
    🔗
    🔗
  5. What kind of solution set is this?
    🔗
    🔗
  6. How does this connect to the line of intersection of two planes?
    🔗
    🔗
Solution.
SymPy reports pivot columns (0, 1), meaning mathematical columns \(1\) and \(2\text{.}\) These are pivot columns to the left of the vertical line, so \(x\) and \(y\) are basic variables. The variable \(z\) is free.
🔗
The reduced matrix represents
\begin{equation*} \begin{aligned} x+\frac{5}{3}z \amp= 1,\\ y-\frac{2}{3}z \amp= 0. \end{aligned} \end{equation*}
🔗
Let \(z=t\text{.}\) Then
\begin{equation*} \begin{aligned} x \amp= 1-\frac{5}{3}t,\\ y \amp= \frac{2}{3}t,\\ z \amp= t. \end{aligned} \end{equation*}
🔗
So the solution set is
\begin{equation*} \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix} + t \begin{bmatrix} -\frac{5}{3}\\ \frac{2}{3}\\ 1 \end{bmatrix}. \end{equation*}
🔗
This is a line. It is the line of intersection of the two planes.
🔗
🔗
🔗

Activity 2.2.55. Solving a linear system with NumPy (U2-LO2).

NumPy’s np.linalg.solve(A, b) computes the solution of \(A\mathbf{x}=\mathbf{b}\) when the coefficient matrix \(A\) is square and has a pivot in every column. We use the system from Activity 2.2.43:
🔗
\begin{equation*} \begin{aligned} x+2y+3z \amp= 9,\\ 2x-y+z \amp= 8,\\ 3x-z \amp= 3. \end{aligned} \end{equation*}
Enter the coefficient matrix and right-hand side as separate arrays. The command uses floating-point arithmetic.
🔗
import numpy as np

A = np.array([
    [1., 2., 3.],
    [2., -1., 1.],
    [3., 0., -1.],
])
b = np.array([9., 8., 3.])

solution = np.linalg.solve(A, b)
print(solution)
print(np.allclose(A @ solution, b))
Output:
🔗
[ 2. -1.  3.]
True
The command np.allclose checks whether the two arrays agree within a small numerical tolerance.
🔗
  1. What are the shapes of A, b, and solution?
    🔗
    🔗
  2. Read the values of \(x\text{,}\) \(y\text{,}\) and \(z\) from the output. Verify them in the three equations.
    🔗
    🔗
  3. What does A @ solution compute, and what does the output True tell us?
    🔗
    🔗
  4. Why can we not apply np.linalg.solve directly to the two-plane system in Activity 2.2.54?
    🔗
    🔗
Solution.
  1. The coefficient matrix has shape (3, 3). Both b and solution have shape (3,); each is a one-dimensional array with three entries.
    🔗
    🔗
  2. The output gives \(x=2\text{,}\) \(y=-1\text{,}\) and \(z=3\text{.}\) Substitution gives
    🔗
    \begin{equation*} \begin{aligned} 2+2(-1)+3(3) \amp= 9,\\ 2(2)-(-1)+3 \amp= 8,\\ 3(2)-3 \amp= 3. \end{aligned} \end{equation*}
    This agrees with the solution obtained by row reduction and back substitution.
    🔗
    🔗
  3. The matrix-vector product A @ solution computes the three left-hand sides. The output True confirms that these values agree with b within the numerical tolerance.
    🔗
    🔗
  4. The two-plane system has a \(2\times 3\) coefficient matrix, which is not square. It also has a free variable and infinitely many solutions. The solve command requires a square coefficient matrix with a pivot in every column; the row-reduction output lets us describe the entire solution set when free variables are present.
    🔗
    🔗
🔗
🔗
🔗

Subsection Homogeneous systems and basic solutions

The preview in Section 2.1 also asked what changes a map forgets (see Activity 2.1.4). That is the special system \(A\mathbf{x}=\mathbf{0}\text{.}\)
🔗

Definition 2.2.56. Homogeneous systems.

If a linear system is of the form
\begin{equation} \begin{array}{ccccccccc} a_{11}x_1 \amp + \amp a_{12}x_2 \amp + \amp \cdots \amp + \amp a_{1n}x_n \amp = \amp 0 \\ a_{21}x_1 \amp + \amp a_{22}x_2 \amp + \amp \cdots \amp + \amp a_{2n}x_n \amp = \amp 0 \\ \vdots \amp \amp \vdots \amp \amp \amp \amp \vdots \amp \amp \vdots \\ a_{m1}x_1 \amp + \amp a_{m2}x_2 \amp + \amp \cdots \amp + \amp a_{mn}x_n \amp = \amp 0 \end{array}\tag{2.2.2} \end{equation}
it is called a homogeneous system.
🔗
  • Note that \(x_1=x_2=\cdots=x_n=0\) is always a solution to a homogeneous system. It is called the trivial solution.
    🔗
    🔗
  • A solution to a homogeneous system where not all \(x_i\) are \(0\) is called a nontrivial solution.
    🔗
    🔗
🔗

Activity 2.2.57. Solving a homogeneous system (U2-LO2).

Solve the homogeneous system
\begin{align*} 2x_1 + 4x_3 + 6x_4 \amp = 0\\ x_1 + 2x_2 + 7x_4 \amp = 0 \end{align*}
🔗
Solution.
Start by writing out the augmented matrix corresponding to the homogeneous system:
\begin{equation*} \left[\begin{array}{cccc|c} 2 \amp 0 \amp 4 \amp 6 \amp 0 \\ 1 \amp 2 \amp 0 \amp 7 \amp 0 \end{array}\right] \end{equation*}
We next use Gaussian elimination (recall Algorithm 2.2.40) to obtain a matrix in row echelon form which is row equivalent to the augmented matrix:
🔗
\begin{equation*} R_1 \to (1/2) R_1 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{cccc|c} 1 \amp 0 \amp 2 \amp 3 \amp 0 \\ 1 \amp 2 \amp 0 \amp 7 \amp 0 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_2 \to R_2 - R_1 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{cccc|c} 1 \amp 0 \amp 2 \amp 3 \amp 0 \\ 0 \amp 2 \amp -2 \amp 4 \amp 0 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_2 \to (1/2) R_2 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{cccc|c} 1 \amp 0 \amp 2 \amp 3 \amp 0 \\ 0 \amp 1 \amp -1 \amp 2 \amp 0 \end{array}\right] \end{equation*}
🔗
If we convert this augmented matrix back to a system of equations, we can (recalling Definition 2.2.45) write the leading variables of the matrix (in this case, \(x_1\) and \(x_2\)) in terms of the free variables (\(x_3\) and \(x_4\)):
\begin{align*} x_1 \amp = -2x_3 - 3x_4\\ x_2 \amp = x_3 - 2x_4 \end{align*}
So if we let \(x_3 = s\) and \(x_4 = t\text{,}\) all solutions to the original linear system are of the form \(x_1 = -2s - 3t\text{,}\) \(x_2 = s - 2t\text{,}\) \(x_3 = s\text{,}\) and \(x_4 = t\text{,}\) where \(s\) and \(t\) are arbitrary real quantities.
🔗
🔗
🔗

Note 2.2.58. Existence of solutions to homogeneous equations.

A homogeneous system of \(m\) linear equations in \(n\) unknowns always has a nontrivial solution if \(n > m\text{,}\) that is if the number of unknowns exceeds the number of equations.
🔗
🔗

Activity 2.2.59. Thinking about homogeneous systems (U2-LO2).

Does a homogeneous system need to have more variables than equations in order to have infinitely many solutions?
🔗
Solution.
No. Such a system has infinitely many solutions whenever it has a free variable, that is, when a row echelon form of the coefficient matrix has fewer pivots than variables.
🔗
🔗
🔗
The solution set of a homogeneous system can be written in vector form.
🔗

Activity 2.2.60. Solutions as linear combinations (U2-LO2, U2-LO4).

Rewrite the general solution to Activity 2.2.57 as an expression involving a linear combination of certain column vectors.
🔗
Solution.
In Activity 2.2.57, we found \(x_1=-2x_3-3x_4\) and \(x_2=x_3-2x_4\text{,}\) with \(x_3\) and \(x_4\) free. Let \(x_3=s\) and \(x_4=t\text{.}\) Collecting the four coordinates into a column vector gives
\begin{equation*} \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4\end{bmatrix} =\begin{bmatrix}-2s-3t \\ s-2t \\ s \\ t\end{bmatrix}. \end{equation*}
🔗
Separate the terms involving \(s\) from those involving \(t\) in each coordinate:
\begin{equation*} \begin{bmatrix}-2s-3t \\ s-2t \\ s \\ t\end{bmatrix} =\begin{bmatrix}-2s \\ s \\ s \\ 0\end{bmatrix} +\begin{bmatrix}-3t \\ -2t \\ 0 \\ t\end{bmatrix}. \end{equation*}
The zero entries record that \(x_3=s\) has no \(t\)-term and \(x_4=t\) has no \(s\)-term.
🔗
Factoring \(s\) out of the first vector and \(t\) out of the second vector gives
\begin{equation*} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = s\begin{bmatrix} -2 \\ 1 \\ 1 \\ 0 \end{bmatrix} + t\begin{bmatrix} -3 \\ -2 \\ 0 \\ 1 \end{bmatrix} \end{equation*}
where \(s,t\in\mathbb R\text{.}\) Thus every solution is a linear combination of these two fixed vectors.
🔗
🔗
🔗

Activity 2.2.62. Finding basic solutions (U2-LO2, U2-LO4).

Consider the homogeneous system whose augmented matrix, when put in RREF, is
\begin{equation*} [A \mid \mathbf{0}] = \left[\begin{array}{ccccc|c} 1 \amp 0 \amp 0 \amp 0 \amp -2 \amp 0 \\ 0 \amp 0 \amp 1 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \amp 5 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \end{array}\right] \end{equation*}
Solve the system, and write the solutions as a linear combination of particular solutions.
🔗
Solution.
Interpret the RREF matrix as a system of linear equations:
\begin{align*} x_1 - 2x_5 \amp = 0\\ x_3 \amp = 0\\ x_4 + 5x_5 \amp = 0 \end{align*}
Next, solve for pivot variables:
\begin{align*} x_1 \amp = 2x_5\\ x_3 \amp = 0\\ x_4 \amp = -5x_5 \end{align*}
Express free variables as parameters:
🔗
Let \(x_2 = s\) and \(x_5 = t\text{.}\) Then
\begin{align*} x_1 \amp = 2t\\ x_2 \amp = s\\ x_3 \amp = 0\\ x_4 \amp = -5t\\ x_5 \amp = t \end{align*}
🔗
Collecting the five coordinates into a column vector gives
\begin{equation*} \begin{bmatrix}x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5\end{bmatrix} =\begin{bmatrix}2t \\ s \\ 0 \\ -5t \\ t\end{bmatrix}. \end{equation*}
🔗
Separate the terms involving \(s\) from those involving \(t\) in each coordinate:
\begin{equation*} \begin{bmatrix}2t \\ s \\ 0 \\ -5t \\ t\end{bmatrix} =\begin{bmatrix}0 \\ s \\ 0 \\ 0 \\ 0\end{bmatrix} +\begin{bmatrix}2t \\ 0 \\ 0 \\ -5t \\ t\end{bmatrix}. \end{equation*}
🔗
Factoring \(s\) out of the first vector and \(t\) out of the second vector gives
\begin{equation*} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = s\begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + t\begin{bmatrix} 2 \\ 0 \\ 0 \\ -5 \\ 1 \end{bmatrix} \end{equation*}
🔗
🔗
🔗

Definition 2.2.63. Basic solutions to homogeneous linear equations.

The Gaussian elimination algorithm produces, for each free variable, a solution to the homogeneous equation \(A \mathbf{x} = \mathbf{0}\text{,}\) by setting that free variable equal to one, and all other free variables equal to \(0\text{.}\) These solutions are called basic solutions, one for every parameter. Every solution can be written uniquely as a linear combination of the basic solutions.
🔗
🔗

Activity 2.2.65. A plane through three points without cross products (U2-LO1, U2-LO2).

Use Gaussian elimination and basic solutions to find an equation for the plane containing
\begin{equation*} P(1,1,-2),\qquad Q(0,2,1),\qquad R(-1,-1,0), \end{equation*}
(without using the cross-product, if you happen to know what that is).
🔗
Solution.
First find two displacement vectors in the plane:
\begin{equation*} \mathbf{u}=\overrightarrow{PQ}=\begin{bmatrix}-1\\1\\3\end{bmatrix}, \qquad \mathbf{v}=\overrightarrow{PR}=\begin{bmatrix}-2\\-2\\2\end{bmatrix}. \end{equation*}
Let \(\mathbf{n}=\begin{bmatrix}a\\b\\c\end{bmatrix}\) be a nonzero normal vector. Then \(\mathbf{n}\) must be perpendicular to both displacement vectors:
\begin{equation*} -a+b+3c=0,\qquad -2a-2b+2c=0. \end{equation*}
🔗
Write this homogeneous system as an augmented matrix:
\begin{equation*} \left[\begin{array}{ccc|c} -1 \amp 1 \amp 3 \amp 0 \\ -2 \amp -2 \amp 2 \amp 0 \end{array}\right]. \end{equation*}
Apply Gaussian elimination, then clear the entry above the second pivot to obtain RREF:
🔗
\begin{equation*} R_1\to -R_1 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp -1 \amp -3 \amp 0 \\ -2 \amp -2 \amp 2 \amp 0 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_2\to R_2+2R_1 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp -1 \amp -3 \amp 0 \\ 0 \amp -4 \amp -4 \amp 0 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_2\to -\tfrac14 R_2 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp -1 \amp -3 \amp 0 \\ 0 \amp 1 \amp 1 \amp 0 \end{array}\right] \end{equation*}
🔗
\begin{equation*} R_1\to R_1+R_2 \end{equation*}
🔗
\begin{equation*} \left[\begin{array}{ccc|c} 1 \amp 0 \amp -2 \amp 0 \\ 0 \amp 1 \amp 1 \amp 0 \end{array}\right] \end{equation*}
🔗
The leading variables are \(a\) and \(b\text{,}\) and \(c\) is free. The reduced equations are
\begin{equation*} a-2c=0,\qquad b+c=0. \end{equation*}
Thus the general solution is
\begin{equation*} \begin{bmatrix}a\\b\\c\end{bmatrix} =\begin{bmatrix}2t\\-t\\t\end{bmatrix} =t\begin{bmatrix}2\\-1\\1\end{bmatrix},\qquad t\in\mathbb R. \end{equation*}
Following Definition 2.2.63, set the single free variable \(c=1\) to obtain the basic solution
\begin{equation*} \mathbf{n}=\begin{bmatrix}2\\-1\\1\end{bmatrix}. \end{equation*}
This nonzero vector is perpendicular to both displacement vectors, so it is a normal vector to the plane.
🔗
Using the point \(P(1,1,-2)\text{,}\) the plane equation is
\begin{equation*} 2(x-1)-(y-1)+(z+2)=0, \end{equation*}
or
\begin{equation*} 2x-y+z=-1. \end{equation*}
🔗
🔗
🔗
For a homogeneous system, row-reducing \([A\mid \mathbf{0}]\) is equivalent to row-reducing \(A\) while remembering that the right-hand side stays zero. The next section gives the solution set of \(A\mathbf{x}=\mathbf{0}\) a name, and from that point on we work with \(A\) alone.
🔗
Homogeneous solution sets are closed under linear combinations. Section 2.3 gives a name to sets with this behavior: subspaces.
🔗
🔗
🔗
PrevTopNext