# How can I do this kind of Cholesky decomposition?

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

-
That's basically the outer product formulation of Cholesky decomposition. Watkins's book has a discussion on this. –  Ｊ. Ｍ. Oct 28 '12 at 4:55

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 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.
so then $L_{11}$ should be such a matrix that its transpose is equal to itself.... does this tell you anything? I guess symmetric But then how can i decompose if matrix A is not given –  ASROMA Oct 27 '12 at 23:08
If $A$ is not given, then you can't do anymore than I said, where $L_{11}$ is the cholesky factor of $A$. Once you know it, then you can extend the factorisation to an additional dimension, as I describe above. –  Daryl Oct 28 '12 at 1:59
OH, it says that Cholesky decomposition of A is given $A=L*L^T$, but then what does it mean $L_{11}L_{11}=L*L^T$ ? –  ASROMA Oct 28 '12 at 2:23
You have a mistake. In the second matrix, the $(1,1)$ block should be $L_{11}^T$. Also, above, if $L_{11}L_{11}^T=LL^T$, then, $L_{11}=$? –  Daryl Oct 28 '12 at 3:34