1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Fareed Abi Farraj Nov 25 '18 at 12:01
  • $\begingroup$ @FareedAF If it had, you'd find it by performing Gaussian elimination with no row swap. $\endgroup$ – egreg Nov 25 '18 at 12:03
  • $\begingroup$ 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? $\endgroup$ – Fareed Abi Farraj Nov 25 '18 at 12:16
  • $\begingroup$ @FareedAF No. Consider the matrix $P(2,3)$, for instance. However, the definition of LU decomposition may vary; what's yours? $\endgroup$ – egreg Nov 25 '18 at 12:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Fareed Abi Farraj Nov 25 '18 at 12:50
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.