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.
🔗
  • 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.
🔗
🔗

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.1. Nonlinear equations.

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{.}\)
    🔗
    🔗
🔗
🔗
In Section 2.1, the question “can this output be produced?” became a question about whether a system can be solved.
🔗

Activity 2.2.2. Revisiting a requested output as equations.

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.
🔗
🔗
🔗
Before introducing a general algorithm, we look at a few more small systems where the equations can be analyzed directly.
🔗

Activity 2.2.3. Forest animals.

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.4. Identifying constants and unknowns.

Identify the constants and unknowns in each linear equation in Activity 2.2.3, i.e., the two linear equations \(x + y = 18\) and \(2x + 4y = 56\text{.}\)
🔗
Solution.
Table 2.2.4. Table of constants and unknowns.
🔗
Equation Constants Unknowns
\(x + y = 18\) \(1,1,18\) \(x,y\)
\(2x + 4y = 56\) \(2,4,56\) \(x,y\)
🔗
🔗

Activity 2.2.5. Another forest problem.

In another Wisconsin forest, there are also robins and badgers. Together they have \(18\) heads, \(36\) eyes, and \(56\) legs. How many robins and badgers are in the forest? Can we use any new terminology to describe the resulting system of linear equations that we use to determine the number of robins and badgers?
🔗
Solution.
Let \(x\) be the number of robins, and \(y\) the number of badgers:
🔗
Heads
🔗
\(x + y = 18\)
Eyes
🔗
\(2x + 2y = 36\)
Legs
🔗
\(2x + 4y = 56\)
Note that the second equation gives \(x + y = 18\) after dividing each side by \(2\text{,}\) which is the same as the first equation.
🔗
From the first equation: \(y = 18-x\text{.}\)
🔗
Substitute this into the third 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 and \(10\) badgers in the forest. The system of three linear equations in two unknowns that we have solved in this problem is consistent.
🔗
🔗
🔗

Activity 2.2.6. Forest analysis.

In a third Wisconsin forest, there are deer and badgers. Together they have \(18\) heads and \(70\) legs. How many deer and badgers are in the forest? Can we use any new terminology to describe this system?
🔗
Solution.
Let \(x\) be the number of deer, and \(y\) the number of badgers.
🔗
Heads
🔗
\(x + y = 18\)
Legs
🔗
\(4x + 4y = 70\)
From the second equation:
🔗
\begin{align*} 4(x + y) \amp = 70\\ x + y \amp = 70/4 = 17.5 \end{align*}
This system is inconsistent, since the first equation gives \(x + y = 18\) but the second gives \(x + y = 17.5\text{.}\) Try substituting the first equation into the second one.
🔗
🔗
🔗

Subsubsection Geometric examples

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*}
🔗
Activity 2.2.7. The geometric point of view.
Consider the following three systems, inspired by our forest examples. 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*}
🔗
(b)
System 2
🔗
\begin{align*} x + y \amp = 18\\ 4x + 4y \amp = 72 \end{align*}
🔗
(c)
System 3
🔗
\begin{align*} x + y \amp = 18\\ 4x + 4y \amp = 56 \end{align*}
🔗
🔗
The same word “solution” also has a geometric meaning. A solution set can be a point, a line, a plane, empty, or higher-dimensional.
🔗
To obtain an equation which describes a plane in three-dimensional space, we take a different approach to the point-slope form equation for lines in two-dimensional space. Instead of defining the equation in terms of the direction in which the plane travels, we instead describe the plane in terms of the one direction in which the plane does not travel, i.e., the direction at a right angle to the plane.
🔗
Definition 2.2.5. 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 represents a plane, with a red point labeled \(\mathbf{x}_0\) lying on it. A thick vertical arrow labeled \(\mathbf{n}\) starts at that point and rises perpendicular to the plane. A small right-angle marker near the base of the arrow indicates the perpendicular relationship.
🔗
Figure 2.2.6. A plane passing through a point \(\mathbf{x}_0\) with normal vector \(\mathbf{n}\text{.}\)
🔗
Activity 2.2.8.
Find the equation 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*}
🔗
🔗
🔗
Definition 2.2.7. 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.8. 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.9.
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.10. A plane perpendicular to a line.
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*}
🔗
🔗
🔗
Shapes in three-dimensional space described as the zeros of a single equation are in most cases two-dimensional, so lines must be 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.9), 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.9. 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{.}\)
🔗
Example 2.2.10. A line of intersection from two planes.
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*}
Solving gives \(x=1\) and \(y=0\text{,}\) so \(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*}
Solving gives \(x=-\frac23\) and \(y=\frac23\text{,}\) so \(Q(-\frac23,\frac23,1)\) is also on the line.
🔗
A direction vector is
\begin{equation*} \mathbf{v}=\overrightarrow{PQ}=\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.11. 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.
🔗
🔗
🔗
🔗

