In ordinary arithmetic, the decomposition of a number is finding two numbers that when multiplied together give the original number. For example, the number 12 can be decomposed into 3 and 4 because 3 * 4 = 12.

There’s a similar idea with matrices. The goal is to start with some matrix M then find two matrices A and B so that A * B = M where the * means matrix multiplication.

Before I go any further I’ll point out that matrix decomposition is important because the technique is used to find the inverse of a matrix, and the matrix inverse is one of the most common and important techniques in all of mathematics.

There are several algorithms you can use to decompose a matrix. I usually use Croat’s algorithm.

I coded up a demo using both C# and JavaScript. In my demo, I start with a matrix M =

 3.0  7.0   2.0   5.0
 1.0  8.0   4.0   2.0
 2.0  1.0   9.0   3.0
 5.0  4.0   7.0   1.0

Weirdly, the algorithm returns the two A and B decompositions combined into one matrix called the LUM (lower-upper matrix):

 5.0000   4.0000   7.0000   1.0000
 0.2000   7.2000   2.6000   1.8000
 0.4000  -0.0833   6.4167   2.7500
 0.6000   0.6389  -0.6017   4.9048

Extracting the lower and upper matrices gives Lower =

 1.0000   0.0000   0.0000   0.0000
 0.2000   1.0000   0.0000   0.0000
 0.4000  -0.0833   1.0000   0.0000
 0.6000   0.6389  -0.6017   1.0000

and Upper =

 5.0000   4.0000   7.0000   1.0000
 0.0000   7.2000   2.6000   1.8000
 0.0000   0.0000   6.4167   2.7500
 0.0000   0.0000   0.0000   4.9048

If you look at LUM and Lower and Upper you can see that Lower has the lower left corner of the LUM with dummy 1.0 values on the diagonal and 0.0 values in the upper right. The Upper has the upper right corner of the LUM, including the diagonal, and 0.0 values in the lower left.

OK, now if you multiply Lower times upper you get (drum roll please):

 5.0   4.0   7.0   1.0
 1.0   8.0   4.0   2.0
 2.0   1.0   9.0   3.0
 3.0   7.0   2.0   5.0

Ooops. Lower * Upper isn’t quite the original matrix M. Some of the rows have been rearranged. Well, as it turn out, the decomposition, in addition to returning the combined LUM matrix, also returns a perm (permutation) vector that tells you how to rearrange the rows of Lower * Upper in order to get the original matrix M back. For my example, the perm vector is:

 3   1   2   0

This means row [3] of Lower * Upper goes to row [0], and so on. I wrote a helper function called applyPerm(m, perm) to programmatically switch the rows.

Well, there’s actually quite a few more details about matrix decomposition, but if you found this blog post looking for a simple explanation, you should have a pretty good grasp of the main ideas.

Artist Thomas Schaller specializes architecture-related scenes, using watercolor. A very difficult technique to get right.