1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ This seems to require us to solve the system in order to say something, which is possible here but can be burdensome in more complicated cases. Is there a way that does not require us to solve the system? Is it sufficient to just check if the echelon form has a zero row? $\endgroup$
    – TEX
    Feb 5, 2021 at 15:30
  • 1
    $\begingroup$ A zero column. I think. Trying to construct one now... $\endgroup$ Feb 5, 2021 at 15:35
  • 1
    $\begingroup$ There is very little difference between solving the system and finding a row echelon form: compared to the row reduction process which gets you from the original augmented matrix to the row echelon form, getting from row echelon form to the solution happens in an instant. $\endgroup$
    – Lee Mosher
    Feb 5, 2021 at 15:49
  • 1
    $\begingroup$ Turns out I was wrong, it's not that either. I tried creating one where one variable must be fixed, writing what i found out now. $\endgroup$ Feb 5, 2021 at 16:27
  • 1
    $\begingroup$ First one is true. Second is ...true but feels like you're putting too much primacy on the order of variables $\endgroup$ Feb 5, 2021 at 19:01
-1
$\begingroup$

It depends on the rang of the row echelon matrix , say the rang of the row echelon matrix matches the dimension of the $x$ vecotr in your case, then you cannnot choose any of the $x_1,x_2\ldots x_n $ as free variables. In case 2 you can choose either $x_1$ or $x_2$ as a free variable , lets say $t\in \mathbb{R}$ and calculate the rest accordingly. The amount of free varibales you can chosse is given by '$rows(x)-rang(A)$'. The varibale you choose to be free is up to you.

$\endgroup$
3
  • $\begingroup$ This is wrong. In case 2, I can only set $x_1$ as free variable because $x_2=5$. $\endgroup$
    – TEX
    Feb 5, 2021 at 15:07
  • $\begingroup$ Yes you are right i missed the zeros on the matrix $\endgroup$
    – y_andoni
    Feb 5, 2021 at 15:11
  • $\begingroup$ well in the second case you may aswell discard the row with 0 as it holds for all $x_1,x_2$ so you need only look at the rows that has at least a non zero component in that case you can easily see which one of the $x_1,x_2$ can be freely chosen. $\endgroup$
    – y_andoni
    Feb 5, 2021 at 15:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.