<s>[INST] Prove an iff condition for the existence of LU decomposition I'm asked to prove that the matrix
$$A=\begin{pmatrix}
a & b & 0\\
c & d & e\\
0 & 1 & g
\end{pmatrix}$$
has a $LU$ decomp iff $a\not=0$ and $ad\not=bc$. However, I do not believe this to be true since we have
$$\frac{1}{2}\begin{pmatrix}
1 & 0 & 0\\
1 & 1 & 0\\
1 & 1 & 1
\end{pmatrix}\begin{pmatrix}
  0 & 1 & 0\\
 0 & 1 & 1\\
0 & 0 & 1
\end{pmatrix}=\begin{pmatrix}
0 & \frac{1}{2} & 0\\
0 & 1 & \frac{1}{2}\\
0 & 1 & 1
\end{pmatrix}$$
Where the LHS is a $LU$ decomp of the RHS, and the RHS has the form mentioned in the question, with $a=ad=bc=0$, contradicting the iff condition.
So what's going on here? Is this question just wrong, or am I not understanding something?
Thanks
 [/INST] Given: $A=\begin{bmatrix}
a &b  &0 \\ 
 c&d  &e \\ 
0 &1  &g 
\end{bmatrix}$, we use the fact the the LU decomposition is possible if no row exchanges are required.

$\Rightarrow :$ Assuming $A$ has an $LU$ decomposition, we start by doing an elimination step. If $a\ne 0$, then the multipliers are $m_{21}=\frac{c}{a}$ and $m_{31}=0$. Hence the elimination produces
$$A^{(1)}=\begin{bmatrix}
a &b  &0 \\ 
 0&d-\frac{bc}{a}  &e \\ 
0 &1  &g 
\end{bmatrix}$$
A row exchange will not be required if $d\ne \frac{bc}{a}$, or $ad\ne bc$. If this is the case, we proceed with another elimination step with $m_{32}=\frac{1}{d-\frac{bc}{a}}$, from which we obtain
$$A^{(2)}=\begin{bmatrix}
a &b  &0 \\ 
 0&d-\frac{bc}{a}  &e \\ 
0 &0  &g-\frac{e}{d-\frac{bc}{a}} 
\end{bmatrix}$$
Therefore the decomposition becomes
$$A=LU=\begin{bmatrix}
1 &0  &0 \\ 
-\frac{c}{a} &1  &0 \\ 
0 &-\frac{1}{d-\frac{bc}{a}}  & 1
\end{bmatrix} =\begin{bmatrix}
a &b  &0 \\ 
 0&d-\frac{bc}{a}  &e \\ 
0 &0  &g-\frac{e}{d-\frac{bc}{a}} 
\end{bmatrix}$$
$\Leftarrow$: Let us prove by contrapositive. Assume $a=0$ or $ad=bc$. 
If $a=0$, then $A$ will be 
$$A=\begin{bmatrix}
0 &b  &0 \\ 
 c&d  &e \\ 
0 &1  &g 
\end{bmatrix}$$
We see that the first pivot is zero, and hence row exchanges are required and the LU decomposition is not possible. 
If $ad=bc$, then a similar step of elimination (see above) produces 
$$A^{(1)}=\begin{bmatrix}
a &b  &0 \\ 
 0&\frac{1}{a}0=0  &e \\ 
0 &1  &g 
\end{bmatrix}$$
which shows a zero second pivot, and hence requires a row exchange.

Therefore we conclude that the $LU$ decomposition exists iff $a\ne 0$ and $ad \ne bc$.
</s>