# LU factorization of a simple matrix

I have the matrix $$A= \begin{pmatrix} -1&1&1\\1&-1&1\\1&1&-1 \end{pmatrix}$$

It is invertible so it has an LU-factorization (Am I right about that?)

I tried to solve it, I first reached that the upper matrix is equal to $$U=P(2,3)E_1A= \begin{pmatrix} -1&1&1\\0&2&0 \\0&0&2 \end{pmatrix}$$

Where $$E_1= \begin{pmatrix} 1&0&0\\1&1&0 \\1&0&1 \end{pmatrix}$$ And $$P(2,3)$$ is the matrix that switches the 2nd row with the $$3$$rd row.

But I continued as I usually do, the matrix $$L$$ usually turns out to be $$L=[P(2,3)E_1]^{-1}$$, but this wasn't a lower matrix !!

I got that $$L= \begin{pmatrix} 1&0&0\\-1&0&1 \\-1&1&0 \end{pmatrix}$$

I checked my calculations $$3$$ times I don't think I have calculation mistakes...

Can anyone help please by giving a correct method and tell me what I did wrong in the method I used?

You have to perform Gaussian elimination without row swaps. \begin{align} \begin{pmatrix} -1&1&1\\ 1&-1&1\\ 1&1&-1 \end{pmatrix} &\to \begin{pmatrix} 1&-1&-1\\ 1&-1&1\\ 1&1&-1 \end{pmatrix} && R_1\gets -R_1 \\[6px] &\to \begin{pmatrix} 1&-1&-1\\ 0&0&2\\ 0&2&0 \end{pmatrix} &&\begin{aligned} R_2&\gets R_2-R_1 \\ R_3&\gets R_3-R_1 \end{aligned} \end{align} No, the matrix does not admit an $$LU$$ decomposition, with $$L$$ lower triangular and $$U$$ upper triangular.

If you swap rows to begin with, \begin{align} P(2,3)A=\begin{pmatrix} -1&1&1\\ 1&1&-1\\ 1&-1&1\\ \end{pmatrix} &\to \begin{pmatrix} 1&-1&-1\\ 1&1&-1\\ 1&-1&1\\ \end{pmatrix} && R_1\gets -R_1 \\[6px] &\to \begin{pmatrix} 1&-1&-1\\ 0&2&0\\ 0&0&2\\ \end{pmatrix} &&\begin{aligned} R_2&\gets R_2-R_1 \\ R_3&\gets R_3-R_1 \end{aligned} \\[6px] &\to \begin{pmatrix} 1&-1&-1\\ 0&1&0\\ 0&0&1\\ \end{pmatrix} &&\begin{aligned} R_2&\gets \tfrac{1}{2}R_2 \\ R_3&\gets \tfrac{1}{2}R_3 \end{aligned} \end{align} Thus you get $$U=\begin{pmatrix} 1&-1&-1\\ 0&1&0\\ 0&0&1\\ \end{pmatrix} \qquad L=\begin{bmatrix} -1 & 0 & 0 \\ 1 & 2 & 0\\ 1 & 0 & 2 \end{bmatrix}$$ so that $$A=P(2,3)LU$$ If you don't do pivot reduction, the idea is essentially the same.

• Can you please explain your idea a bit more? Why $A$ doesn't have an LU factorization? I didn't quite get it, maybe because I don't know the conditions for a matrix to have the LU factorization... – Fareed Abi Farraj Nov 25 '18 at 12:01
• @FareedAF If it had, you'd find it by performing Gaussian elimination with no row swap. – egreg Nov 25 '18 at 12:03
• Isn't it true that if the matrix is invertible then it has an LU factorization? This matrix is invertible and it doesn't have an LU factorization why? – Fareed Abi Farraj Nov 25 '18 at 12:16
• @FareedAF No. Consider the matrix $P(2,3)$, for instance. However, the definition of LU decomposition may vary; what's yours? – egreg Nov 25 '18 at 12:20
• it is to write the matrix as a product of 2 matrices L and U, where L is a lower triangular matrix and U is an upper triangular matrix. – Fareed Abi Farraj Nov 25 '18 at 12:50

Since you are swapping the second and third rows, you must multiply by the corresponding elemenetary matrix: $$A= \begin{pmatrix} -1&1&1\\1&-1&1\\1&1&-1 \end{pmatrix}= \begin{pmatrix} 1&0&0\\0&0&1\\0&1&0 \end{pmatrix} \begin{pmatrix} 1&0&0\\-1&1&0\\-1&0&1 \end{pmatrix} \begin{pmatrix} -1&1&1\\0&2&0\\0&0&2 \end{pmatrix}=PLU.$$ See WA answer.

You know that $$L$$ will be a lower triangular matrix with ones in the diagional. Now look at the pivots in $$U$$, and conclude all columns (and rows) contain pivots. Now you go back to your $$A$$ matrix, and divide the columns by the diagonal pivot. In your first column, $$-1$$ is on the diagonal, thus you divide the entire column by $$-1$$. In your second column, $$-1$$ is on the diagional, thus all the entries below the diagonal (in this case only the third row) will be divided by $$-1$$. The same applies for the third, getting

$$L=\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ -1 & -1 & 1 \end{bmatrix} ,$$ does this make sense?

• $A \ne LU$ for the the $L$ you suggested – Fareed Abi Farraj Nov 25 '18 at 10:51
• Ah, I guess that's because $U$ is different. I like egregs explanation. – Mathbeginner Nov 26 '18 at 13:25

If $$A$$ is invertible, then it admits an LU factorization if and only if all its leading principal minors are non-zero.

So $$A$$ doesn't have an LU factorization since a leading principal minor is zero, which means that, $$D_2= \bigg| \begin{matrix} -1&1\\1&-1 \end{matrix} \bigg| =0$$

But matrix $$A$$ has a PLU decomposition