# Linear Algebra - Gaussian Elimination

I have an augmented coefficient matrix $$\left[\begin{array}{cccc|c} 1 & 0 & 1 & -3 & 0\\ 0 & 1 & -1 & -1 & -4 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right].$$ I got this using gaussian elimination. However now I'm stuck because I don't know how to find the answer to the unknown variables $a,b,c,d$ because I can't make it so there's only one 1 per row...

-

Perhaps it's easier to see what's going on if you now rewrite the the augmented matrix as a system of linear equations. I'll use $x_1,x_2,x_3$, and $x_4$ as variables. Your augmented matrix then corresponds to the system

\left\{\begin{align*} &x_1+x_3-3x_4=0\\ &x_2-x_3-x_4=-4\\ &0=0\;, \end{align*}\right.

which in turn is equivalent to

\left\{\begin{align*} &x_1=-x_3+3x_4\\ &x_2=-4+x_3+x_4\;. \end{align*}\right.

You can substitute any values whatever for $x_3$ and $x_4$, but once you've specified them, $x_1$ and $x_2$ are completely determined. For instance, if you set $x_3=1$ and $x_4=3$, then $x_1=-1+3\cdot4=11$ and $x_2=-4+1+3=0$.

You can express the same information in matrix form like this:

$$\begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix}=\begin{bmatrix}-x_3+3x_4\\-4+x_3+x_4\\x_3\\x_4\end{bmatrix}=\begin{bmatrix}0\\-4\\0\\0\end{bmatrix}+x_3\begin{bmatrix}-1\\1\\1\\0\end{bmatrix}+x_4\begin{bmatrix}3\\1\\0\\0\end{bmatrix}\;.$$

And now you have your answer: the set of solutions to the original system of equations that led to your augmented matrix is the set of all vectors of the form

$$\begin{bmatrix}0\\-4\\0\\0\end{bmatrix}+x_3\begin{bmatrix}-1\\1\\1\\0\end{bmatrix}+x_4\begin{bmatrix}3\\1\\0\\0\end{bmatrix},\qquad x_3,x_4\in\Bbb R\;.\tag{1}$$

After you've reduced the augmented matrix, you'll always have some columns that are unit vectors; in this problem those are the first two columns. You may have some columns that aren't unit vectors, columns that you weren't able to reduce; in this problem those are the last two columns. The variables for the unreduced columns, if there are any, can always be chosen to be anything you like, and the variables for the unit vector columns can then be solved for in terms of the others, just as I did here.

If there are no unreduced columns the system has a unique solution; you probably don't have any real difficulty with this case.

There is one more thing to watch out for: a row that's all zeroes, such as you got in this problem, is fine, but a row that's all zeroes except for the augmentation element corresponds to an equation of the form $0=c$, where $c\ne 0$; this is impossible and indicates that the original system is inconsistent and therefore has no solution.

With practice you can develop the ability to go directly from the matrix to an answer in the form $(1)$, but if you're just beginning, you may want to go through the intermediate steps as I've shown them.

-

Since the last row is a zero row, there are infinitely many solutions. To find them, you may:

$\ \ \$1) Identify the non-pivot columns of the coefficient part of the reduced matrix. These are the columns that do not contain a leading row entry. Here, they are columns three and four. These correspond to the variables, presumably, $c$ and $d$.

$\ \ \$2) Give $c$ and $d$ arbitrary values: say, $c=s$ and $d=t$. Here, $s$ and $t$ will be the parameters of your solution space.

$\ \ \$3) Use row 2 to write $b$ in terms of $c$ and $d$, and then in terms of $s$ and $t$: $$b-c-d=-4\quad\iff\quad b=-4+c+d\quad\iff\quad b=-4+s+t.$$

$\ \ \$4) Use row 1 to write $a$ in terms of $b$, $c$, and $d$, and then in terms of $s$ and $t$: $$a+c-3d=0\quad\iff\quad a= -c+3d\quad\iff\quad a=-s+3t.$$

So the solutions are described by \eqalign{ a&=-s+3t\cr b&=-4+s+t\cr c&=s\cr d&=t } Giving $s$ and $t$ particular values will give you a solution of the system. For instance taking $s=1$ and $t=2$ gives the solution $a=5$, $b=-1$, $c=1$, $d=2$.

-
Of course for a consistent system of three equations in four unknowns, there would be infinitely many solutions even if the last row were not a zero row... – Will Orrick May 2 '12 at 19:12

There are two free variables : c and d , and the other two variables a and b you can get them from the equations you got after getting the echelon form : b=c+d-4. Go to the first equation: a=-c+3d. (for each value that c and d take you get the correspond values of a and b, then the set of solutions is infinite).

-