I wrote an article “Matrix Decomposition” in the December 2012 issue of MSDN Magazine. See http://msdn.microsoft.com/en-us/magazine/jj863137.aspx. As I mention in the article, matrix decomposition isn’t a very flashy topic but matrix decomposition is an important part of many algorithms. Matrix decomposition breaks down a square matrix into two matrixes that when multiplied together give the original matrix. An analogy for regular numbers is that 6 can be decomposed into 3 and 2 because 3 * 2 = 6.

For example, suppose some matrix M is:

3.00 7.00 2.00 5.00
1.00 8.00 4.00 2.00
2.00 1.00 9.00 3.00
5.00 4.00 7.00 1.00

It is possible to decompose M into matrixes L and U:

1.00 0.00 0.00 0.00
0.20 1.00 0.00 0.00
0.40 -0.08 1.00 0.00
0.60 0.64 -0.60 1.00

5.00 4.00 7.00 1.00
0.00 7.20 2.60 1.80
0.00 0.00 6.42 2.75
0.00 0.00 0.00 4.91

Matrix L stands for lower because all the meaningful (non-zero) values are in the lower-left. Matrix U stands for upper because all meaningful numbers are in the upper right.

Actually, an important detail is that when L and U are multiplied together, the result is not quite M, it’s M with rows 0 and 3 exchanged. So, the technique is sometimes called LUP, for lower-upper-permuted, decomposition.

As it turns out, and it’s not obvious at all, that by decomposing a matrix, the extremely difficult process of inverting a matrix is made quite a bit easier. And, matrix inversion is the key step for many important algorithms.

### Like this:

Like Loading...

*Related*