Issue with calculating the cholesky decomposition

I am trying to calculate the cholesky decomposition of the matrix Q=

2 -1 0 -1 0 0 0 0 0
-1 3 -1 0 -1 0 0 0 0
0 -1 2 0 0 -1 0 0 0
-1 0 0  3 -1 0 -1 0 0
0 -1 0 -1 4 -1 0 -1 0
0 0 -1 0 -1 3 0 0 -1
0 0 0 -1 0 0 2 -1 0
0 0 0 0 -1 0 -1 3 -1
0 0 0 0 0 -1 0 -1 2


But it says that the matrix should be positive definite. The inverse of the matrix does exist. Actually the above is a precision matrix. Any suggestions

-
What software are you using for your Cholesky decomposition? – J. M. May 18 '12 at 3:38
What software are you using for your matrix-inversion? – Gottfried Helms May 18 '12 at 15:08

Take $v=(1,1,1,1,1,1,1,1,1)^T$. Then $Q v = 0$, just by looking at the matrix above.

This is not positive definite or invertible. No Matlab necessary.

-
OK, I used Octave :-). – copper.hat May 18 '12 at 3:59

I get the cholesky-factor C by the LDU-decomposition as $\small C=L\cdot D$ with

$$\small \text{L=}\begin{bmatrix} 1&0&0&0&0&0&0&0&0\\ -1/2&1&0&0&0&0&0&0&0\\ 0&-2/5&1&0&0&0&0&0&0\\ -1/2&-1/5&-1/8&1&0&0&0&0&0\\ 0&-2/5&-1/4&-10/19&1&0&0&0&0\\ 0&0&-5/8&-1/19&-25/54&1&0&0&0\\ 0&0&0&-8/19&-5/27&-16/95&1&0&0\\ 0&0&0&0&-19/54&-5/19&-15/17&1&0\\ 0&0&0&0&0&-54/95&-2/17&-1&1 \end{bmatrix}$$

and the diagonalmatrix D with $$\small \text{diag(D)=} \begin{bmatrix} \sqrt{2}&\sqrt{5/2}&\sqrt{8/5}&\sqrt{19/8}&\sqrt{54/19}&\sqrt{95/54}&\sqrt{136/95}&\sqrt{24/17}& 0 \end{bmatrix}$$

Numerically to two dec digits this is

$$\small \text{ C =} \begin{bmatrix} 1.41& 0.00& 0.00& 0.00& 0.00& 0.00& 0.00& 0.00& 0.00\\ -0.71& 1.58& 0.00& 0.00& 0.00& 0.00& 0.00& 0.00& 0.00\\ 0.00& -0.63& 1.26& 0.00& 0.00& 0.00& 0.00& 0.00& 0.00\\ -0.71& -0.32& -0.16& 1.54& 0.00& 0.00& 0.00& 0.00& 0.00\\ 0.00& -0.63& -0.32& -0.81& 1.69& 0.00& 0.00& 0.00& 0.00\\ 0.00& 0.00& -0.79& -0.08& -0.78& 1.33& 0.00& 0.00& 0.00\\ 0.00& 0.00& 0.00& -0.65& -0.31& -0.22& 1.20& 0.00& 0.00\\ 0.00& 0.00& 0.00& 0.00& -0.59& -0.35& -1.06& 1.19& 0.00\\ 0.00& 0.00& 0.00& 0.00& 0.00& -0.75& -0.14& -1.19& 0.00 \end{bmatrix}$$ The right-down entry is zero by the LDU-decomposition, so the matrix Q is only positive semidefinite( one eigenvalue is zero). Some software-cholesky-procedures might not be able to deal with close-to-zero or zero eigenvalues.

-
Checking the singular value decomposition (or eigendecomposition, since the matrix is symmetric after all) reveals that the matrix is in fact singular. Most Cholesky routines are ill-equipped to handle the positive semidefinite case, which is what OP's problem might be. – J. M. May 18 '12 at 3:42