December 2012

Volume 27 Number 12

C# - Matrix Decomposition

By James McCaffrey | December 2012

Matrix decomposition, a technique that breaks down a square numeric matrix into two different square matrices, is the basis for efficiently solving a system of equations, which in turn is the basis for inverting a matrix. And inverting a matrix is a part of many important algorithms. This article presents and explains C# code that performs matrix decomposition, matrix inversion, a system of equations solution and related operations.

Admittedly, matrix decomposition isn’t a flashy topic, but a collection of matrix methods can be an important addition to your personal code library. The methods are explained so you can modify the source code to meet your own needs. Additionally, some of the techniques used in the matrix methods can be reused in other coding scenarios.

The best way for you to get a feel for the kind of information presented in this article is to take a look at the screenshot in Figure 1. The demo program begins by creating a 4 x 4 square matrix and displaying its values. Next, the matrix is decomposed into what’s called an LUP matrix. L stands for lower and U stands for upper. The P part (P stands for permutation) is an array with values {3,1,2,0} and indicates that rows 0 and 3 were exchanged during the decomposition process. The decomposition also generated a toggle value of -1, indicating that an odd number of row exchanges occurred. The demo program displays the decomposition in two ways: first as a combined LU matrix and then as separate L and U matrices. Next, the program computes and displays the inverse of the original matrix, using the LUP matrix behind the scenes. The demo program computes the determinant of the original matrix, again using the decomposition. It then uses the inverse of the matrix to solve a system of linear equations and concludes by combining the L and U matrices back into the original matrix.

Figure 1 Matrix Decomposition Demo

But why go to all the trouble of creating a custom matrix decomposition method and a library of related methods? Although there are many standalone matrix tools available, they can sometimes be difficult to integrate into an application or system. And in spite of the fundamental importance of matrix decomposition, there are few free, non-copyrighted .NET code implementations available; those that do exist are often not explained in enough detail for you to modify the source code to suit your coding scenarios.

This article assumes you have intermediate C# programming skills and at least a basic understanding of matrix operations and terminology. All of the key C# code is presented in this article. The code is also available from the MSDN code download site at msdn.microsoft.com/magazine/msdnmag1212.

Dr. James McCaffrey works for Volt Information Sciences Inc., where he manages technical training for software engineers working at the Microsoft Redmond, Wash., campus. He has worked on several Microsoft products including Internet Explorer and MSN Search. McCaffrey is the author of .NET Test Automation Recipes (Apress, 2006). He can be reached at jammc@microsoft.com.

Thanks to the following technical experts for reviewing this article: Paul Koch and Dan Liebling