How can I do this kind of Cholesky decomposition?

Question

$B_{(n+1)(n+1)}$ = $ \begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$ = $\begin{bmatrix} L_{11} & 0 \\ L_{21} & l_{22} \\ \end{bmatrix} $ $\begin{bmatrix} L_{11}^T & L_{21}^T \\ 0 & l_{22} \\ \end{bmatrix} $

Here A is nxn matrix, $l_{22}$ is scalar, $L_{11}$ is also a nxn matrix. So Cholasky factorization of this B matrix will give us the following: $L_{11}*L_{11}^T=A, L_{11}*L_{21}^T=u, L_{21}*L_{11}^T=u^T$, and $L_{21}*L_{21}^T=1-l_{11}^2$

1. What to do after this?

2. Is the factorization done?

3. If this is done, how can I compute B's complexity(flops) if A is given - lets say it is N?

Thanks.

Answer 1

Well, regarding 1, $L_1$ is computed as per the standard cholesky factorisation for $A$. Then from your working, you get $L_{21}^T=L_{11}^{-1}u$ and $l_{22}=\sqrt{1-L_{21}L_{21}^T}$.

For 2, now the factorisation is complete as you have determined what they factors should be.

For 3, the complexity for the determination of $L_{11}$ is known for the Cholesky decomposition. Then you just have to increment it for the additional computations which you incur.