## Matrix Decomposition

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.