# enough conditions to check that a matrix doesn't have Cholesky factorization while factorizing it

I wrote this code to find Cholesky factorization of a symmetric positive definite matrix in MatLab:

function L = cholesky(A)
n = length(A);
L = zeros(n, n);
for i=1:n
l = L_solver(L(1:i-1, 1:i-1), A(1:i-1, i));
L(i, 1:i-1) = l;
L(i, i) = sqrt(A(i, i) - l.'*l);
end
end


Which L_solver(L, b) solves linear system $$Lx=b$$ and returns $$x$$. Then I tried to improve it. If the input matrix $$A$$ is not positive definite, it finds the least non-negative integer $$t$$ such if we add $$tI$$ to $$A$$, it becomes positive definite and we can return its Cholesky factorization. And we also return that $$t$$. This is how I modified the code:

function [L, t] = cholesky_decomposition(A)
n = length(A);
t = 0;
while true
L = zeros(n, n);
found = true;
for i=1:n
l = L_solver(L(1:i-1, 1:i-1), A(1:i-1, i));
L(i, 1:i-1) = l;
L(i, i) = sqrt(A(i, i) - l.'*l);
if (imag(L(i, i)) > 0) || A(i, i) <= 0
t = t + 1;
A = A + eye(n, n);
found = false;
break;
end
end
if found
break;
end
end
end


As I searched, the most efficient method to check if a matrix is positive definite, is to check if it has Cholesky factorization. So I try to factorize it and if I reach an entry on the main diagonal that isn't positive or inside the square-root becomes negative, I add $$I$$ to the matrix. I want to know if these two conditions are correct and enough in this scenario.

• Just a small nitpick (but a professionally important one), while enough is a decent word to describe what you want to ask, it is still vague. Mathematically precise terms are "sufficient conditions" and "necessary conditions". Nov 13 at 20:39