# Cholesky solve for semi-definite system

I am thinking about the following linear algebra problem: $$Ax = b$$ where $$A$$ is an $$n$$ by $$n$$ positive semi-definite matrix, in particular, it is rank $$n-1$$ with null space span$$\{e=(1,1,\ldots,1)^\top\}$$. We assume that $$b$$ is in the range of $$A$$ and we are looking for a solution $$x$$ in the range of $$A$$. The solution is unique.

I would like to assume that the Cholesky decomposition is given: $$A = CC^\top$$ where $$C$$ is lower triangular matrix. Because $$A$$ is rank $$n-1$$, the right bottom most entry of $$C$$ will satisfy that $$C(n,n)=0$$.

The new system I get is now $$CC^\top x = b$$ if we let $$z=C^\top x$$ and consider $$Cz = b$$, we can find first $$n-1$$ entries of $$z$$ by a lower triangular solve. The last entry of $$z$$ has to be zero because $$C^\top$$ is upper triangular and $$C^\top(n,n) = 0$$.

My problem is how do we do the next step, that is to find $$x$$ such that $$e^\top x = 0$$ and that $$C^\top x = z$$ Of course this can be solved by adding the equation $$e^\top x = 0$$ into the linear system. But is there a good way where we can exploit the upper triangular property of $$C^\top$$? If possible, I would also assume that $$C$$ is sparse, it would be better if we could exploit the sparsity as well.

• You are in the case of what is called an "incomplete Cholesky factorization" – Jean Marie Oct 2 '19 at 19:52
• @JeanMarie I know it is similar to the incomplete Cholesky. But my main problem is that C is not full rank while many incomplete Cholesky papers assume C is full rank. – Chen Ke Oct 3 '19 at 14:55

I found an easy way to do it. I can simply solve the system $$C^\top y = z$$ By assuming $$y(n) = 0$$, I can obtain a unique solution $$y$$ via upper triangular solve. The difference between $$x$$ and $$y$$ satisfies that $$C^\top (x-y) = 0$$ therefore it lives in the null space of $$C^\top$$, i.e. the span of $$e$$. That means $$x-y = c e$$ Notice that $$e^\top x = 0$$, we must have $$e^\top(x-y) = -e^\top y = c e^\top e = cn$$ so $$c = mean(y)$$, we can easily see that $$x = y - \bar{y} e$$ where $$\bar{y}$$ is the average of $$y$$.