Why is Doolittle Decomposition Algorithm failing and what should I try next?

Question

I am trying to find the LU Decomposition of the following matrix:

So far I have only tried the Doolittle Decomposition algorithm with partial pivoting (it's never failed me before!). As far as I can tell, that algorithm will not work because I end up with a zero on the diagonal that I cannot get rid of by swapping rows. After doing some research, I still do not understand:

1. What is special about this matrix that makes the Doolittle method not work for it? Would this be considered a "sparse" matrix?

2. Is there a better algorithm I should use instead?

For your information, I am doing this in the context of solving a system of equations in the form Ax = b, where A is the above matrix and b is something like [0 0 0 5 0 0 0 0 0]^T

Thank you for your help!

Answer 1

1. The matrix is a singular matrix, and therefore your system of equations has no solution

A singular matrix has no inverse, so the solution to your equation AX=B, which is

X = A^-1B

does not exist.

Singular matrices have a determinant of zero. Put another way, they have 2 or more linearly dependent rows or columns, which means some linear combination of its rows or columns is zero. Here, the sum of the 2nd, 5th and 8th rows is zero. There are actually three different combinations that give zero, but I will let you find the others as it might be a good exercise. As a result, your 9x9 matrix is actually rank 6.

1. Doolittle decomposition should serve you well here, just make sure you are decomposing a square, non-singular matrix