Have to show that
$$\begin{bmatrix}0 & 1\\1 & 1\end{bmatrix}$$ has no LU factorization.
It seems trivial just to say that this cannot have an LU decomposition because it is a lower triangular matrix already.
What is a more formal way of suggesting that this cannot be furth decomposed into LU?
$\endgroup$ 13 Answers
$\begingroup$Suppose $A = \pmatrix{0 & 1 \\ 1 & 1}$ has an $LU$ decomposition.
Then $A=LU$ for some lower triangular matrix $L$ and upper triangular matrix $U$.
Let $L= \pmatrix{ l_{11} & 0 \\ l_{21} & l_{22}}$ and $U = \pmatrix{ u_{11} & u_{12} \\ 0 & u_{22}}$
By matrix multiplication, we conclude the following:
$a_{11} = l_{11} \cdot u_{11} = 0$, so it must be either $l_{11}=0$ or $u_{11}=0$.
Suppose $l_{11}=0$, since $a_{12} = l_{11} \cdot u_{21}$ this would imply $a_{12} = 0 \neq 1$. A contradiction.
Suppose $u_{111}=0$, since $a_{21} = l_{21} \cdot u_{11}$ this would imply $a_{21} = 0 \neq 1$. A contradiction.
So we conclude that $A$ cannot have an $LU$ decomposition. $\square$
$\endgroup$ 1 $\begingroup$Your matrix is not lower triangular. If it were, then taking $U$ to be the identity matrix would give you an LU decomposition.
What happens here is that your matrix is non-singular, and its $1,1$ entry is zero. If you write it as $LU$ with $L$ lower triangular and $U$ upper triangular, then $A_{11}=L_{11}U_{11}$. So either $L_{11}=0$ or $U_{11}=0$, and this would made the corresponding matrix singular, and so $A$ would be singular, a contradiction.
$\endgroup$ 2 $\begingroup$I would say, that an argument based on the nature of the LU decomposition suffices. A constructive argument would be, that a step in the LU decomposition algorithm can not be performed - division by zero, e.g. $l_{i,1}=\frac{ a_{i,1} }{a_{1,1} }$ where here $i=2$. Hence the simple LU decomposition is not possible.
Though LU with partial pivoting is still possible (trivial).
