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
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.