7
$\begingroup$

Given the matrix A=$ \left( \begin{array}{ccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8\\ 1 & -1 & 2 & 3 \\ 2 & 1 & 1 &2\end{array} \right) $, write it in the $L_{4 \times 4}U_{4 \times 4}$, where L is the lower triangular matrix and U is the upper triangular matrix.

To be honest, I don't even understand what the question is asking of me, however I do know what upper and lower triangular matrices are.

Thanks in advance for your help.

$\endgroup$
  • 3
    $\begingroup$ Find a lower triangular matrix $L_{4\times 4}$ and a upper triangular matrix $U_{4\times 4}$ such that $A=L_{4\times 4} U_{4 \times 4}$. $\endgroup$ – Patrick Li May 24 '13 at 0:46
  • 3
    $\begingroup$ This is called LU decomposition. See the Doolittle algorithm in particular. $\endgroup$ – Julien May 24 '13 at 0:47
  • $\begingroup$ Note that not every matrix admits a LU decomposition. But every square matrix has a PLU decomposition with $P$ permutation matrix. See this paragraph in particular. Since all the leading principal minors of your matrix are nonzero, it qualifies. $\endgroup$ – Julien May 24 '13 at 1:01
  • $\begingroup$ Here is a very slow-paced video giving the LU decomposition of a $3\times 3$ matrix. This approach is different from the nice answers below as it strictly follows the Gaussian elimination algorithm: you end up with $U$, and you keep track of $L$ along the way. $\endgroup$ – Julien May 24 '13 at 1:52
13
$\begingroup$

Let's go step by step. We want an equation of the following form:

$$\begin{pmatrix}1&2&3&4\\5&6&7&8\\1&-1&2&3\\2&1&1&2\end{pmatrix}=\begin{pmatrix}\star&0&0&0\\\star&\star&0&0\\\star&\star&\star&0\\\star&\star&\star&\star\end{pmatrix}\begin{pmatrix}\star&\star&\star&\star\\0&\star&\star&\star\\0&0&\star&\star\\0&0&0&\star\end{pmatrix}$$

From the first column and first row of our known matrix, it's not too hard to see that we can start with this:

$$\begin{pmatrix}1&2&3&4\\5&6&7&8\\1&-1&2&3\\2&1&1&2\end{pmatrix}=\begin{pmatrix}1&0&0&0\\5&\star&0&0\\1&\star&\star&0\\2&\star&\star&\star\end{pmatrix}\begin{pmatrix}1&2&3&4\\0&\star&\star&\star\\0&0&\star&\star\\0&0&0&\star\end{pmatrix}$$

Next, we can choose the diagonal elements of our upper triangular matrix to be $1$, and fill in the lower triangular matrix column by column:

$$\begin{pmatrix}1&2&3&4\\5&6&7&8\\1&-1&2&3\\2&1&1&2\end{pmatrix}=\begin{pmatrix}1&0&0&0\\5&-4&0&0\\1&-3&\star&0\\2&-3&\star&\star\end{pmatrix}\begin{pmatrix}1&2&3&4\\0&1&\star&\star\\0&0&1&\star\\0&0&0&1\end{pmatrix}$$

$$\begin{pmatrix}1&2&3&4\\5&6&7&8\\1&-1&2&3\\2&1&1&2\end{pmatrix}=\begin{pmatrix}1&0&0&0\\5&-4&0&0\\1&-3&5&0\\2&-3&1&\star\end{pmatrix}\begin{pmatrix}1&2&3&4\\0&1&2&\star\\0&0&1&\star\\0&0&0&1\end{pmatrix}$$

$$\begin{pmatrix}1&2&3&4\\5&6&7&8\\1&-1&2&3\\2&1&1&2\end{pmatrix}=\begin{pmatrix}1&0&0&0\\5&-4&0&0\\1&-3&5&0\\2&-3&1&7/5\end{pmatrix}\begin{pmatrix}1&2&3&4\\0&1&2&3\\0&0&1&8/5\\0&0&0&1\end{pmatrix}$$

$\endgroup$
  • $\begingroup$ Not exactly the way computers proceed (as far as I know, but I'm no expert), yet a very nice and efficient approach, +1. $\endgroup$ – Julien May 24 '13 at 1:44
  • $\begingroup$ @julien: I think you may be right, see my previous comment. Maybe a simple calculation issue I am guessing. Good catch - regards $\endgroup$ – Amzoti May 24 '13 at 2:11
  • $\begingroup$ Thank you for the help! I didn`t realize it wanted me to find L and U such that LU=A. $\endgroup$ – Sujaan Kunalan May 24 '13 at 2:54
14
$\begingroup$

As @Julien pointed out, every square matrix admits a $PLU$ decomposition, where $P$ is a permutation matrix. We have: $A = P \cdot L \cdot U$, such that:

$A=\begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\0 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\\1 & 1 & 0 & 0\\2 & 1 & 1 & 0\\5 & \dfrac{4}{3} & \dfrac{5}{3} & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 & 4\\0 & -3 & -1 & -1\\0 & 0 & -4 & -5\\0 & 0 & 0 & -\dfrac{7}{3} \end{bmatrix}$

You could try manually cranking this one to find its $LU$ factorization. We want:

$L \cdot U = \begin{bmatrix} 1 & 0 & 0 & 0\\l_{21} & 1 & 0 & 0\\l_{31} & l_{32} & 1 & 0\\l_{41} & l_{42} & l_{43} & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{11} & u_{12} & u_{13} & u_{14}\\0 & u_{22} &u_{23} & u_{24}\\0 & 0 & u_{33} & u_{34}\\0 & 0 & 0 & u_{44} \end{bmatrix} = \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}$

We start off by solving the first row, so we get:

$$u_{11} = 1, u_{12} = 2, u_{13} = 3, u_{14} = 4$$

The portion of the multiplication that determines the remaining entries in the first column of $A$ yields:

$$l_{21}u_{11} = 5 \rightarrow l_{21} = 5$$

$$l_{31}u_{11} = 1 \rightarrow l_{31} = 1$$

$$l_{11}u_{11} = 2 \rightarrow l_{41} = 2$$

At this point rewrite all the variables you solved for and then continue the process and see if you can solve the remaining variables. Of course it is easy to check the result if you can solve all of the equations.

So, we currently have:

$L \cdot U = \begin{bmatrix} 1 & 0 & 0 & 0\\5 & 1 & 0 & 0\\1 & l_{32} & 1 & 0\\2 & l_{42} & l_{43} & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 & 4\\0 & u_{22} &u_{23} & u_{24}\\0 & 0 & u_{33} & u_{34}\\0 & 0 & 0 & u_{44} \end{bmatrix} = \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}$

Try solving for $u_{22},u_{23}, u_{24}$, and then $l_{32}, l_{42}$ and continue this process.

$\endgroup$
  • 1
    $\begingroup$ + Nice head start and direction (+ for all that formatting, too!) $\;\langle \ddot\smile\rangle$ $\endgroup$ – Namaste May 24 '13 at 1:46
  • $\begingroup$ It is good that not everyone was as lazy as me linking to a youtube video to avoid all the typesetting...+1. $\endgroup$ – Julien May 24 '13 at 1:48

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.