0
$\begingroup$

Hi Mathoverflow

I hope you bear with me that my linear algebra knowledge is a little rusty, but I have a question that might potentially very easy to answer. Nevertheless it's been bugging me for a good 3 hours now.

I'm trying to find the LU decomposition of a matrix in order to find the determinant. This would be a straightforward process if it weren't for the fact that my matrix library (Meshcach) only gives me back one matrix when use their LU factor method (together with a pivot). So when I have the matrix A:

Matrix: 3 by 3
2              4              1
4            -10              2 
1              2              4

and I call LUfactor, I get the pivot p: 

Permutation: size: 3
0->0 1->1 2->2

and the matrix LU:

Matrix: 3 by 3
2              4              1 
2            -18              0 
0.5           -0            3.5

My question is: How do I find the upper matrix from LU? It seems that the library stores the upper and lower matrix as one single matrix, but I can't figure out how to separate them.

The true upper and lower matrices should be:

Lower matrix
1              0              0 
0.5            1              0 
0.25         0.5              1

Upper matrix
4            -10              2 
0             -9              0 
0              0            3.5

But I'm not sure how the output of meschach would be used to obtain them. I'm aware that this might partly be an algorithm question and could be argued to belong in stackoverflow instead, but I really think there is a higher chance of running in to somebody math-savy who can figure out what's going on, than there is of running in to a programmer who dealt with exactly this problem before.

I hope somebody can help

Improve this question
$\endgroup$
4
  • $\begingroup$ Is there any reason why you want to calculate the determinant this way? This looks like an overkill, row reduction is much faster and as far as I know the easy LU decomposition algorithms include row-reducing the matrix. If you are really interested in the LU decomposition, there are couple algorithms listed on Wikipedia. A good description of the process (and for many other basic math results) is also given at this page: tutorial.math.lamar.edu/Classes/LinAlg/LUDecomposition.aspx $\endgroup$
    – Nick S
    Commented Oct 24, 2010 at 22:09
  • 1
    $\begingroup$ Not at all overkill; LU decomposition and row reduction are just two different ways of looking at Gaussian elimination. In any event, I don't think this is a research-level question, there are other sites like math.stackexchange.com for more elementary matters. $\endgroup$
    – J. M. isn't a mathematician
    Commented Oct 25, 2010 at 0:51
  • $\begingroup$ It is an overkill because it is dressing up something simple (computing the determinant via GE) in something fancy (computing the LU via GE and then computing the determinant). So although mathematically the two are essentially equivalent, via any other reasonable metric, doing LU first is the long way round. That said, a) you should ask this on math.SE, b) sometimes routines are overloaded - on Octave, if I do lu(A) then I just get one matrix but if I do [L U P] = lu(A) then I get three, c) you shouldn't be computing determinants anyway. $\endgroup$
    – Andrew Stacey
    Commented Oct 25, 2010 at 7:39
  • $\begingroup$ ...I'm missing your point, Andrew. LU decomposition is nothing more than a tidied-up reorganization of Gaussian elimination. When you have the $\mathbf{L}$ and $\mathbf{U}$ matrices (which are more often than not merged into a single matrix for parsimony of space) as well as the permutation matrix, computing the determinant is as easy as multiplying together the diagonal elements of $\mathbf{U}$ and multiplying that product with the signature of the permutation. That doesn't look roundabout to me. $\endgroup$
    – J. M. isn't a mathematician
    Commented Oct 28, 2010 at 9:16

1 Answer 1

Reset to default
2
$\begingroup$

The factorization you give at the end ("the true upper and lower matrices") is incorrect. To see why, just check the (1,1) element in your original matrix. Multiplying your $L$ by your $U$ gives 4 for that element, but your original matrix has a 2 there.

Meshcach's factorization is correct. The right $L$ and $U$ matrices are 


L =   1 0 0 
      2 1 0
    0.5 0 1


U = 2   4   1
    0 -18   0 
    0   0 3.5

You should be able to read that off of Meshcach's output pretty easily.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Here, one can straightforwardly multiply together the diagonal elements of $\mathbf{U}$ since the permutation matrix output is the identity permutation. If the permutation was not the identity, one should multiply the product of the diagonals with -1 if the number of swaps was odd, and 1 otherwise for the determinant. $\endgroup$
    – J. M. isn't a mathematician
    Commented Oct 25, 2010 at 0:57
  • $\begingroup$ Damn, well that would explain my confusion. My reference L and U are from a tutorial explaining how to do the factorization, so it didn't even occur to me to check them. Thanks a lot! $\endgroup$
    – Arnfred
    Commented Oct 25, 2010 at 1:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .