Consider the following two linear system of equations of the form $b=Ax$
case 1:
$$
\begin{pmatrix}
4\\
5
\end{pmatrix}= \begin{pmatrix}
1& 2 & -1\\
2 & -4 & 0
\end{pmatrix}\begin{pmatrix}
x_1\\
x_2\\
x_3
\end{pmatrix}
$$
case 2:
$$
\begin{pmatrix}
0\\
5
\end{pmatrix}= \begin{pmatrix}
0 & 0\\
0 & 1
\end{pmatrix}\begin{pmatrix}
x_1\\
x_2\\
\end{pmatrix}
$$
The reduced row echelon form of case 1 is
$$
\begin{pmatrix}
1 & 0 & -0.5 & 3.25\\
0 & 1 & -0.25 & 0.3750
\end{pmatrix}
$$
Hence, $x_1,x_2$ are basic variables, $x_3$ is free variable.
The reduced row echelon form of case 2 is
$$
\begin{pmatrix}
0 & 1 & 5\\
0 & 0 & 0
\end{pmatrix}
$$
Hence, $x_2$ is basic variable, $x_1$ is free variable.
Question: There is a key difference between case 1 and case 2.
In case 1, I am free to decide which two variables among $\{x_1,x_2,x_3\}$ are set as basic and which one is set as free. The reduced row echelon suggests to set $x_1,x_2$ as basic variables and $x_3$ as free. However, I could equivalently set $x_1,x_3$ as basic variables and $x_2$ as free. Or, I could also set $x_3,x_2$ as basic variables and $x_1$ as free. This can be seen by doing naive calculations from the system of equations.
In case 2, I am not free to decide which variable between $\{x_1,x_2\}$ should be set as basic and which one should be set as free. Again, this can be seen by doing naive calculations from the system of equations.
More generally (and for more complicated systems) I am wondering whether there is an easy way to detect when I am (not) free in setting the free/basic variables from just looking at the reduced row echelon, without the need of doing other calculations. Is this a matter of zero rows or is there something more subtle?
Best Answer
In these sort of cases, the solution is a line or plane or something similar, embedded within the input space. When describing this solution we can choose any variable that is not orthogonal to it as a free variable, and then once we have enough to fully describe a projection of the solution with the same number of dimensions, we can say any other variables we would need to get back to the solution set have you are "basic", forced by the selection of free variables to take on a particular value.
In case 1, the solution is $x = (\frac{109}{42}, \frac{1}{21}, -\frac{55}{42}) + (2,1,4)t$, and since none of $(1,0,0)$, $(0,1,0)$, and $(0,0,1)$ are orthogonal to $2,1,4$, we can pick any one of $x_1$, $x_2$, and $x_3$ to be the free variable.
In case 2, the solution can be described as the line $x = (0,5) + (1,0)t$, where it is obvious that $(0,1)$ is orthogonal to the solution line, and so $x_2$ cannot be considered free.
I've done a bit of searching to figure out how to detect this in the RREF. here's an example.
$$ \begin{pmatrix} 1\\ 4 \end{pmatrix}= \begin{pmatrix} 4& -6 & 3\\ -2 & 3 & 4 \end{pmatrix}\begin{pmatrix} x_1\\ x_2\\ x_3 \end{pmatrix} $$
This has RREF
$$ \left(\begin{array}{ccc|c} 1 & -\frac{3}{2} & 0 & -\frac{4}{11}\\ 0 & 0 & 1 & \frac{9}{11} \end{array}\right) $$
And it turns out that $x_3 = \frac{9}{11}$ all the time. The solution set is $(-\frac{2}{11}, \frac{4}{33}, \frac{9}{11}) + (2,3,0)t$; this is clearly orthogonal to $(0,0,1)$ and so $x_3$ is fixed.
This provides guidance to the answer The second row of the RREF contains only columns from $x_3$ and the solution vector, so this one must be fixed; I can select from $x_1$ and $x_2$ to be free because they share a row.
Applying this wisdom to case 1: selecting one of $x_1$ or $x_2$ to be free fixes $x_3$ by the action of one of the rows, which then (since everything else in the other row is fixed) fixes the other one, and picking $x_3$ to be free fixes $x_1$ and $x_2$ by the respective actions of the two rows in themselves.
Applying similar wisdom to case 2: $x_1$ gets to be free because it affects absolutely nothing; $x_2$ does not because it is surrounded by already-fixed results.
So it looks like it goes something like this: if a variable is in a position in one of the rows where it can affect only variables that are either fixed or already chosen as free, then it must be fixed. Otherwise, you may choose it to be free.