12.2: Systems of Linear Equations with Many Solutions

When we solve a system of equations of the form \(Ax=b\), we mentioned that we may have three outcomes:

• a unique solution
• no solution
• infinity many solutions

Assume that we have \(m\) equations and \(n\) unknowns.

• Case 1 \(m<n\), we do not have enough equations, there will be only TWO outcomes: no solution, or infinity many solutions.
• Case 2 \(m=n\), we may have all THREE outcomes. If the determinant is nonzero, we have a unique solution, otherwise, we have to decide the outcome based on the augmented matrix.
• Case 3 \(m>n\), we have more equations than the number of unknowns. That means there will be redundant equations (we can remove them) or conflict equations (no solution). We may have all THREE outcomes.

We talked about several methods for solving the system of equations. The most general one is the Gauss-Jordan or Gaussian elimination, which works for all three cases. Note that Jacobian and Gauss-Seidel can not work on Case 1 and Case 3.

We will focus on the Gaussian elimination. After the Gaussian elimiation, we look at the last several rows (could be zero) with all zeros except the last column.

If one element from the corresponding right hand side is not zero, we have that 0 equals some nonzero number, which is impossible. Therefore, there is no solution. E.g.,

\[\begin{split}\left[
\begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 0
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 3 \\ 4 \\ 5
\end{matrix}
\right]
\end{split} \nonumber \]

In this case, we say that the system is inconsistent. Later in the semester we will look into methods that try to find a “good enough” solution for an inconsistant system (regression).

Otherwise, we remove all the rows with all zeros (which is the same as removing redundant equations). If the number of remaining equations is the same as the number of unknowns, the rref is an identity matrix, and we have unique solution. E.g.,

\[\left[
\begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
0 & 0 & 0
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 3 \\ 4 \\ 0
\end{matrix}
\right]
\Rightarrow \left[
\begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 3 \\ 4
\end{matrix}
\right] \nonumber \]

If the number of remaining equations is less than the number of unknowns, we have infinitely many solutions. Consider the following three examples:

\[\begin{split}\left[
\begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 0
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 3 \\ 0
\end{matrix}
\right]
\Rightarrow \left[
\begin{matrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 3
\end{matrix}
\right] \Rightarrow x= [2, 3, x_3]^\top \end{split} \nonumber \]

where \(x_3\) is a free variable.

\[\begin{split}\left[
\begin{matrix}
1 & 2 & 0 \\
0 & 0 & 1 \\
0 & 0 & 0
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 3 \\ 0
\end{matrix}
\right]
\Rightarrow \left[
\begin{matrix}
1 & 2 & 0 \\
0 & 0 & 1 \\
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 3
\end{matrix}
\right] \Rightarrow x= [2-2x_2, x_2, 3]\end{split} \nonumber \]

where \(x_2\) is a free variable.

\[\begin{split}\left[
\begin{matrix}
1 & 2 & 0 & 1 \\
0 & 0 & 1 & 3 \\
0 & 0 & 0 & 0
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 5 \\ 0
\end{matrix}
\right]
\Rightarrow \left[
\begin{matrix}
1 & 2 & 0 & 1 \\
0 & 0 & 1 & 3 \\
\end{matrix}
\, \middle\vert \,
\begin{matrix}
2 \\ 5
\end{matrix}
\right] \Rightarrow x= [2-2x_2-x_4, x_2, 5-3x_4, x_4]\end{split} \nonumber \]

where \(x_2\) and \(x_4\) are free variables.

Question

Assume that the system is consistent, explain why the number of equations can not be larger than the number of unknowns after the redundant equations are removed?

Do This

If there are two solutions for \(Ax=b\), that is \(Ax=b\) and \(Ax'=b\) while \(x \neq x'\). Check that \(A(cx+(1-c)x')=b\) for any real number \(c\). Therefore, if we have two different solutions, we have infinite many solutions.

If \(Ax=b\) and \(Ax′=b\), then we have \(A(x−x′)=0\). If \(x\) is a particular solution to \(Ax=b\), then all the solutions to \(Ax=b\) are \(\{x+v: v \mbox{ is a solution to the homogeneous system } Av=0\}\).

The solution for \(Ax=0\) is always a subspace.

After removing the redundant rows, if the number of equations is the same as the number of unknowns, we have a unique solution. If the difference between the number of equations and the number of unknowns is 1, all the solutions lie on a line. If the difference is 2, all the solutions lie on a 2-D plane.

Question

What is the solution to the following set of linear equations in augmented matrix form?

\[\begin{split}A =
\left[
\begin{matrix}
-2 & 4 & 8 \\
1 & -2 & 4 \\
4 & -8 & 16
\end{matrix}
\, \middle\vert \,
\begin{matrix}
0 \\ 0 \\ 0
\end{matrix}
\right]
\end{split} \nonumber \]