Is the LU decomposition just Gauss-Jordan elimination?

158 Views Asked by At

I am watching Gilbert Strang's neat lecture on the LU decomposition, which is taught just after Gaussian elimination. $LU$ for a matrix $A$ was found doing $EA=U$ and finally $A=E^{-1}U$.

Seems to me, as a programmer, that we could see this just as Gaussian elimination works for finding an inverse, i.e.,

$$ E \begin{bmatrix} I & A \end{bmatrix} = L U $$

where $\begin{bmatrix} I & A \end{bmatrix}$ is just the augmented matrix, and would imply making the same operations on $A$ and $I$. In this case, we would stop when $A$ is lower triangular, rather than the identity matrix.

I don't have much practice yet and would be interested on whether this idea is correct, or how is it not, or some additions that need to be made.

1

There are 1 best solutions below

0
On

I think the algorithm you used is just a modified version of Gaussian elimination, which is $LU$ decomposition. In this lecture, $A$ is multiplied by some matrices of elementary row operations on left hand side such that $EA=U$, the procedure stops when $A$ is upper triangular not lower triangular. Then $L=E^{-1}$ and $A=LU$.

When we apply Gauss–Jordan elimination to find the inverse of a matrix if it exists, similarly A is multiplied by some matrices of elementary row operations, the procedure stops when left block can be reduced to the identity matrix when A is invertible.

$$\begin{bmatrix} A & I \end{bmatrix}\to \begin{bmatrix} EA=I & E \end{bmatrix}$$ Then $E=A^{-1}$.

It is better to observe the differences when solving a system of linear equation $Ax=b$. For $LU$ decomposition, since $LUx=EAx=Eb$, we need two substitution steps, solve $Ly=Eb$ for $y$ and then $Ux=y$ for $x$. For Gauss–Jordan elimination, we can solve the equation by multiplying the inverse matrix.