Section 1.5 Existence of Solutions
Recall that any linear system may be expressed as a matrix equation of the form
\(A\vb{x} = \vb{b}\text{.}\) Furthermore, this system is consistent if and only if the last column of the augmented matrix
\(\mqty[A \amp \bb]\) is
not a pivot column. Based on this and our observations in
Section 1.4, we can make the following observations.
Theorem 1.5.1. Consistency, Rank and the Column Space.
Let \(A\) be an \(m\times n\) matrix, \(\vb{x}\in\RR^{n}\) and \(\vb{b}\in\RR^{m}\text{.}\) The linear system \(A\vb{x} = \vb{b}\) is consistent if and only if \(\vb{b}\in\col{A}\text{.}\) Equivalently, the system is consistent if and only if \(\rank{A} = \rank{\mqty[A & \vb{b}]}\text{.}\) Furthermore, the system has precisely one solution if \(\rank{A} = \rank{\mqty[A & \vb{b}]} = n\) and has infinitely many solutions if \(\rank{A} = \rank{\mqty[A & \vb{b}]} \lt n\text{.}\)
As before, we use Gaussian elimination (i.e., row reduction) to solve systems.
Example 1.5.2.
Find any solutions of
\begin{align*}
5x - 7y + 3z &= 17\\
-15x + 20y - 9z &= -50
\end{align*}
Solution.
Reducing to an echelon form is enough to determine if the system is consistent and find the number of solutions it has. Using Octave to find the reduced echelon form (see the code cell immediately after this example), we get
\begin{equation*}
\begin{bmatrix} 1 & 0 & \frac{3}{5} & 2 \\ 0 & 1 & 0 & -1\end{bmatrix}.
\end{equation*}
From the reduced echelon form above, we see that the system must be consistent since the rank of the coefficient matrix is equal to the rank of the augmented matrix. Equivalently, the last column is not a pivot column. Furthermore, there are infinitely many solutions since the rank of the coefficient matrix is less than the total number of columns.
The solution set itself can be written in vector notation as
\begin{equation*}
\begin{bmatrix}x \\ y \\ z\end{bmatrix} = \begin{bmatrix}2 \\ -1 \\ 0\end{bmatrix} + z\begin{bmatrix}-\frac{3}{5} \\ 0 \\ 1\end{bmatrix}.
\end{equation*}
This, again, is verified below.
In the last example the variable \(z\) led to infinitely many solutions and we were able to write out solution depending on the value of this variable. We call \(z\) a free variable and \(x\) and \(y\) basic variables.
Definition 1.5.3. Basic and Free Variables.
Given a consistent linear system \(A\vb{x}=\vb{b}\text{,}\) the variables corresponding to pivot columns of \(A\) are basic variables and the variables corresponding to non-pivot columns of \(A\) are free variables.
Any solution of the linear system
\(A\vb{x} = \vb{b}\) can always be written to depend solely on any free variables as we did in
Example 1.5.2. In fact we can go a bit further, still using our answer in
Example 1.5.2 as a guide. Using free variables, any solution to
\(A\vb{x}=\vb{b}\) can be written as a sum of two components:
\begin{equation*}
\vb{x} = \vb{x}_p + \vb{x}_{\text{free}}.
\end{equation*}
This notation will change shortly, but the main idea is that one component of the solution will not depend on the free variable and will represent a single solution of the system
\(A\vb{x} = \vb{b}\text{.}\) In
Example 1.5.2 this would be
\begin{equation*}
\vb{x}_{p} = \mqty[2\\-1\\0],
\end{equation*}
and it's easy to verify that
\begin{equation*}
A\vb{x}_{p} = \mqty[5 & -7 & 3 \\ -15 & 20 & -9]\mqty[2\\-1\\0] = \mqty[17\\-50].
\end{equation*}
The
other component of the solution,
\(\vb{x}_{\text{free}}\text{,}\) will depend on the free variable. In
Example 1.5.2, this component was
\begin{equation*}
\vb{x}_{\text{free}} = z\mqty[-\frac{3}{5} \\ 0 \\ 1].
\end{equation*}
As it turns out, this component is not a solution of the original system \(A\vb{x} = \vb{b}\text{.}\) Instead, \(A\vb{x}_{\text{free}} = \vb{0}\text{.}\) This behavior is shared by all consistent systems with free variables, and leads us to introduce the following terminology.
Definition 1.5.4. Associated Homogeneous System.
Given a linear system \(A\vb{x} = \vb{b}\text{,}\) we define the associated homogeneous system to be the system \(A\vb{x} = \vb{0}\text{.}\)
The observations made after
Example 1.5.2 can be summarized in the following theorem.
Theorem 1.5.5. Particular and Homogeneous Solutions.
Suppose that \(A\vb{x} = \vb{b}\) is a consistent linear system. Then the general solution \(\vb{x}\) can be written in the form \(\vb{x} = \vb{x}_{p} + \vb{x}_{h}\) where \(\vb{x}_{p}\) is a single solution of the original system \(A\vb{x} = \vb{b}\) and \(\vb{x}_{h}\) is the general solution of the associated homogeneous system \(A\vb{x} = \vb{0}\text{.}\) We call \(\vb{x}_{p}\) a particular solution.
Proof.
Here, we only prove that \(\vb{x}_{h}\) satisfies the associated homogeneous system. Since \(\vb{x}_{p}\) is a solution of the original system along with \(\vb{x} = \vb{x}_{p} + \vb{x}_{h}\text{,}\) it follows that
\begin{equation*}
A\vb{x}_{h} = A(\vb{x}-x_{p}) = \vb{b} - \vb{b} = \vb{0}.
\end{equation*}
Therefore \(\vb{x}_{h}\) is a solution of the associated homogeneous system.
Since solutions of homogeneous systems play such an important role in the solution of non-homogeneous systems, we give their solution sets a special name.
Definition 1.5.6. Null Space.
Let \(A\) be a matrix. The null space of \(A\) is the set of all solutions of \(A\vb{x} = \vb{0}\text{.}\) This is denoted by \(\nul{A}\text{.}\)
As with column spaces and row spaces, null spaces are always subspaces.
Theorem 1.5.7. The Null Space is a Subspace.
Let \(A\) be an \(m\times n\) matrix. Then \(\nul{A}\) is a subspace of \(\RR^n\text{.}\)
Proof.
To show that \(\nul{A}\) is a subspace we need to show that it's closed under linear combinations. So let \(\vb{u},\vb{v}\in\nul{A}\) be arbitrary vectors in the null space and let \(\alpha,\beta\in\RR\) be arbitrary scalars. Our goal is to show that \(\alpha\vb{u} + \beta\vb{v}\in\nul{A}\text{.}\) Thankfully, we can do this very quickly:
\begin{align*}
A(\alpha\vb{u} + \beta\vb{v}) &= \alpha A\vb{u} + \beta A\vb{v}\\
&= \vb{0} + \vb{0} \\
&= \vb{0},
\end{align*}
which shows that the linear combination \(\alpha\vb{u}+\beta\vb{v}\) lies in \(\nul{A}\text{.}\)
The concept of the null space is related to that of the column space in
Definition 1.4.8, but they are distinct. To be precise, if
\(A\) is an
\(m\times n\) matrix then
\begin{align*}
\col{A} &= \qty{A\vb{x} : \vb{x}\in\RR^n} \subseteq \RR^{m} \\
\nul{A} &= \qty{\vb{x} : A\vb{x} = \vb{0}} \subseteq \RR^{n}
\end{align*}
Example 1.5.8. Finding a Null Space.
Let
\begin{equation*}
A = \mqty[0 & 5 & 5 & -10 & 0 \\ 2 & -3 & -3 & 6 & 2 \\ 4 & 1 & 1 & -2 & 4].
\end{equation*}
Find \(\nul{A}\text{.}\)
Solution.
We need to find the solution set of \(A\vb{x} = \vb{0}\) which we've done before. The Octave code cell below can be used to solve this system, giving the reduced echelon form for the augmented matrix \(\mqty[A & \vb{0}]\) to be
\begin{equation*}
\mqty[1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & -2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0].
\end{equation*}
Therefore any solution \(\vb{x}\in\RR^5\) of \(A\vb{x}=\vb{0}\) must look like
\begin{equation*}
\vb{x} = \mqty[x_1\\x_2\\x_3\\x_4\\x_5] = \mqty[-x_5\\-x_3+2x_4\\x_3\\x_4\\x_5] = x_3\mqty[0\\-1\\1\\0\\0] + x_4\mqty[0\\2\\0\\1\\0] + x_5\mqty[-1\\0\\0\\0\\1].
\end{equation*}
Note that the above shows that
\begin{equation*}
\nul{A} = \spn{\qty{\mqty[0\\-1\\1\\0\\0], \mqty[0\\2\\0\\1\\0], \mqty[-1\\0\\0\\0\\1]}}
\end{equation*}
Since these vectors are also linearly independent, it follows that the set
\begin{equation*}
\qty{\mqty[0\\-1\\1\\0\\0], \mqty[0\\2\\0\\1\\0], \mqty[-1\\0\\0\\0\\1]}
\end{equation*}
is in fact a basis for \(\nul{A}\) and \(\dim{\nul{A}} = 3\text{.}\)
At this point we can make a simple but useful observation. In
Example 1.5.8, the dimension of the null space was directly tied to the number of free variables in the system
\(A\vb{x} = \vb{0}\text{.}\) The number of basic variables is likewise equal to the number of pivot columns of
\(A\text{.}\) Noting that the number of basic variables plus the number of free variables must be the total number of columns of
\(A\text{,}\) together with
Theorem 1.4.6, we get the
Rank-Nullity Theorem.
Theorem 1.5.9. Rank-Nullity Theorem.
Let \(A\) be an \(m\times n\) matrix. Then
\begin{equation*}
\rank{A} + \dim\nul{A} = n.
\end{equation*}