Subsection Row operations

All of these examples have the same form. The coefficients form a matrix \(A\text{,}\) the unknowns form a vector \(\mathbf{x}\text{,}\) and the constants form a vector \(\mathbf{b}\text{.}\) The system is \(A\mathbf{x}=\mathbf{b}\text{.}\)
🔗
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 system is consistent exactly when \(\mathbf{b}\) is a linear combination of the columns of \(A\text{.}\)
🔗

Activity 2.2.11. Matrix equation for a linear system.

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 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.12. 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*}
🔗
🔗

Note 2.2.13.

For the system \(A\mathbf{x}=\mathbf{b}\text{,}\) there are three related objects.
🔗
The matrix \(A\) is the coefficient matrix. The vector \(\mathbf{b}\) is the right-hand side. The augmented matrix is
\begin{equation*} [A\mid \mathbf{b}]. \end{equation*}
🔗
When solving a system, row-reduce the augmented matrix \([A\mid \mathbf{b}]\text{.}\) Only columns to the left of the vertical line correspond to variables. The column to the right of the vertical line is not a variable column.
🔗
🔗
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.14. 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.
🔗

Activity 2.2.12. Elementary operations with matrices.

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. Find the augmented matrix for the linear systems, and describe the operation that is performed to obtain this matrix from the previous one.
🔗
Solution.
The initial system and augmented matrix is
🔗
\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.15. 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.16. 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.17. 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.13. Solving systems using back substitution.

The following are augmented matrices (see Definition 2.2.12) representing systems of linear equations in three unknowns \(x\text{,}\) \(y\text{,}\) and \(z\text{.}\) Write the equations corresponding to each system of equations, then solve the systems.
🔗
(a)
\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*}
🔗
Solution.
Rewrite as:
🔗
\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{.}\)
🔗
🔗
🔗
(b)
\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{.}\)
🔗
🔗
🔗
🔗

Definition 2.2.19. 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.20 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.20. A schematic of a matrix in row echelon form.
🔗

Activity 2.2.14. Identifying REF and RREF matrices.

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

Definition 2.2.21. 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.
🔗
🔗

Note 2.2.22.

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

Activity 2.2.15. Reading row reduction in code.

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

Activity 2.2.16. Finding row echelon forms.

Find a row echelon form of the given matrix \(A\text{.}\)
🔗
\begin{equation*} A = \begin{bmatrix} 0 \amp 0 \amp 1 \amp 2 \\ 3 \amp 3 \amp 6 \amp -9 \\ 2 \amp 3 \amp 0 \amp -2 \end{bmatrix} \end{equation*}
Solution.
First nonzero column is column 1. Interchange rows 1 and 2:
🔗
\begin{equation*} \begin{bmatrix} 3 \amp 3 \amp 6 \amp -9 \\ 0 \amp 0 \amp 1 \amp 2 \\ 2 \amp 3 \amp 0 \amp -2 \end{bmatrix} \end{equation*}
Multiply first row by \(1/3\text{:}\)
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 1 \amp 2 \amp -3 \\ 0 \amp 0 \amp 1 \amp 2 \\ 2 \amp 3 \amp 0 \amp -2 \end{bmatrix} \end{equation*}
Subtract 2 times first row from Row 3:
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 1 \amp 2 \amp -3 \\ 0 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp -4 \amp 4 \end{bmatrix} \end{equation*}
Interchange rows 2 and 3:
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 1 \amp 2 \amp -3 \\ 0 \amp 1 \amp -4 \amp 4 \\ 0 \amp 0 \amp 1 \amp 2 \end{bmatrix} \end{equation*}
The matrix is now in REF with leading ones in columns 1, 2, and 3.
🔗
🔗
🔗
Since we can solve systems of linear equations whose augmented matrices are in row echelon form using back substitution as in Activity 2.2.13, Algorithm 2.2.24 gives a practical method of solving any system of linear equations.
🔗

Activity 2.2.17. Solving a linear system using row echelon form.

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.24 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.18, 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.25.

In Activity 2.2.17, every variable column has a pivot. Equivalently, the coefficient matrix can be row-reduced all the way to \(I_3\text{.}\) This is why the system has a unique solution.
🔗
🔗

Definition 2.2.26. 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.
🔗

