# Guassian Elimination with matrices

I am struggling with Gaussian elimination with matrices. I need to bring the following matrix

$$\left[\begin{array}{cccc|c} 1&-1&2&1 & 2\\ 2&-3&2&0 & 3\\ -1&1&2&3 & 6\\ -3&2&0&3 & 9\\ \end{array}\right]$$

The matrix after the = sign is supposed to be augmented wth the first matrix but I as unable to do the proper formatting.

I know the final answer is

$\begin{bmatrix} 1&0&0&-1 \\0&1&0&0 \\0&0&1&1 \\0&0&0&0 \end{bmatrix}=\begin{bmatrix}-5\\-3\\2\\0\end{bmatrix}$

The question asked if the columns of A are linearly independent. I am looking for some help with walking through the steps of reduction and whether or not this matrix needs to be in reduced row echelon form or just row echelon form. I know to bring this to row echelon form you can only swap rows, add/subtract rows, and multiply rows by scalars, or add/subtract rows when multiplied by scalers

• just looking for some basic strategies for guassian elimination – jh123 Oct 15 '16 at 14:12
• @ Rodrigo de Azevedo thanks for the edit, – jh123 Oct 15 '16 at 14:22

Let's walk through elimination: \begin{align} \left[ \begin{array}{cccc|c} 1 & -1 & 2 & 1 & 2\\ 2 & -3 & 2 & 0 & 3\\ -1 & 1 & 2 & 3 & 6\\ -3 & 2 & 0 & 3 & 9 \end{array}\right] &\to \left[ \begin{array}{cccc|c} 1 & -1 & 2 & 1 & 2 \\ 0 & -1 & -2 & -2 & -1 \\ 0 & 0 & 4 & 4 & 8 \\ 0 & -1 & 6 & 6 & 15 \end{array}\right] &&\begin{aligned} R_2&\gets R_2-2R_1\\R_3&\gets R_3+R_1\\R_4&\gets R_4+3R_1\end{aligned} \tag{1}\\[6px]&\to \left[ \begin{array}{cccc|c} 1 & -1 & 2 & 1 & 2 \\ 0 & 1 & 2 & 2 & 1 \\ 0 & 0 & 4 & 4 & 8 \\ 0 & 1 & 8 & 8 & 16 \end{array}\right] &&\begin{aligned} R_2&\gets -R_2\\R_4&\gets R_4+R_2\end{aligned} \tag{2}\\[6px]&\to \left[ \begin{array}{cccc|c} 1 & -1 & 2 & 1 & 2 \\ 0 & 1 & 2 & 2 & 1 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right] &&\begin{aligned} R_3&\gets \tfrac{1}{4}R_3\\R_4&\gets R_4-8R_3\end{aligned} \tag{3}\\[6px]&\to \left[ \begin{array}{cccc|c} 1 & -1 & 0 & -1 & -2 \\ 0 & 1 & 0 & 0 & -3 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right] &&\begin{aligned}R_2&\gets R_2-2R_3\\R_1&\gets R_1-2R_3\end{aligned} \tag{4}\\[6px]&\to \left[ \begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5 \\ 0 & 1 & 0 & 0 & -3 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right] &&R_1\gets R_1+R_2 \tag{5} \end{align}

Already after step $(3)$ you can conclude that the columns of the matrix $A$ are linearly dependent, because you get a null row in a row echelon form (just consider the first four columns); the fact that you get a full null row in the augmented matrix tells you that the linear system is solvable, because the last column cannot contain a leading $1$.

Steps $(4)$ and $(5)$ are backwards elimination, that lead to the reduced row echelon form, very useful to easily express all solutions.

Indeed, if we denote by $x_1$, $x_2$, $x_3$ and $x_4$ the unknowns, we see that $x_4$ is free and the equations read $$\begin{cases} x_1-x_4=-5 \\[4px] x_2 = -3 \\[4px] x_3+x_4=2 \end{cases}$$ so the generic solution is $$\begin{bmatrix} -5+h\\ -3\\ 2-h\\ h \end{bmatrix}$$

The advantage to go into this order for elimination is that it makes it possible to write the $LU$ decomposition of the matrix $A$. I use to denote the elementary operations we have performed up to step $(3)$ as $$E_{21}(-2),\quad E_{31}(1),\quad E_{41}(3),\quad E_2(-1),\quad E_{42}(1),\quad E_3(\tfrac{1}{4}),\quad E_{43}(-8)$$ and this allows to write $$L=E_{21}(2)E_{31}(-1)E_{41}(-3)E_2(-1)E_{42}(-1)E_3(4)E_{43}(8) =\begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & -1 & 0 & 0 \\ -1 & 0 & 4 & 0 \\ -3 & -1 & 8 & 1 \end{bmatrix}$$ and $$U=\begin{bmatrix} 1 & -1 & 2 & 1 \\ 0 & 1 & 2 & 2 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$ You can check that $A=LU$.

• @ egreg thanks a lot for your time, you ad a typo in your system of equations x1 - x4 = -5 not 5, also step 4 and 5 is this trying to get a 0 in row 1 column 2 and 3? if so why not get one for column 4? – jh123 Oct 15 '16 at 14:42
• @javahelper123 Thanks for pointing up the typo. In steps 4 and 5 we use each leading 1 to get zeros above it, which is what the reduced row echelon form should look like. There is no leading 1 in column 4. – egreg Oct 15 '16 at 14:50
• @ egreg okay so if a leading 1 has a number above it then I should get rid of that number above, and if it fdoesnt have a number above then that's fine, also if there is no leading 1 in a row and it has all 0s then I can not reduce anything above? – jh123 Oct 15 '16 at 14:54
• and also does it have to be directly above? – jh123 Oct 15 '16 at 14:55
• @javahelper123 In step 4 we use the leading 1 in column 3 to get rid of the nonzero coefficients in column 3 above the leading 1 (there are zeros below because we already have a row echelon form). – egreg Oct 15 '16 at 15:10

Call the rows $r_1 \ldots r_4$.. After the following 8 operations you arrive at your answer: $$r_4 \leftarrow r_4 - 3r_3$$ $$r_3 \leftarrow r_3 + r_1$$ $$r_2 \leftarrow r_2 - 2r_1$$ $$r_4 \leftarrow r_4 - r_2$$ $$r_4 \leftarrow r_4 + r_3$$ $$r_2 \leftarrow 2r_2 + r_3$$ $$r_1 \leftarrow 2r_1 - r_2$$ $$r_1 \leftarrow r_1 - r_3$$