# Solve $A\cdot x = b$ by Naïve Gaussian elimination

The following is a homework problem:

Let: $$A = \left[\matrix{4& 2& -5 &1\\ -8& 0& 9& 7\\ -32& -4& 43& 18\\ 24 &4 &-22 &-8\\} \right]$$

$$b = \left[\matrix{-1 \\ -1 \\ 3 \\ 14}\right]$$

Solve $A\cdot x = b$ by Naïve Gaussian elimination. Note the relationship between the subtractive row multipliers and the elements of the L matrix. How is the U matrix related to the reduced terms in the augmented matrix before back-substitution?

I have solved the problem and found $L$ and $U$ by Naïve Gaussian elimination.

$$U = \left[\matrix{4& 2& -5& 1\\ 0 &4 &-1& 9\\ 0& 0 &6 &-1\\ 0& 0& 0& 5\\}\right]$$ $$L = \left[\matrix{1& 0& 0& 0\\ -2& 0& 0& 0\\ -8& 3& 1& 0\\ 6& -2& -6 &1 \\ }\right]$$

However, what I seem to be having trouble with is the second part of the question ('How is the $U$ matrix related to the reduced terms in the augmented matrix before back-substitution?')

I understand that $U$ is the first 4 columns of the augmented $Ax$ matrix after row reduction, but what would be a proper answer to this question?

• Those are not the usual $L$ and $U$, because $LU\ne A$. Commented Feb 7, 2014 at 23:01
• They actually are. Someone edited the question and messed up the values. The actual A matrix is [4 2 -5 1; -8 0 9 7; -32 -4 43 18; 24 4 -22 -8] Commented Feb 7, 2014 at 23:58
• In the edit history there's no trace of the matrix you're saying. It has been like that since the beginning. Please, fix it in the question, not in comments. Commented Feb 8, 2014 at 0:41
• I probably copied and pasted the wrong one in the first place. anyway, fixed now Commented Feb 8, 2014 at 0:44

The matrix $A$ is lower triangular and invertible, because all coefficients on the diagonal are nonzero. So when you do the $LU$ decomposition, you have $L=A$ and $U$ is the identity matrix.

If you properly do Gaussian elimination, the first step (eliminating under the first pivot) will give the matrix $$\begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 3 & 1 & 0\\ 0 &-2 & 1 & 1 \end{bmatrix}$$ and so on for the other columns.

Since the original matrix has been changed, here's what can be said; after elimination according to the Gauss-Doolittle method (no reduction of pivots), we find, for the augmented matrix, the reduced form $$[U\mid c]=\left[\begin{array}{cccc|c} 4 & 2 & -5 & 1 & -1 \\ 0 & 4 & -1 & 9 & -3 \\ 0 & 0 & 6 & -1 & 4 \\ 0 & 0 & 0 & 5 & 10 \end{array}\right]$$ and the matrix $L$ such that $L[\,U\mid c\,]=[\,A\mid b\,]$ is $$L=\begin{bmatrix} 1 & 0 & 0 & 0 \\ -2 & 1 & 0 & 0 \\ -6 & -3 & 1 & 0 \\ 8 & 2 & -1 & 1 \end{bmatrix}.$$

The question ‘How is the $U$ matrix related to the reduced terms in the augmented matrix before back-substitution?’ is not really clear. What I can say is that the system $$Ux=c,$$ where $c$ denotes the last column in the reduced augmented matrix, is equivalent to the original linear system $Ax=b$. In particular, the form of $U$ tells you that the system has a unique solution. The fact that $L[\,U\mid c\,]=[\,A\mid b\,]$ implies that $Lc=b$, so $c=L^{-1}b$.

What can be done now is to multiply the last row by $1/5$ and do “backwards elimination”, reducing the pivots: we find $$\left[\begin{array}{cccc|c} 1 & 0 & 0 & 0 & 12 \\ 0 & 1 & 0 & 0 & -5 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 2 \end{array}\right]$$ which shows the unique solution.

• Someone edited the question and messed up the elements of matrix A. the actual matrix is [4 2 -5 1; -8 0 9 7; -32 -4 43 18; 24 4 -22 -8]. What happens in this case? Commented Feb 7, 2014 at 23:57
• @RyanHannaAL-Kass Please, edit it and make it correct. Commented Feb 7, 2014 at 23:59
• Done. What happens now? Commented Feb 8, 2014 at 0:46
• @RyanHannaAL-Kass I'll have a look tomorrow morning. Here's almost 2am. Commented Feb 8, 2014 at 0:50