2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You are in the case of what is called an "incomplete Cholesky factorization" $\endgroup$ – Jean Marie Oct 2 '19 at 19:52
  • $\begingroup$ @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. $\endgroup$ – Chen Ke Oct 3 '19 at 14:55
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.