Systems of equations
Lets review the method you use in high-school to solve systems of equations - the elimination method - and then rewrite it under a new notation - the matrix and vector notation.
A few examples will be given.
Key concepts: systems of equations in matrix-vector notation, elimination, pivot, rank, conditions for 1,0 or infinite solutions.
Matrix-vector notation for a system
Consider the system with two equations, called \(l_1\) and \(l_2\):
\[ \begin{cases} x-4y =2\\ 2x-6y = 5 \end{cases} \tag{1}\]
In Equation 1 we find two equations and two unknowns \(x\) and \(y\). We want their values such that both equations are satisfied. (this system represents the interception of two lines)
Using the matrix-vector notation we can write Equation 1 as:
\[ \begin{pmatrix} 1 & -4\\ 2 & -6 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}2\\5\end{pmatrix} \tag{2}\]
Lets read Equation 2 in words: the \(2\) by \(2\) matrix of coefficients is multiplied by the column vector \(\begin{pmatrix}x\\y\end{pmatrix}\) , the result is \(\begin{pmatrix}2\\5\end{pmatrix}\). This is one equation with one unknown, the column vector \(\begin{pmatrix}x\\y\end{pmatrix}\). Traditionally we write Equation 2 as \(A \mathbf{x} =\mathbf{b}\).
How do we multiply a vector by a matrix?
Answer:
\[ \overbrace{\begin{pmatrix} 1 & -4\\ 2 & -6 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}}^\text{matrix-vector mult.} =\overbrace{\begin{pmatrix}1\cdot x-4\cdot y \\ 2\cdot x-6\cdot y\end{pmatrix}}^\text{scalar mult.} \]
Matrix times a vector on the lhs is just a super-compact way of writing the vector on the rhs. Moreover, notice the shapes of the matrix and vectors, this is very, very important. A \(2\) by \(2\) matrix times a \(2\) by \(1\) column vector yields a \(2\) by \(1\) column vector! If you understand this it should not be a problem to see what shapes are or not compatible, check this:
[\(2\times2\)][ \(3\times 1\)] \(=\) Nonsense
[\(3\times2\)][ \(2\times 1\)] \(=\) [\(3\times 1\)]
[\(2\times3\)][ \(3\times 1\)] \(=\) [\(2\times 1\)]
[\(3\times2\)][ \(3\times 1\)] \(=\) Nonsense
[\(1\times3\)][ \(3\times 1\)] \(=\) [\(1\times 1\)]
Solving the system using the Elimination method
Lets solve the system Equation 1 using the traditional rules we already know from high-school, recall:
- you can replace an equation by itself times some constant.
- you can replace any one equation by the sum both equations.
- you can isolate \(x\) or \(y\) in one equation and substitute in the other equation.
In other words, 1. and 2., just say this: you can replace \(l_1\) or \(l_2\) by some convenient combination \(al_1+bl_2\). Rule 3. is known as back-substitution.
Applying any one of these operations yields another and equivalent system of equations.
The central idea of the Elimination method is use linear combination of equations (1. and 2.) to eliminate variables and thus giving us an equivalent and easier to solve system. To eliminate variables we make clever use of rules \(1\) and \(2\). Once the system is simple enough we can use rule \(3\). How do you know what is or not a good combination? We’ll see that with examples. But the guiding principle is to use the pivots.
This recaps what you know and use these rules to solve the Equation 1 and in parallel see the corresponding matrix-vector version.
step 1: Replace equation \(l_2\) by, \(l_2\) minus twice the equation \(l_1\), i.e., make the new second equation \(l_2'\) into \(l_2-2l_1\). This gives us:
\[ \begin{cases}x-4y =2\\2x-6y = 5\end{cases} \overset{l_2'=l_2-2l_1}{\longrightarrow}\begin{cases} x-4y =2\\ 2y = 1\end{cases} \]
Correspondingly in Equation 2 we subtract from row \(l_2\) twice the row \(l_1\), giving us
\[ \begin{pmatrix} 1 & -4\\ 2 & -6 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}2\\5\end{pmatrix}\overset{l_2'=l_2-2l_1}{\longrightarrow} \begin{pmatrix} 1 & -4\\ 0 & 2 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}2\\1\end{pmatrix} \]
A good way to look at this is to focus on using the matrix entry \(1\), to eliminate the matrix entry \(2\). This entry \(1\) is called a pivot entry!
step 2: Multiply equation \(l_2\) by \(1/2\):
\[ \begin{cases} x-4y =2\\ 2y = 1\end{cases}\overset{l_2'=1/2l_2}{\longrightarrow} \begin{cases} x-4y =2\\ y = 1/2\end{cases} \]
In matrix-vector notation we find:
\[ \begin{pmatrix} 1 & -4\\ 0 & 2 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}2\\1\end{pmatrix}\overset{l_2'=1/2l_2}{\longrightarrow} \begin{pmatrix} 1 & -4\\ 0 & 1 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}2\\1/2\end{pmatrix} \]
step 3: Focusing on the second pivot, the \(1\) in row \(l_2\), we eliminate the entry, \(-4\), by replacing \(l_1\) by \(l_1\) plus four times \(l_2\):
\[ \begin{cases} x -4y =2\\ y = 1/2\end{cases}\overset{l_1'=l_1+4l_2}{\longrightarrow}\begin{cases} x =4\\ y = 1/2\end{cases} \]
In matrix-vector notation we find:
\[ \begin{pmatrix} 1 & -4\\ 0 & 1 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}2\\1/2\end{pmatrix}\overset{l_1'=l_1+4l_2}{\longrightarrow} \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}4\\1/2\end{pmatrix} \]
From which we can read the final result \(x=4\) and \(y=1/2\).
Better notation: Going through the three steps again we notice we can improve our matrix-vector notation by suppressing the column \(\begin{pmatrix}x\\y\end{pmatrix}\) and writing instead the steps as:
\[ \left(\begin{matrix} 1 & -4 \\ 2 & -6 \end{matrix}\;\middle|\; \begin{matrix} 2\\5\end{matrix}\right) \overset{l_2'=l_2-2l_1}{\longrightarrow} \left(\begin{matrix} 1 & -4 \\ 0 & 2 \end{matrix}\;\middle|\; \begin{matrix} 2\\1\end{matrix}\right) \overset{l_2'=1/2l_2}{\longrightarrow} \left(\begin{matrix} 1 & -4 \\ 0 & 1 \end{matrix}\;\middle|\; \begin{matrix} 2\\1/2\end{matrix}\right) \overset{l_1'=l_1+4l_2}{\longrightarrow} \left(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\;\middle|\; \begin{matrix} 4\\1/2\end{matrix}\right) \]
From now on we’ll adopt this way of writing systems of equations, its called the extended matrix notation, because we appended a new column to right side of the \(2\times2\) matrix. From the extended matrix we read the solution as follows
\[ \left(\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}\;\middle|\; \begin{matrix} 4\\1/2\end{matrix}\right)\longrightarrow \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}4\\1/2\end{pmatrix}\longrightarrow \begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}4\\1/2\end{pmatrix} \]
where in the last step we multiplied the vector by the matrix.
The vector
\[ \begin{pmatrix}4\\1/2\end{pmatrix} \]
is the solution of
\[ \begin{pmatrix} 1 & -4\\ 2 & -6 \end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}= \begin{pmatrix}2\\5\end{pmatrix} \]
Meaning, the solution of
\[ \begin{cases}x-4y =2\\2x-6y = 5\end{cases} \]
is:
\[ \begin{cases}x =4\\y=1/2\end{cases} \]
More examples of the elimination method
The following examples will be given:
A system with one solution
A system with no solution
A system with many solutions
Another system with many solutions
Example 1: A system with one solution
Consider the following system written in three different notations.
\[ \begin{cases} x+y-z=1\\ 2x-y+2z = 9\\ 2y=-x+z \end{cases} \leftrightsquigarrow \begin{pmatrix} 1 & 1 & -1\\ 2 & -1 & 2\\ 1 & 2 &-1 \end{pmatrix} \begin{pmatrix} x\\ y\\ z \end{pmatrix} = \begin{pmatrix} 1\\ 9\\ 0 \end{pmatrix} \leftrightsquigarrow \left( \begin{matrix} 1 & 1 & -1\\ 2 & -1 & 2\\ 1 & 2 & -1 \end{matrix} \;\middle|\; \begin{matrix} 1\\ 9\\ 0 \end{matrix} \right) \tag{3}\]
(This system represents the interception of three planes, each row of the matrix is a vector perpendicular to a plane)
Again we’ll use the extended notation during the elimination algorithm, because we don’t want to carry around the \(x\), \(y\) and \(z\) at each step.
\[ \begin{align} &\left(\begin{matrix}1 & 1 & -1\\2 & -1 & 2 \\1 & 2 & -1 \end{matrix}\;\middle|\;\begin{matrix}1\\9\\0 \end{matrix}\right) \overset{l_2'=l_2-2l_1\\l_3'=l_3-l_1}{\longrightarrow} \left(\begin{matrix}1 & 1 & -1 \\0 & -3 & 4 \\0 & 1 & 0 \end{matrix}\;\middle|\;\begin{matrix}1\\7\\-1\end{matrix}\right) \overset{l_2 \leftrightarrow l_3}{\longrightarrow} \left(\begin{matrix}1 & 1 & -1 \\0 & 1 & 0\\0 & -3 & 4\end{matrix}\;\middle|\;\begin{matrix}1\\-1\\7\end{matrix}\right)\\ \overset{l_3'=l_3+3l_2}{\longrightarrow} &\left(\begin{matrix}1 & 1 & -1 \\0 & 1 & 0 \\0 & 0 & 4 \end{matrix}\;\middle|\;\begin{matrix}1\\-1\\4\end{matrix}\right) \overset{l_3'=l_3/4}{\longrightarrow}\left(\begin{matrix}1 & 1 & -1 \\0 & 1 & 0 \\0 & 0 & 1 \end{matrix}\;\middle|\;\begin{matrix}1\\-1\\1\end{matrix}\right) \overset{l_1'=l_1+l_3}{\longrightarrow}\left(\begin{matrix}1 & 1 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \end{matrix}\;\middle|\;\begin{matrix}2\\-1\\1\end{matrix}\right) \\ \overset{l_1'=l_1-l_2}{\longrightarrow} &\left(\begin{matrix}1 & 0 & 0 \\0 & 1 & 0 \\0 & 0 & 1 \end{matrix} \;\middle|\;\begin{matrix}3\\-1\\1\end{matrix}\right) \end{align} \]
Each step has its own commentary:
On the first step we use the pivot \(A_{11}=1\) to eliminate the entries \(2\) and \(1\) bellow.
The second step we switched equations, so as to bring a pivot \(1\) at position \(A_{22}\).
The third step consists in using this pivot to eliminate the entry \(-3\) below.
In step four we divided \(l_3\) by \(4\) so that that the pivot \(A_{33}\) is \(1\) instead of \(4\).
At step five we use \(A_{33}\) to eliminate the entry \(-1\) above it.
Step six we just used the pivot \(A_{22}\), to eliminate the entry \(1\) at \(A_{12}\).
After simplification, it is time to go back to the original notation - we find:
\[ \begin{cases} x = 3\\y=-1\\z=1 \end{cases} \]
which is the solution of the system of equations! Correspondingly, the solution for the matrix-vector notation is the following vector
\[ \begin{pmatrix} 2\\ -1\\ 1 \end{pmatrix} \]
Important observations (that we’ll come very useful later): the form of the matrix after all these l.c. of rows, known as the reduced matrix, \(A'\), it has the form of a \(3\times 3\) identity matrix:
\[ \begin{pmatrix}I\end{pmatrix} \]
and its rank is \(3\), meaning, the number of pivots if \(3\). Note as well that if we consider each column of the matrix as a vector, then we find \(3\) independent vectors. We write \(r=3\).
Definition 1 [rank \(r\) of a matrix \(A\)] = \(r\) = [# of pivots] =[# of indep columns of \(A\) or \(A'\)] = [# of indep rows of \(A\) or \(A'\)]=[rank of the reduced matrix \(A'\)]
Moreover, notice that the rank of the extended matrix \(r^*\) is also \(3\). And that the number of columns \(n=3\) as well.
From this example we see something that happens in general:
A system of equations \(A\mathbf{x}=\mathbf{b}\) have one solution provided \(r=r^*=n\).
Example 2: A system with no solution
The system this time is:
\[ \begin{cases} 2x-y=8\\ y+2x = 4\\ x=-y-1 \end{cases} \leftrightsquigarrow \begin{pmatrix} 2 & -1\\ 2 & 1\\ 1 & 1 \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix} = \begin{pmatrix} 8\\ 4\\ -1 \end{pmatrix} \leftrightsquigarrow \left( \begin{matrix} 2 & -1 \\ 2 & 1 \\ 1 & 1 \end{matrix} \;\middle|\; \begin{matrix} 8\\ 4\\ -1 \end{matrix} \right) \tag{4}\]
To find how many solutions \(\begin{pmatrix}x\\y\end{pmatrix}\) are there, we try to compute them using the Elimination algorithm:
\[ \begin{align} &\left(\begin{matrix}2 & -1 \\2 & 1 \\1 & 1 \end{matrix}\;\middle|\;\begin{matrix}8\\4\\-1\end{matrix}\right) \overset{l_1\leftrightarrow l_3}{\longrightarrow} \left(\begin{matrix}1 & 1\\ 2 & 1 \\2 & -1 \end{matrix} \;\middle|\;\begin{matrix}-1\\4\\8\end{matrix}\right) \overset{l_2'=l_2-2l_1\\l_3'=l_3-2l_1}{\longrightarrow} \left(\begin{matrix}1 & 1 \\0 & -1 \\0 & -3 \end{matrix}\;\middle|\;\begin{matrix}-1\\6\\10\end{matrix}\right)\\ \overset{l_2'=-l_2\\l_3'=l_3-3l_2}{\longrightarrow} &\left(\begin{matrix}1 & 1 \\0 & 1 \\0 & 0 \end{matrix} \;\middle|\; \begin{matrix}-1\\-6\\-8\end{matrix}\right) \overset{l_1'=l_1-l_2}{\longrightarrow} \left(\begin{matrix}1 & 0 \\0 & 1 \\0 & 0 \end{matrix} \;\middle|\;\begin{matrix}5\\-6\\-8\end{matrix}\right) \end{align} \]
This means:
\[ \left(\begin{matrix}1 & 0 \\0 & 1 \\0 & 0 \end{matrix} \;\middle|\;\begin{matrix}5\\-6\\-8\end{matrix}\right) \leftrightsquigarrow \begin{pmatrix}1 & 0 \\0 & 1 \\0 & 0 \end{pmatrix} \begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}5\\-6\\-8\end{pmatrix} \]
Now that most simplification is done, lets convert back to the system’s notation:
\[ \begin{cases} x=5\\ y=-6\\ 0=-8 \end{cases} \tag{5}\]
It is clearly impossible. No choice of \(x\) or \(y\) makes this three statements true simultaneously! Since Equation 4 is equivalent to Equation 5, therefore our original system Equation 4 has no solution as well.
Observations: Notice the form of the reduced matrix, \(A'\) is
\[ \begin{pmatrix}I\\\mathbf{0}\end{pmatrix} \]
The fact that \(r=2\), \(r^*=3\) and \(n=2\), shows that \(r<r^*\).
In general: A system of equations \(A\mathbf{x}=\mathbf{b}\) have no solution provided \(r<r^*\).
Example 3: A system with many solutions
The system is:
\[ \begin{cases} x+y-z=0\\ 2x-y+2z = 0\\ \end{cases} \leftrightsquigarrow \begin{pmatrix} 1 & 1 & -1\\ 2 & -1 & 2\\ \end{pmatrix} \begin{pmatrix} x\\ y\\ z \end{pmatrix} = \begin{pmatrix} 0\\ 0 \end{pmatrix} \leftrightsquigarrow \left( \begin{matrix} 1 & 1 & -1\\ 2 & -1 & 2 \\ \end{matrix} \;\middle|\; \begin{matrix} 0\\0 \end{matrix} \right) \tag{6}\]
Solving:
\[ \begin{align} &\begin{pmatrix}1 & 1 & -1 &\bigm| & 0\\2 & -1 & 2 &\bigm| & 0\\\end{pmatrix} \overset{l_2'=l_2-2l_1}{\longrightarrow} \begin{pmatrix}1 & 1 & -1 &\bigm| & 0\\0 & -3 & 4 &\bigm| & 0\end{pmatrix} \overset{l_2'=-1/3l_2}{\longrightarrow} \begin{pmatrix}1 & 1 & -1 &\bigm| & 0\\0 & 1 & -4/3 &\bigm| & 0\end{pmatrix}\\ \overset{l_1'=l_1-l_2}{\longrightarrow} &\begin{pmatrix}1 & 0 & 1/3 &\bigm| & 0\\0 & 1 & -4/3 &\bigm| & 0\end{pmatrix} \end{align} \]
Once again, this notation means:
\[ \begin{pmatrix}1 & 0 & 1/3 &\bigm| & 0\\0 & 1 & -4/3 &\bigm| & 0\end{pmatrix} \leftrightsquigarrow \begin{pmatrix}1 & 0 & 1/3\\0 & 1 & -4/3 \end{pmatrix} \begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix} \tag{7}\]
Converting back to the system notation have:
\[ \begin{cases} x+1/3z =0\\ y-4/3z=0 \end{cases} \iff \begin{cases} x=-1/3z\\ y=4/3z \end{cases} \tag{8}\]
Asking what \((x,y,z)\in \mathbb{R}^3\) that satisfy the equation Equation 6 is equivalent to ask, what is \(x,y,z\in \mathbb{R}\) that satisfy Equation 8 . Each real \(z\) we choose gives us the corresponding \(x\) and \(y\); as a consequence we have many solution. In other words, the solution is
\[ \begin{pmatrix} x\\ y\\ z \end{pmatrix} = \begin{pmatrix} -1/3z\\ 4/3z\\ z \end{pmatrix} \tag{9}\]
Observations: The form of the reduced matrix is:
\[ \begin{pmatrix}I \,\,F\end{pmatrix} \]
where the \(F\) block is the third column \((1/3, -4/3)^\intercal\), while \(I\) is the \(2\) by \(2\) identity.
Additionally, \(r=2\), \(r^*=2\) and \(n=3\). A general rule (to be explained later) is:
A system of equations \(A\mathbf{x}=\mathbf{b}\) have infinite solutions provided \(r=r^*<n\).
Example 4: Another system with many solutions
What is the solution \((x,y, z, w)\) for the following system:
\[ \begin{cases} &x&+ &2 y&+&2 z &+&2w &= 1\\ &2x&+&4y&+&6z&+&8w &= 2\\ &3x&+&6y&+&8z&+&10w &=3 \end{cases} \]
Using elimination algorithm we make linear combinations of the equation with the goal of eliminating variables, here is one way to go
\[
\begin{align}
&\begin{pmatrix}
1 & 2 & 2 & 2 &\bigm|1\\
2 & 4 & 6 & 8 &\bigm|2\\
3 & 6 & 8 & 10 &\bigm| 3
\end{pmatrix}
\overset{l_2' = l_2-2l_1}{\longrightarrow}
\begin{pmatrix}
1 & 2 & 2 & 2 &\bigm| 1\\
0 & 0 & 2 & 4 &\bigm| 0\\
3 & 6 & 8 & 10 &\bigm| 3
\end{pmatrix}
\overset{l_3' = l_3-3l_1}{\longrightarrow}
\begin{pmatrix}
1 & 2 & 2 & 2 &\bigm| 1\\
0 & 0 & 2 & 4 &\bigm| 0\\
0 & 0 & 2 & 4 &\bigm| 0
\end{pmatrix}\\
&\overset{l_3'=l_3-l_2}{\longrightarrow}
\begin{pmatrix}
1 & 2 & 2 & 2 &\bigm| 1\\
0 & 0 & 2 & 4 &\bigm| 0\\
0 & 0 & 0 & 0 &\bigm| 0
\end{pmatrix}
\overset{l_2'=1/2l_2}{\longrightarrow}
\begin{pmatrix}
1 & 2 & 2 & 2 &\bigm| 1\\
0 & 0 & 1 & 2 &\bigm| 0\\
0 & 0 & 0 & 0 &\bigm| 0
\end{pmatrix}
\overset{l_1'=l_1-2l_2}{\longrightarrow}
\begin{pmatrix}
1 & 2 & 0 & -2 &\bigm| 1\\
0 & 0 & 1 & 2 &\bigm| 0\\
0 & 0 & 0 & 0 &\bigm| 0
\end{pmatrix}
\end{align}
\tag{10}\]
We simplified it as much as we can, going back to the system’s notation we have:
\[ \begin{cases} x + 2 y & &- &2w &=1\\ &z &+ &2w &=0 \end{cases} \]
Now, promote \(y\) and \(w\) into parameters and express \(x\) and \(z\) in term of them:
\[ \begin{cases} x + 2 y & &- &2w &=1\\ &z &+ &2w &=0 \end{cases} \longrightarrow \begin{cases} x &=1-2y&-&2w\\ z &=&-&2w \end{cases} \tag{11}\]
For each values we assign to \(y\) and \(w\) we get one solution! There’s an infinite number of them.
This example is given so that you can see, that the final aesthetic of the reduced \(A'\) may have the \(I\) and \(F\) blocks mixed!
This is also a matrix with form:
\[ \begin{pmatrix}I \,\,F\end{pmatrix} \]
The rank is \(r=2\), the rank of the extended matrix is \(r^*=2\), meanwhile \(n=4\). Since \(r=r^*<n\) we have an infinite number of solutions.
Example 5: A system that may have one, none or many solutions
What is the solution of:
\[ \begin{cases} &x&+ &k y&+&2 z &= 1\\ &x&+&y&+&(k+1)z &= k\\ &-x&-&y&-&z &=k+1 \end{cases} \]
Using the extended matrix formulation we use the pivots to eliminate entries:
\[ \begin{align} &\begin{pmatrix} 1 & k & 2 &\bigm|1\\ 1 & 1 & k+1 &\bigm|k\\ -1 & -1 & -1 &\bigm| k+1 \end{pmatrix} \overset{l_2' = l_2-l_1\\l_3'=l_3+l_1}{\longrightarrow} \begin{pmatrix} 1 & k & 2 &\bigm| 1\\ 0 & 1-k & k-1 &\bigm| k-1\\ 0 & k-1 & 1 &\bigm| k+2 \end{pmatrix} \overset{l_3' = l_3+l_2}{\longrightarrow} \begin{pmatrix} 1 & k & 2 &\bigm| 1\\ 0 & 1-k & k-1 &\bigm| k-1\\ 0 & 0 & k &\bigm| 2k+1 \end{pmatrix} \end{align} \]
Now, depending upon on the value \(k\) the system may have one, none or many solutions:
- For \(k=1\) then
\[ \begin{pmatrix} 1 & 1 & 2 &\bigm|1\\ 0 & 0 & 0 &\bigm|0\\ 0 & 0 & 1 &\bigm| 3 \end{pmatrix} \overset{l_2 \leftrightarrow l_3}{\longrightarrow} \begin{pmatrix} 1 & 1 & 2 &\bigm|1\\ 0 & 0 & 1 &\bigm|3\\ 0 & 0 & 0 &\bigm| 0 \end{pmatrix}\overset{l_1'=l_1-2l_2 }{\longrightarrow}\begin{pmatrix} 1 & 1 & 0 &\bigm|-5\\ 0 & 0 & 1 &\bigm|3\\ 0 & 0 & 0 &\bigm| 0 \end{pmatrix} \tag{12}\]
which has the form:
\[ \begin{pmatrix}I\,\,F \end{pmatrix} \]
and: \(r=2\), \(r^*=2\) and \(n=3\).
Since \(r=r^*<n\) we conclude we have an infinite number of solutions as we readily check by actually computing them. From Equation 12 we know:
\[ \begin{cases} x + y = -5\\ z=3 \end{cases} \]
Since we have two equations and three unknowns, we promote one of them, let it be \(x\), to the status of a parameter \(x_0\), hence:
\[ \begin{pmatrix}x\\y\\z\end{pmatrix}=\begin{pmatrix}x_0\\-5-x_0\\3\end{pmatrix}=\begin{pmatrix}0\\-5\\3\end{pmatrix}+x_0\begin{pmatrix}1\\-1\\0\end{pmatrix} \]
For each \(x_0\) of our choice we have a distinct solution. There is infinite of them.
- For \(k=0\)
\[ \begin{pmatrix} 1 & 0 & 2 &\bigm|1\\ 0 & 1 & -1 &\bigm|-1\\ 0 & 0 & 0 &\bigm| 1 \end{pmatrix} \]
The system has the form:
\[ \begin{pmatrix} I & F\\ \mathbf{0} &\mathbf{0} \end{pmatrix} \]
And note: \(r=2\), \(r^*=3\) and \(n=3\), thus \(r<r^*=n\) which tells us there is no solution. In fact we can see why by rolling back to:
\[ \begin{cases} x+2z=1\\ y-z =-1\\ 0=1 \end{cases} \]
There are no \(x\), \(y\) and \(z\) that satisfies these three equations simultaneously.
- If \(k\) is not \(0,1\) then we always have \(r=r^*=n\), thus, there is always a unique solution.
In summary:
A system of equations \(A\mathbf{x}=\mathbf{b}\) have infinite solutions provided \(r=r^*<n\).
A system of equations \(A\mathbf{x}=\mathbf{b}\) have one solution provided \(r=r^*=n\).
A system of equations \(A\mathbf{x}=\mathbf{b}\) have no solutions provided \(r<r^*\).
For the moment assume this summary as a fact of life, later we’ll justify in detail the meaning of this triple equality, for know just focus on learning elimination and testing the triple equality
How do we know how many pivots are there? Use elimination method to introduce in the matrix as many zeros as possible, giving us the reduced form \(A'\). Counting the pivots in \(A'\) is easy. Recall that the number of pivots of \(A\) is the same as \(A'\).
A matrix where all entries below the pivots were killed is in triangular form. Back substitution can already be used at this stage. (we did not do this in the examples, but we could) If we proceed and also kill all entries above the pivots, we get the best matrix (this is what we did in the examples above). A matrix is then said to be in reduced row echelon form. Back substitution can also used at this final stage.