Difficulty using LUDecomposition

Question

I'm having trouble using LUDecomposition with pivoting. I read the Mathematica help on this particular command, but I'm still lost. Take a matrix like:

a = {{1, 2, 3}, {2, 4, 1}, {2, 5, 7}}

I evaluated

{lu, p, c} = LUDecomposition[{{1, 2, 3}, {2, 4, 1}, {2, 5, 7}}]

and got

{{{1, 2, 3}, {2, 1, 1}, {2, 0, -5}}, {1, 3, 2}, 0}

I don't really understand how to interpret this result, assuming that it's correct.

Answer 1

m = {{1, 2, 3}, {2, 4, 1}, {2, 5, 7}};
{lu, p, c} = LUDecomposition[m];
l = lu SparseArray[{i_, j_} /; j < i -> 1, {3, 3}] + IdentityMatrix[3];
u = lu SparseArray[{i_, j_} /; j >= i -> 1, {3, 3}];
l.u == m[[p]]
(* True *)

l.u is equal to a permutation of the rows of m

MatrixForm /@ {l, u}

Answer 2

As noted in the docs for LUDecomposition[], the two triangles are by default returned together as a single array; this is customary for LU decomposition routines, as in the original LINPACK and MATLAB's lu(). In fact, exactly this same format is stored internally by the LinearSolveFunction[] returned by LinearSolve[]:

a = {{1, 2, 3}, {2, 4, 1}, {2, 5, 7}};
{lu, piv, cond} = LUDecomposition[{{1, 2, 3}, {2, 4, 1}, {2, 5, 7}}]
   {{{1, 2, 3}, {2, 1, 1}, {2, 0, -5}}, {1, 3, 2}, 1}

ls = LinearSolve[{{1, 2, 3}, {2, 4, 1}, {2, 5, 7}}];
ls[[2, 3]]
   {{{1, 2, 3}, {2, 1, 1}, {2, 0, -5}}, {1, 3, 2}, 1}

You will need the first two results to reconstitute your original matrix. (The third result is a valuable diagnostic quantity called the matrix condition number; I should hope that this will eventually be introduced to you in your classes.)

In MATLAB, one could use the utility functions tril() and triu() to extract the triangular factors from the compressed array representing the LU decomposition. In Mathematica, on the other hand, belisarius has shown the way it used to be done. However, since version 7, Mathematica has been able to catch up to MATLAB in this regard, since the functions LowerTriangularize[] and UpperTriangularize[] became built-in:

l = LowerTriangularize[lu, -1] + IdentityMatrix[Length[lu]]
   {{1, 0, 0}, {2, 1, 0}, {2, 0, 1}}

u = UpperTriangularize[lu]
   {{1, 2, 3}, {0, 1, 1}, {0, 0, -5}}

To reconstitute the permutation matrix, do this:

p = IdentityMatrix[Length[lu]][[piv]]
   {{1, 0, 0}, {0, 0, 1}, {0, 1, 0}}

Now, we can easily check the decomposition:

p.a - l.u
   {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}}

As an aside, here is how one computes Det[a] using the results of LUDecomposition[a]:

{Signature[piv] Tr[lu, Times], Det[a]}
   {5, 5}

Answer 3

Alternative Implementation

Hidden deep in the documentation code is supplied for explicit LU-factorization.

Documentation`HelpLookup@"Compatibility/tutorial/LinearAlgebra/MatrixManipulation"

LUmatrices[mm_?MatrixQ] := Module[
                                  {m},
                                  m=First@LUDecomposition[mm];
                                  {m - # + IdentityMatrix[Length@m], #} &[m*Array[Boole[# <= #2] &, Dimensions@m]]
                          ];

---

A = {{1, 2, 3}, {2, 4, 1}, {2, 5, 7}};
MatrixForm /@ LUmatrices[a]

Here is the output for your matrix.

I do not know how efficient or general this implementation is.

Answer 4

I don't know why people are complicating this more than it should be.

You did the LUDecomposition function and got this:

 {{{1, 2, 3}, {2, 1, 1}, {2, 0, -5}}, {1, 3, 2}, 1}

All you need to do is grab the first part of this answer, so the matrix:

{{1, 2, 3}, {2, 1, 1}, {2, 0, -5}}

To make it easier input it as an actual matrix form

---

From here it is super easy to see the answer once you know how to interpret it

For the Lower triangular matrix all you do is:

1. Keep the values in red in the lower part of the matrix
2. Erase the diagonal entries and everything above
3. Replace the diagonal entries by 1's
4. Everything else above by 0's
5. Voila your L matrix

Like so:

---

As you can guess the Upper triangular matrix is similar to this:

1. You grab the same matrix with all the entries
2. This time you erase everything below the diagonal and replace it by 0's
3. Voila your U matrix

Like so:

That is literally all you need to do, it seems long when I explain but this is such a quick way to do this.

This works everytime with all matrices.