8.3: Underdetermined Systems

Sometimes we have systems of linear equations where we have more unknowns than equations, in this case we call the system “underdetermined.” These types of systems can have infinite solutions. i.e., we can not find an unique \(x\) such that \(Ax = b\). In this case, we can find a set of equations that represent all of the solutions that solve the problem by using Gauss Jordan and the Reduced Row Echelon form. Lets consider the following example:

\[ \begin{split}\begin{bmatrix}5 & -2 & 2 & 1 \\ 4 & -3 & 4 & 2 \\ 4 & -6 & 7 & 4 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}\end{split} \nonumber \]

Question

Define an augmented matrix \(M\) that represents the above system of equations:

#Put your code here

Question

What is the Reduced Row Echelon form for A?

from answercheck import checkanswer

checkanswer.matrix(M,'efb9b2da0e44984a18f595d7892980e2');

# Put your answer to the above question here

from answercheck import checkanswer

checkanswer.matrix(RREF,'f1fa8baac1df4c378db20cff9e91ca5b');

Notice how the above RREF form of matrix A is different from what we have seen in the past. In this case not all of our values for \(x\) are unique. When we write down a solution to this problem by defining the variables by one or more of the undefined variables. for example, here we can see that \(x_4\) is undefined. So we say \(x_4=x_4\), i.e. \(x_4\) can be any number we want. Then we can define \(x_3\) in terms of \(x_4\). In this case \(x_3 = \frac{11}{15} - \frac{4}{15}x_4\). The entire solution can be written out as follows:

\[\begin{split}
\begin{align*}
x_1 &= \frac{1}{15} + \frac{1}{15}x_4 \\
x_2 &= \frac{2}{5} + \frac{2}{5}x_4 \\
x_3 &= \frac{11}{15} - \frac{4}{15}x_4 \\
x_4 &= x_4
\end{align*}
\end{split} \nonumber \]

Do This

Review the above answer and make sure you understand how we get this answer from the Reduced Row Echelon form from above.

Sometimes, in an effort to make the solution more clear, we introduce new variables (typically, \(r\),\(s\),\(t\)) and substitute them in for our undefined variables so the solution would look like the following:

\[\begin{split}
\begin{align*}
x_1 &= \frac{1}{15} + \frac{1}{15}r \\
x_2 &= \frac{2}{5} + \frac{2}{5}r \\
x_3 &= \frac{11}{15} - \frac{4}{15}r \\
x_4 &= r
\end{align*}
\end{split} \nonumber \]

We can find a particular solution to the above problem by inputing any number for \(r\). For example, set \(r\) equal to zero and create a vector for all of the \(x\) values.

\[\begin{split}
\begin{align*}
x_1 &= \frac{1}{15}\\
x_2 &= \frac{2}{5}\\
x_3 &= \frac{11}{15} \\
x_4 &= 0
\end{align*}
\end{split} \nonumber \]

##here is the same basic math in python
import numpy as np
r = 0
x = np.matrix([1/15+1/15*r, 2/5+2/5*r, 11/15-4/15*r, r]).T
x

Do This

Define two more matrixes \(A\), \(b\) representing the above system of equations \(Ax=b\):

# put your answer to the above question here.

from urllib.request import urlretrieve

urlretrieve('https://raw.githubusercontent.com/colbrydi/jupytercheck/master/answercheck.py', 
            'answercheck.py');

from answercheck import checkanswer

checkanswer.matrix(A,'a600d0416a3fb9b4bde87b08caf068f1');

from answercheck import checkanswer

checkanswer.vector(b,'4cfaa788e4dd6de04fdf6aea4a0e0e71');

Now let us check our answer by multipying matrix \(A\) by our solution \(x\) and see if we get \(b\)

np.allclose(A*x,b)

Do This

Now go back and pick a different value for \(r\) and see that it also produces a valid solution for \(Ax=b\).