Table of Contents
Chapter 1: Systems of linear equations
Linear equations
First example: a linear equation in two variables
Consider the equation \[ 2x+5y=7.\] This is an equation in two variables, or indeterminates, $x$ and $y$.
A solution of this equation is a pair of numbers $(a,b)\in \mathbb{R}^2$ so that if we replace $x$ with $a$ and replace $y$ with $b$, then the equation becomes true.
In other words, so that $2a+5b$ really is equal to $7$.
- $(3,1)$ is not a solution, because $2\times 3+5\times 1\ne 7$
- $(1,1)$ is a solution, because $2\times 1+5\times 1=7$
- Other solutions include $(0,\tfrac 75)$, $(0.5,1.2)$, $(6,-1)$, $(3.5,0)$, $(-\tfrac32,2)$, …
We can't make a complete list of all solutions, since there are infinitely many solutions in $\mathbb{R}^2$. However, we can draw the set of all solutions as a subset of $\mathbb{R}^2$. This turns out to be a straight line:
We say that the equation $2x+5y=7$ is a linear equation in two variables.
Definition
If $a,b,c$ are any fixed numbers, then equation \[ ax+by=c\] is a linear equation in two variables.
When you draw the set of all solutions of a linear equation in two variables, you always get a straight line in the $x$-$y$ plane.
More examples of linear equations in two variables
- $y-x=1$
- $x-y=0$
- $x=0\iff 1x+0y=0$
Linear equations in 3 variables
Definition
If $a,b,c,d$ are any fixed numbers, then equation \[ ax+by+cz=d\] is a linear equation in 3 variables.
When you draw the set of all solutions of a linear equation in 3 variables, you always get a plane in 3-dimensional space, $\mathbb{R}^3$.
Examples
Note: you can view the examples below from different angles, by clicking the “Rotate 3D graphics view” button.
- $x+y+z=1$ <html><iframe scrolling=“no” src=“https://tube.geogebra.org/material/iframe/id/528999/width/800/height/503/border/888888/rc/true/ai/false/sdz/true/smb/false/stb/true/stbh/true/ld/false/sri/true/at/auto” width=“800px” height=“503px” style=“border:0px;”> </iframe></html>
- $x+y=1$ This may be viewed as a linear equation in 3 variables, since it is equivalent to $x+y+0z=1$. <html><iframe scrolling=“no” src=“https://tube.geogebra.org/material/iframe/id/529043/width/800/height/503/border/888888/rc/true/ai/false/sdz/true/smb/false/stb/true/stbh/true/ld/false/sri/true/at/auto” width=“800px” height=“503px” style=“border:0px;”> </iframe></html>
- $z=1$, viewed as the equation $0x+0y+z=1$ <html><iframe scrolling=“no” src=“https://tube.geogebra.org/material/iframe/id/529069/width/800/height/503/border/888888/rc/true/ai/false/sdz/true/smb/false/stb/true/stbh/true/ld/false/sri/true/at/auto” width=“800px” height=“503px” style=“border:0px;”> </iframe><br /></html>This plane is horizontal (parallel to the $x$-$y$ plane).
Linear equations (in general)
A linear equation in $m$ variables (where $m$ is some natural number) is an equation of the form \[ a_1x_1+a_2x_2+\dots+a_mx_m=b\] where $a_1,a_2,\dots,a_m$ and $b$ are fixed numbers (called coefficients) and $x_1,x_2,\dots,x_m$ are variables.
Example
\[ 3x_1+5x_2-7x_3+11x_4=12\] is a linear equation in 4 variables.
- A typical solution will be a point $(x_1,x_2,x_3,x_4)\in \mathbb{R}^4$ so that $3x_1+5x_2-7x_3+11x_4$ really does equal $12$.
- For example, $(-2,0,-1,1)$ is a solution.
- The set of all solutions is a 3-dimensional object in $\mathbb{R}^4$, called a hyperplane.
- Since we can't draw pictures in 4-dimensional space $\mathbb{R^4}$ we can't draw this set of solutions!
Systems of linear equations
A system of linear equations is just a list of several linear equations. By a solution of the system, we mean a common solution of each equation in the system.
Example
Find the line of intersection of the two planes \[ x+3y+z=5\] and \[ 2x+7y+4z=17.\]
Just to get an idea of what's going on, here's a picture of the two planes:
<html><iframe scrolling=“no” src=“https://tube.geogebra.org/material/iframe/id/529147/width/800/height/503/border/888888/rc/true/ai/false/sdz/true/smb/false/stb/true/stbh/true/ld/false/sri/true/at/auto” width=“800px” height=“503px” style=“border:0px;”> </iframe></html>
To find the equation of the line of intersection, we must find the points which are solutions of both equations at the same time. Eliminating variables, we get \[ x=-16+5z,\quad y=7-2z\] which tells us that for any value of $z$, the point \[ (-16+5z,7-2z,z)\] is a typical point in the line of intersection.
Let's look at the example from the end of Lecture 2 more closely: $$\begin{array}{ccccccrrr} x&+&3y&+&z&=&5&\quad&(1)\\ 2x&+&7y&+&4z&=&17&&(2)\end{array}$$ We find the solutions of this system by applying operations to the system to make a new system, aiming to end up with a very simple sort of system where we can see the solutions easily.
First replace equation (2) with $(2)-2\times (1)$. We'll call the resulting equations (1) and (2) again, although of course we end up with a different system of linear equations: $$\begin{array}{ccccccrrr} x&+&3y&+&z&=&5&\quad&(1)\\ &&y&+&2z&=&7&&(2)\end{array}$$ Now replace equation (1) with $(1)-3\times (2)$: $$\begin{array}{ccccccrrr} x&&&-&5z&=&-16&\quad&(1)\\ &&y&+&2z&=&7&&(2)\end{array}$$ Notice that we can now easily rearrange (1) to find $x$ in terms of $z$, and we can rearrange (2) to find $y$ in terms of $z$. Since $z$ can take any value, we write $z=t$ where $t$ is a “free parameter” (which means $t$ can be any real number, or $t\in \mathbb{R}$). \begin{align*} x&=-16+5t\\ y&=7-2t\\ z&=t,\qquad t\in \mathbb{R}\end{align*} We can also write this in so-called “vector form”: \[ \begin{bmatrix} x\\y\\z\end{bmatrix}=\begin{bmatrix} -16\\7\\0\end{bmatrix}+t\begin{bmatrix} 5\\-2\\1\end{bmatrix},\qquad t\in \mathbb{R}.\] This is the equation of the line where the two planes described by the original equations (1) and (2) intersect.
Note for each different value of $t$, we get a different solutions (that is, a different point on the line of intersection). For example, setting $t=0$ we see that $(-16,7,0)$ is a solution; setting $t=1.5$, we see that $(-16+1.5\times 5,7+1.5\times (-2),1.5) = (-8.5,4,1.5)$ is another solution, and so on. This works for any value $t\in\mathbb{R}$, and every solution may be written in this way.
Observations
- The operations we applied to the original linear system don't change the set of solutions. This is because each operation is reversible.
- Writing out the variables $x,y,z$ each time is unnecessary. If we erase the variables from the system $$\begin{array}{ccccccrrr} x&+&3y&+&z&=&5&\quad&(1)\\ 2x&+&7y&+&4z&=&17&&(2)\end{array}$$ and write all the numbers in a grid, or a matrix, we get:
\[ \begin{bmatrix} 1&3&1&5\\2&7&4&17\end{bmatrix}\] Notice that the first column corresponds to the $x$ variable, the second to $y$, the third to $z$ and the numbers in the final column are the right hand sides of the equations. Each row corresponds to one equation. So instead of performing operations on equations, we can perform operations on the rows of this matrix: \begin{align*} &\begin{bmatrix} 1&3&1&5\\2&7&4&17\end{bmatrix} \\[6pt]\xrightarrow{R2\to R2-2\times R1}& \begin{bmatrix} 1&3&1&5\\0&1&2&7\end{bmatrix} \\[6pt]\xrightarrow{R1\to R1-3\times R1}& \begin{bmatrix} 1&0&-5&-16\\0&1&2&7\end{bmatrix} \end{align*} Now we translate this back into equations to solve: $$\begin{array}{ccccccrrr} x&&&-&5z&=&-16&\quad&(1)\\ &&y&+&2z&=&7&&(2)\end{array}$$ so \[ \begin{bmatrix} x\\y\\z\end{bmatrix}=\begin{bmatrix} -16\\7\\0\end{bmatrix}+t\begin{bmatrix} 5\\-2\\1\end{bmatrix},\qquad t\in \mathbb{R}.\]
This sort of thing works in general: we can take any system of linear equations, write down a corresponding matrix, perform certain reversible operations on the rows of this matrix to get a new matrix, and then write down a new system of linear equations with the same solutions as the original system. If we do things in a sensible way then the new system will be easy to solve, so we'll be able to solve the original system (since the solution set is the same).
Let's give some terminology which will allow us to make this process clear.
The augmented matrix of a system of linear equations
Definition
Given a system of linear equations: \begin{align*} a_{11}x_1+a_{12}x_2+\dots+a_{1m}x_m&=b_1\\ a_{21}x_1+a_{22}x_2+\dots+a_{2m}x_m&=b_2\\ \hphantom{a_{11}}\vdots \hphantom{x_1+a_{22}}\vdots\hphantom{x_2+\dots+{}a_{nn}} \vdots\ & \hphantom{{}={}\!} \vdots\\ a_{n1}x_1+a_{n2}x_2+\dots+a_{nm}x_m&=b_n \end{align*} its augmented matrix is \[ \begin{bmatrix} a_{11}&a_{12}&\dots &a_{1m}&b_1\\ a_{21}&a_{22}&\dots &a_{2m}&b_2\\ \vdots&\vdots& &\vdots&\vdots\\ a_{n1}&a_{n2}&\dots &a_{nm}&b_n \end{bmatrix}.\]
The numbers in this matrix are called the entries of the matrix. We can be a bit more precise: the number in row $i$ and column $j$ is called the $(i,j)$ entry of the matrix.
Example
To find the augmented matrix of the linear system \begin{align*} 3x+4y+7z&=2\\x+3z&=0\\y-2z&=5 \end{align*} notice that we can rewrite it as \begin{align*} 3x+4y+7z&=2\\{\color{red}1}x+{\color{red}0y}+3z&=0\\{\color{red}0x}+{\color{red}1}y-2z&=5 \end{align*} so the augmented matrix is \[ \begin{bmatrix} 3&4&7&2\\1&0&3&0\\0&1&-2&5\end{bmatrix}.\]
- the $(2,3)$ entry of this matrix is $3$;
- the $(3,2)$ entry is $1$;
- the $(1,4)$ entry is $2$;
- the $(4,1)$ entry is undefined (since this matrix does not have a $4$th row).
Elementary operations on a system of linear equations
If we perform one of the following operations on a system of linear equations:
- list the equations in a different order; or
- multiply one of the equations by a non-zero real number; or
- replace equation $j$ by “equation $j$ ${}+{}$ $c\times {}$ (equation $i$)”, where $c$ is a non-zero real number,
then the new system will have exactly the same solutions as the original system. These are called elementary operations on the linear system.
Why do elementary operations leave the solutions of systems unchanged?
- we are doing the same thing to the left hand side and the right hand side of each equation, so any solution to the original system will also be a solution to the new system; and
- these operations are reversible, using operations of the same type, so any solution to the new system will also be a solution to the original system.
Elementary row operations on a matrix
Recall that when we form the augmented matrix of a linear system, each equation in the system becomes a row of the matrix. So we can translate the elementary operations on the linear system into corresponding operations on the rows of the matrix. We get three different types:
- change the order of the rows of the matrix;
- multiply one of the rows of the matrix by a non-zero real number;
- replace row $j$ by “row $j$ ${}+{}$ $c\times {}$ (row $i$)”, where $c$ is a non-zero real number and $i\ne j$.
The system of linear equations corresponding to these matrices will then have exactly the same solutions.
We call these operations elementary row operations or EROs on the matrix.
Example
Use EROs to find the intersection of the planes \begin{align*} 3x+4y+7z&=2\\x+3z&=0\\y-2z&=5\end{align*}
Solution 1
\begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{3&4&7&2}{1&0&3&0}{0&1&-2&5} \ar{\text{reorder rows}}\go{1&0&3&0}{0&1&-2&5}{3&4&7&2} \ar{R3\to R3-3R1}\go{1&0&3&0}{0&1&-2&5}{0&4&-2&2} \ar{R3\to R3-4R2}\go{1&0&3&0}{0&1&-2&5}{0&0&6&-18} \ar{R3\to \tfrac16 R3}\go{1&0&3&0}{0&1&-2&5}{0&0&1&-3} \end{align*}
So
- from the last row, we get $z=-3$
- from the second row, we get $y-2z=5$, so $y-2(-3)=5$, so $y=-1$
- from the first row, we get $x+3z=0$, so $x+3(-3)=0$, so $x=9$
The conclusion is that \[ \begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}9\\-1\\-3\end{bmatrix}\] is the only solution.
Example
Use EROs to find the intersection of the planes \begin{align*} 3x+4y+7z&=2\\x+3z&=0\\y-2z&=5\end{align*}
Solution 1
\begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{3&4&7&2}{1&0&3&0}{0&1&-2&5} \ar{\text{reorder rows}}\go{1&0&3&0}{0&1&-2&5}{3&4&7&2} \ar{R3\to R3-3R1}\go{1&0&3&0}{0&1&-2&5}{0&4&-2&2} \ar{R3\to R3-4R2}\go{1&0&3&0}{0&1&-2&5}{0&0&6&-18} \ar{R3\to \tfrac16 R3}\go{1&0&3&0}{0&1&-2&5}{0&0&1&-3} \end{align*}
So
- from the last row, we get $z=-3$
- from the second row, we get $y-2z=5$, so $y-2(-3)=5$, so $y=-1$
- from the first row, we get $x+3z=0$, so $x+3(-3)=0$, so $x=9$
The conclusion is that \[ \begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}9\\-1\\-3\end{bmatrix}\] is the only solution.
Solution 2
We start in the same way, but by performing more EROs we make the algebra at the end simpler.
\begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{3&4&7&2}{1&0&3&0}{0&1&-2&5} \ar{\text{reorder rows}}\go{1&0&3&0}{0&1&-2&5}{3&4&7&2} \ar{R3\to R3-3R1}\go{1&0&3&0}{0&1&-2&5}{0&4&-2&2} \ar{R3\to R3-4R2}\go{1&0&3&0}{0&1&-2&5}{0&0&6&-18} \ar{R3\to \tfrac16 R3}\go{1&0&3&0}{0&1&-2&5}{0&0&1&-3} \ar{R2\to R2+2R3}\go{1&0&3&0}{0&1&0&-1}{0&0&1&-3} \ar{R1\to R1-3R3}\go{1&0&0&9}{0&1&0&-1}{0&0&1&-3} \end{align*}
So
- from the last row, we get $z=-3$
- from the second row, we get $y=-1$
- from the first row, we get $x=9$
The conclusion is again that \[ \begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}9\\-1\\-3\end{bmatrix}\] is the only solution.
Discussion
In both of these solutions we used EROs to transform the augmented matrix into a nice form.
- In solution 1, we ended up with the matrix $\left[\begin{smallmatrix}1&0&3&0\\0&1&-2&5\\0&0&1&-3\end{smallmatrix}\right]$ which has a staircase pattern, with zeros below the staircase, and 1s just above the “steps” of the staircase. This is an example of a matrix in row echelon form (see below). We needed a bit of easy algebra, called back substitution, to finish off the solution. (Why is it called echelon form? It seems that this word has an archaic meaning which is relevant to the staircase-like pattern: “any structure or group of structures arranged in a steplike form.”)
- In solution 2, we ended up with the matrix $\left[\begin{smallmatrix}1&0&0&9\\0&1&0&-1\\0&0&1&-3\end{smallmatrix}\right]$ which has a staircase pattern with zeros below the staircase and 1s just above the “steps” of the staircase, and the additional property that we only have zeros above the 1s on the steps. This is an example of a matrix in reduced row echelon form (see below). Finding the solution from this matrix needed no extra algebra.
Row echelon form and reduced row echelon form
Row echelon form (REF)
Definition
A row of a matrix is a zero row if it contains only zeros. For example, $[0\ 0\ 0\ 0\ 0]$ is a zero row.
A row of a matrix is non-zero, or a non-zero row if contains at least one entry that is not $0$. For example $[0\ 0\ 3\ 0\ 0]$ is non-zero, and so is $[1\ 2\ 3\ 4\ -5]$.
Definition
The leading entry of a non-zero row of a matrix is the leftmost entry which is not $0$.
For example, the leading entry of the row $[0~0~0~6~2~0~3~1~0]$ is $6$.
Definition
A matrix is in row echelon form, or REF, if it has all of the following three properties:
- The zero rows of the matrix (if any) are all at the bottom of the matrix.
- In every non-zero row of the matrix, the leading entry is $1$.
- If row $i$ and row $(i+1)$ are both non-zero, then the leading entry in row $(i+1)$ is to the right of the leading entry in row $i$. <html><br /></html>In other words, as you go down the rows, the leading entries must go to the right.
For example, $\left[\begin{smallmatrix} 1&2&3&4&5\\0&1&2&3&4\\0&0&1&2&3\end{smallmatrix}\right]$ and $\left[\begin{smallmatrix} 1&2&3&4&5\\0&1&2&3&4\\0&0&1&2&3\\0&0&0&0&0\end{smallmatrix}\right]$ are both in REF, but
- $\left[\begin{smallmatrix} 1&2&3&4&5\\0&0&0&0&0\\0&0&1&2&3\end{smallmatrix}\right]$ and $\left[\begin{smallmatrix} 1&2&3&4&5\\0&0&0&0&0\\0&0&1&2&3\\0&0&0&0&0\end{smallmatrix}\right]$ are not in REF, since they each have a zero row which isn't at the bottom;
- $\left[\begin{smallmatrix} 1&2&3&4&5\\0&2&3&4&1\\0&0&1&2&3\end{smallmatrix}\right]$ is not in REF, since the leading entry on the second row isn't $1$;
- $\left[\begin{smallmatrix} 0&1&2&3&4\\1&2&3&4&5\\0&0&1&2&3\end{smallmatrix}\right]$ is not in REF, since the leading entry in row $2$ is not to the right of the leading entry in row $1$.
Reduced row echelon form (RREF)
Definition
A matrix is in reduced row echelon form or RREF if it is in row echelon form (REF), so that
- The zero rows of the matrix (if any) are all at the bottom of the matrix.
- In every non-zero row of the matrix, the leading entry is $1$.
- If row $i$ and row $(i+1)$ are both non-zero, then the leading entry in row $(i+1)$ is to the right of the leading entry in row $i$. <html><br /></html>In other words, as you go down the rows, the leading entries must go to the right.
and the matrix also has the property:
<html><ol start=“4”><li class=“level1”><div class=“li”></html> If a column contains the leading entry of a row, then every other entry in that column is $0$. <html></div></li></ol></html>
For example, \[\begin{bmatrix} {\color{blue}1}&{\color{red}2}&{\color{red}3}&4&5\\0&{\color{blue}1}&{\color{red}2}&3&4\\0&0&{\color{blue}1}&2&3\end{bmatrix}\quad\text{and}\quad \begin{bmatrix} {\color{blue}1}&0&{\color{red}3}&4&5\\0&{\color{blue}1}&0&3&4\\0&0&{\color{blue}1}&2&3\end{bmatrix}\] are both in REF, but they are not in RREF because the red entries are non-zero and are in the same column as a leading entry (in blue).
On the other hand, \[\begin{bmatrix} {\color{blue}1}&0&0&4&5\\0&{\color{blue}1}&0&3&4\\0&0&{\color{blue}1}&2&3\end{bmatrix}\] is in RREF.
Example
Use EROs to put the following matrix into RREF: \[\begin{bmatrix} 1&2&3&4&5\\0&1&2&3&4\\0&0&1&2&3\end{bmatrix}\] and solve the corresponding linear system.
Solution
\begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{1&2&3&4&5}{0&1&2&3&4}{0&0&1&2&3} \ar{R2\to R2-2R3}\go{1&2&3&4&5}{0&1&0&-1&-2}{0&0&1&2&3} \ar{R1\to R1-3R3}\go{1&2&0&-2&-4}{0&1&0&-1&-2}{0&0&1&2&3} \ar{R1\to R1-2R2}\go{1&0&0&0&0}{0&1&0&-1&-2}{0&0&1&2&3} \end{align*} This matrix is in RREF. Write $x_i$ for the variable corresponding to the $i$th column. The solution is
- $x_4=t$, a free parameter, i.e. $t\in\mathbb{R}$. This is because the $4$th column does not contain a leading entry.
- From row 3: $x_3+2t=3$, so $x_3=3-2t$
- From row 2: $x_2-t=-2$, so $x_2=-2+t$
- From row 1: $x_1=0$
So the solution is \[ \begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix}=\begin{bmatrix}0\\-2\\3\\0\end{bmatrix}+ t\begin{bmatrix}0\\1\\-2\\1\end{bmatrix},\quad t\in\mathbb{R}.\]
(Geometrically, this is a line in 4-dimensional space $\mathbb{R}^4$).
Solving a system in REF or RREF
Given an augmented matrix in REF (or RREF), each column except the last column corresponds to a variable. These come in two types:
- leading variables are variables whose column contains the leading entry of some row;
- free variables are all the other variables.
Example
For the augmented matrix $$ \begin{bmatrix} 1&2&3&0&0&8\\0&0&1&1&1&5\\0&0&0&1&3&4\end{bmatrix}$$ which is in REF, if we use the variables $x_1,x_2,x_3,x_4,x_5$ then
- $x_1$, $x_3$ and $x_4$ are leading variables, since the corresponding columns have a leading entry
- $x_2$ and $x_5$ are free variables, since the corresponding columns do not have a leading entry
To solve such a linear system, we use the following procedure:
- assign a free parameter (a letter like $r,s,t,\dots$ representing some arbitrary real number) to each free variable
- starting at the bottom of the matrix, write out each row and rearrange it to give an equation for its leading variable, substituting the other variables as needed.
In the example above, this gives:
- $x_2$ and $x_5$ are free, so set $x_2=s$ where $s\in \mathbb{R}$ and $x_5=t$ where $t\in \mathbb{R}$
- Working from the bottom: $$ x_4+3x_5=4\implies x_4=4-3x_5=4-3t$$ $$ x_3+x_4+x_5=5\implies x_3=5-x_4-x_5=5-(4-3t)-t=1+2t$$ $$ x_1+2x_2+3x_3=8\implies x_1=8-2x_2-3x_3=8-2s-3(1+2t)=5-2s-6t.$$
So \begin{align*} x_1&=5-2s-6t\\x_2&=s\\x_3&=1+2t\\x_4&=4-3t\\x_5&=t\end{align*} where $s$ and $t$ are free parameters, i.e. $s,t\in \mathbb{R}$.
Writing this solution in vector form gives: $$ \begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix} = \begin{bmatrix} 5\\0\\1\\4\\0\end{bmatrix}+s\begin{bmatrix} -2\\1\\0\\0\\0\end{bmatrix} +t\begin{bmatrix} -6\\0\\2\\-3\\1\end{bmatrix},\quad s,t\in \mathbb{R}.$$
Note that the solution set is a subset of $\mathbb{R}^5$, which is $5$-dimensional space; and the solution set is $2$-dimensional, because there are $2$ free parameters.
Gaussian elimination
We've seen that putting a matrix into REF (or even better, in RREF) makes it easier to solve equations.
Aim: put any matrix into REF using EROs.
Algorithm
- Re-order the rows so that the leftmost leading entry in the matrix is in the top row.
- Divide all of the top row by its leading entry, so that this entry becomes a $1$.
- “Pivot about the leading 1”: subtract multiples of the top row from each row below so that all entries below the leading $1$ in the top row become $0$.
- Go back to the start, ignoring the top row (until no rows remain, except possibly zero rows).
If we want, we can go further and put the matrix into RREF. First put it into REF as above, and then:
- Look at the non-zero row nearest the bottom of the matrix
- Pivot about the leading $1$ in that row and use it to make zeros above: subtract multiples of that row from each row above
- Move to the next row up, and go to step 2 (until no rows remain).
Example
Use Gaussian elimination to solve the linear system \begin{align*} 2x+y+3z+4w&=27\\ x+2y+3z+2w&=30\\x+y+3z+w&=25\end{align*}
Solution 1
We put the augmented matrix into REF: \begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25} \ar{\text{reorder rows (to avoid division)}} \go{1&1&3&1&25}{1&2&3&2&30}{2&1&3&4&27} \ar{R2\to R2-R1\text{ and }R3\to R3-2R2} \go{1&1&3&1&25}{0&1&0&1&5}{0&-1&-3&2&-23} \ar{R3\to R3+R2} \go{1&1&3&1&25}{0&1&0&1&5}{0&0&-3&3&-18} \ar{R3\to-\tfrac13R3} \go{1&1&3&1&25}{0&1&0&1&5}{0&0&1&-1&6} \end{align*} This is in REF. There are leading entries in the columns for $x,y,z$ but not for $w$, so $w=t$ is a free variable (where $t\in\mathbb{R}$). Now $$ z-w=6\implies z=6+w=6+t$$ $$ y+w=5\implies y=5-w=5-t$$ $$ x+y+3z+w=25\implies x=25-y-3z-w=25-(5-t)-3(6+t)-t=2-3t.$$ So $$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix}=\begin{bmatrix} 2\\5\\6\\0\end{bmatrix}+t\begin{bmatrix}-3\\-1\\1\\1\end{bmatrix},\quad t\in\mathbb{R}.$$
Solution 2
We put the augmented matrix into RREF. \begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{2&1&3&4&27}{1&2&3&2&30}{1&1&3&1&25} \ar{\text{do everything as above}} \go{1&1&3&1&25}{0&1&0&1&5}{0&0&1&-1&6} \ar{R1\to R1-3R3} \go{1&1&0&4&7}{0&1&0&1&5}{0&0&1&-1&6} \ar{R1\to R1-R2} \go{1&0&0&3&2}{0&1&0&1&5}{0&0&1&-1&6} \end{align*} This is in RREF. There are leading entries in the columns for $x,y,z$ but not for $w$, so $w=t$ is a free variable (where $t\in\mathbb{R}$). Now $$ z-w=6\implies z=6+w=6+t$$ $$ y+w=5\implies y=5-w=5-t$$ $$ x+3w=2\implies x=2-3w=2-3t$$ So $$ \begin{bmatrix}x\\y\\z\\w\end{bmatrix}=\begin{bmatrix} 2\\5\\6\\0\end{bmatrix}+t\begin{bmatrix}-3\\-1\\1\\1\end{bmatrix},\quad t\in\mathbb{R}.$$
Examples
Example 1
A function $f(x)$ has the form \[ f(x)=ax^2+bx+c\] where $a,b,c$ are constants. Given that $f(1)=3$, $f(2)=2$ and $f(3)=4$, find $f(x)$.
Solution
\begin{gather*} f(1)=3\implies a\cdot 1^2+b\cdot 1 +c = 3\implies a+b+c=3\\ f(2)=2\implies a\cdot 2^2+b\cdot 2 +c = 3\implies 4a+2b+c=2\\ f(3)=4\implies a\cdot 3^2+b\cdot 3 +c = 3\implies 9a+3b+c=4 \end{gather*}
We get a system of three linear equations in the variables $a,b,c$: \begin{gather*} a+b+c=3\\ 4a+2b+c=2\\ 9a+3b+c=4 \end{gather*}
Let's reduce the augmented matrix for this system to RREF.
\begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{1&1&1&3}{4&2&1&2}{9&3&1&4} \ar{R2\to R2-4R1\text{ and }R3\to R3-9R1} \go{1&1&1&3}{0&-2&-3&-10}{0&-6&-8&-23} \ar{R2\to -\tfrac12 R2} \go{1&1&1&3}{0&1&\tfrac32&5}{0&-6&-8&-23} \ar{R3\to R3+6R2} \go{1&1&1&3}{0&1&\tfrac32&5}{0&0&1&7} \ar{R1\to R1-R3\text{ and }R2\to R2-\tfrac32R3} \go{1&1&0&-4}{0&1&0&-5.5}{0&0&1&7} \ar{R1\to R1-R2} \go{1&0&0&1.5}{0&1&0&-5.5}{0&0&1&7} \end{align*} So $a=1.5$, $b=-5.5$ and $c=7$; so \[ f(x)=1.5x^2-5.5x+7.\]
Example 2
Solve the linear system \begin{align*}2x+4y-2z&=1\\x+y+z&=4\\2x+5y+z&=3\end{align*} by transforming the augmented matrix into reduced row echelon form.
Solution
\begin{align*} \def\go#1#2#3{\begin{bmatrix}#1\\#2\\#3\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{3&4&-2&1}{1&1&1&4}{2&5&1&3} \ar{R1\leftrightarrow R2} \go{1&1&1&4}{3&4&-2&1}{2&5&1&3} \ar{R2\to R2-3R1\text{ and }R3\to R3-2R1} \go{1&1&1&4}{0&1&-5&-11}{0&3&-1&-5} \ar{R3\to R3-3R1} \go{1&1&1&4}{0&1&-5&-11}{0&0&14&28} \ar{R3\to \tfrac1{14}R3} \go{1&1&1&4}{0&1&-5&-11}{0&0&1&2} \ar{R1\to R1-R3\text{ and }R2\to R2+5R3} \go{1&1&0&2}{0&1&0&-1}{0&0&1&2} \ar{R1\to R1-R2} \go{1&0&0&3}{0&1&0&-1}{0&0&1&2} \end{align*} The solution is $x=3$, $y=-1$, $z=2$. So there is a unique solution: just one point in $\mathbb{R}^3$, namely $(3,-1,2)$.
Example 3
Solve the linear system \begin{align*}3x+y-2z+4w&=5\\x+z+w&=2\\4x+2y-6z+6w&=0\end{align*}
Solution
\begin{align*} &\go{3&1&-2&4&5}{1&0&1&1&2}{4&2&-6&6&0} \ar{R1\leftrightarrow R2} \go{1&0&1&1&2}{3&1&-2&4&5}{4&2&-6&6&0} \ar{R2\to R2-3R1\text{ and }R3\to R3-4R1} \go{1&0&1&1&2}{0&1&-5&1&-1}{0&2&-10&2&-8} \ar{R3\to R3-2R2} \go{1&0&1&1&2}{0&1&-5&1&-1}{0&0&0&0&-6} \ar{R3\to -\tfrac16 R3} \go{1&0&1&1&2}{0&1&-5&1&-1}{0&0&0&0&1} \end{align*}
This is in REF. The last row corresponds to the equation \[ 0=1\] which clearly has no solution! We conclude that this system has no solutions, and hence the original linear system has no solutions either.
A linear system with no solutions is called inconsistent.
We can detect an inconsistent linear system, since whenever we apply EROs to put the augmented matrix into REF, we will get a row of the form $[0~0~0~\dots~0~*]$ where $*$ is non-zero.
Example 4
For which value(s) of $k$ does the following linear system have infinitely many solutions?
\begin{gather*}x+y+z=1\\x-z=5\\2x+3y+kz=-2\end{gather*}
Solution
\begin{align*} &\go{1&1&1&1}{1&0&-1&5}{2&3&k&-2} \ar{R2\to R2-R1\text{ and }R3\to R3-2R1} \go{1&1&1&1}{0&-1&-2&4}{0&1&k-2&-4} \ar{R2\to -R2} \go{1&1&1&1}{0&1&2&-4}{0&1&k-2&-4} \ar{R3\to R3-R2} \go{1&1&1&1}{0&1&2&-4}{0&0&k-4&0} \end{align*}
If $k-4=0$, then this matrix is in REF: \[\go{1&1&1&1}{0&1&2&-4}{0&0&0&0}\] In this situation, $z$ is a free variable (since there's no leading entry in the third column). For each value of $z$ we get a different solution, so if $k-4=0$, or equivalently, if $k=4$, then there are infinitely many different solutions.
If $k-4\ne0$, then we can divide the third row by $k-4$ to get the REF: \[\go{1&1&1&1}{0&1&2&-4}{0&0&1&0}\] In this situtation, there are no free variables since $x$, $y$ and $z$ are all leading variables. So if $k-4\ne 0$, or equivalently if $k\ne 4$, then there are no free variables so there is not an infinite number of solutions. (The only possibilities are that there is is a unique solution or that the system is inconsistent; and in this case you can check that there is a unique solution, although we don't need to know this to answer the question).
In conclusion, the system has infinitely many solutions if and only if $k=4$.
Observations about Gaussian elimination
We know that we can apply EROs to any augmented matrix into REF.
Suppose the system has $n$ equations and $m$ variables, and let $k$ be the number of non-zero rows in REF. Also suppose the system is consistent: then the REF has no row of the form $[0~0~0~\dots~1]$.
- $k\le n$, because there are only $n$ rows in the whole matrix
- $k$ is precisely the number of leading variables. So $k$ is no bigger $m$, the total number of variables; in symbols, we have $k\le m$.
- All the other variables are free variables, so $$ \text{$m-k$ is the number of free variables.} $$
What does this tell us about the set of solutions? For example, how many solutions are there?
Observation 1: free variables and the number of solutions
For consistent systems, this shows that:
- either $k=m$;
- so $m-k=0$
- there are no free variables
- the system has one solution and no more
- We say it has a unique solution.
- or $k<m$
- so $m-k>0$
- there is at least one free variable
- so the system has infinitely many solutions (one for each value of each free variable)
- The number of free variables, $m-k$, is called the dimension of the solution set.
Observation 2: systems with fewer equations than variables
For consistent systems where $n<m$ (fewer equations than variables):
- $k\le n < m$, so $k<m$.
- So there is at least one free variable.
- So in this situation we always have infinitely many solutions.
Chapter 2: The algebra of matrices
Definition
An $n\times m$ matrix is a grid of numbers with $n$ rows and $m$ columns: \[ A=\begin{bmatrix}a_{11}&a_{12}&\dots&a_{1m}\\a_{21}&a_{22}&\dots&a_{2m}\\\vdots&\vdots&&\vdots\\a_{n1}&a_{n2}&\dots&a_{nm}\end{bmatrix}\]
The $(i,j)$ entry of a matrix $A$ is $a_{ij}$, the number in row $i$ and column $j$ of $A$.
Example
If $B=\begin{bmatrix} 99&3&5\\7&-20&14\end{bmatrix}$, then $B$ is a $2\times 3$ matrix, and the $(1,1)$ entry of $B$ is $b_{11}=99$, the $(1,3)$ entry of $B$ is $b_{13}=5$, the $(2,1)$ entry is $b_{21}=7$, etc.
One more example
Solve the following linear system: \begin{align*} x+y+z&=2\\2x-z&=0\\x+3y+4z&=6\\3x+y&=2\end{align*}
Solution
We remark that there are more equations than unknowns… but this isn't a problem! We proceed as usual:
\begin{align*} \def\go#1#2#3#4{\begin{bmatrix}#1\\#2\\#3\\#4\end{bmatrix}} \def\ar#1{\\[6pt]\xrightarrow{#1}&} &\go{1&1&1&2}{2&0&-1&0}{1&3&4&6}{3&1&0&2} \ar{R2\to R2-2R1,\ R3\to R3-R1\text{ and }R4\to R4-3R1} \go{1&1&1&2}{0&-2&-3&-4}{0&2&3&4}{0&-2&-3&-4} \ar{R3\to R3+R2\text{ and }R4\to R4-R2} \go{1&1&1&2}{0&1&1.5&2}{0&0&0&0}{0&0&0&0} \ar{R1\to R1-R2} \go{1&0&-0.5&0}{0&1&1.5&2}{0&0&0&0}{0&0&0&0} \end{align*}
Now $z$ is a free variable, say $z=t$ where $t\in \mathbb{R}$, and from row 2 we get $y=2-1.5t$ and row 1 gives $x=0.5t$, so the solution is \[ \begin{bmatrix}x\\y\\z\end{bmatrix}=\begin{bmatrix}0\\2\\0\end{bmatrix}+t\begin{bmatrix}0.5\\-1.5\\1\end{bmatrix},\quad t\in\mathbb{R}.\]
Observations about Gaussian elimination
We know that we can apply EROs to any augmented matrix into REF.
Suppose the system has $n$ equations and $m$ variables, and let $k$ be the number of non-zero rows in REF. Also suppose the system is consistent: then the REF has no row of the form $[0~0~0~\dots~1]$.
- $k\le n$, because there are only $n$ rows in the whole matrix
- $k$ is precisely the number of leading variables. So $k$ is no bigger $m$, the total number of variables; in symbols, we have $k\le m$.
- All the other variables are free variables, so $$ \text{$m-k$ is the number of free variables.} $$
What does this tell us about the set of solutions? For example, how many solutions are there?
Observation 1: free variables and the number of solutions
For consistent systems, this shows that:
- either $k=m$;
- so $m-k=0$
- there are no free variables
- the system has one solution and no more
- We say it has a unique solution.
- or $k<m$
- so $m-k>0$
- there is at least one free variable
- so the system has infinitely many solutions (one for each value of each free variable)
- The number of free variables, $m-k$, is called the dimension of the solution set.
Observation 2: systems with fewer equations than variables
For consistent systems where $n<m$ (fewer equations than variables):
- $k\le n < m$, so $k<m$.
- So there is at least one free variable.
- So in this situation we always have infinitely many solutions.