Activity 2.2.18. Solving a system in REF.

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. Solve the system.
🔗
Solution.
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) + 4(9 - 2t) + 5(t) \amp = 6\\ x_1 + 4 + 10t - 33 + 3t + 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.
🔗
🔗
🔗

Activity 2.2.19. Analyzing an inconsistent system.

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*}
Solve the system.
🔗
Solution.
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.
🔗
🔗
🔗
Row echelon matrices are not unique for a given starting matrix. For example,
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 3 \amp 9 \\ 0 \amp 1 \amp -6 \\ 0 \amp 0 \amp 1 \end{bmatrix} \end{equation*}
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 3 \amp 9 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \end{bmatrix} \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.
🔗
For now, rank is a row-reduction count: the number of pivots. Later we will reinterpret it as the number of independent directions transmitted by a matrix.
🔗

Definition 2.2.28. Rank of a matrix.

The rank of a matrix \(M\) is the number of pivots in any row echelon form row equivalent to \(M\text{.}\)
🔗
🔗

Activity 2.2.20. Finding the rank of a matrix.

Find the rank of
🔗
\begin{equation*} C = \begin{bmatrix} 1 \amp 1 \amp 2 \amp 7 \\ 0 \amp 1 \amp 0 \amp 3 \\ 2 \amp 1 \amp 4 \amp 11 \end{bmatrix} \end{equation*}
Solution.
We convert the matrix to row echelon form using Algorithm 2.2.24. Subtract 2 times Row 1 from Row 3:
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 1 \amp 2 \amp 7 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp -1 \amp 0 \amp -3 \end{bmatrix} \end{equation*}
Add Row 2 to Row 3:
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 1 \amp 2 \amp 7 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \end{bmatrix} \end{equation*}
The matrix is now in REF with 2 leading ones, and so the rank of \(C\) is \(2\text{.}\)
🔗
🔗
🔗

Activity 2.2.21. Finding the rank of a matrix (continued).

Find the rank of
🔗
\begin{equation*} D = \begin{bmatrix} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 2 \amp 1 \amp 2 \amp -1 \end{bmatrix} \end{equation*}
Solution.
Subtract 2 times Row 1 from Row 3:
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 1 \amp 0 \amp -5 \end{bmatrix} \end{equation*}
Subtract Row 2 from Row 3:
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 0 \amp 0 \amp -8 \end{bmatrix} \end{equation*}
Multiply Row 3 by \((-1/8)\text{:}\)
🔗
\begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 1 \amp 2 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 0 \amp 0 \amp 1 \end{bmatrix} \end{equation*}
Matrix is now in REF with 3 leading ones, and so the rank of \(D\) is \(3\text{.}\)
🔗
🔗
🔗
See Theorem 2.2.29. Together with the inconsistency test, it gives a method for finding the number of solutions to any given linear system.
🔗

Note 2.2.30. 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.
    🔗
    🔗
🔗

Note 2.2.31. 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.22. Analyzing solution sets using rank.

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.23. Analyzing solution sets using rank (continued).

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

Subsection Homogeneous systems and basic solutions

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

Definition 2.2.32. 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.24. Solving a homogeneous system.

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.24) 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.26) 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.
🔗
🔗
🔗

Activity 2.2.25. A plane through three points without cross products.

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 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*}
Choose \(c=1\text{.}\) The first equation gives \(b=a-3\text{.}\) Substituting into the second gives
\begin{equation*} -2a-2(a-3)+2=0, \end{equation*}
so \(a=2\text{,}\) and then \(b=-1\text{.}\) One normal vector is
\begin{equation*} \mathbf{n}=\begin{bmatrix}2\\-1\\1\end{bmatrix}. \end{equation*}
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*}
🔗
🔗
🔗

Note 2.2.33. Normal vectors from homogeneous systems.

The plane-through-three-points activity found a normal vector by solving a homogeneous system. Basic solutions below make this procedure systematic.
🔗
🔗

Note 2.2.34. 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.26. Thinking about homogeneous systems.

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 if the rank of the coefficient matrix for the system is smaller than \(n\text{.}\)
🔗
🔗
🔗
The solution set of a homogeneous system can be written in vector form.
🔗

Activity 2.2.27. Solutions as linear combinations.

Rewrite the general solution to Activity 2.2.24 as an expression involving a linear combination of certain column vectors.
🔗
Solution.
Solution set:
\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*}
🔗
🔗
🔗

Activity 2.2.28. Finding basic solutions.

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*}
🔗
Now write the solutions in vector form:
\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.36. 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.
🔗
🔗
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