Cholesky factor when adding a row and column to already factorized matrix

Question

I have a positive deifnite, symmetrical, $N\times N$ real matrix $A$ which has 1's on the diagonal and all off-diagonal elements positive and $<1$. Let $A=LL^t$ be the Cholesky decomposition of $A$. Suppose now that I extend $A$ as follows: $$\left( \begin{array}{cc} A & a \\ a^t & 1 \end{array} \right)$$ where $a$ is a $N\times1$ real vector with positive elements $<1$. Thus the extended matrix has the same structure as the original matrix $A$. I would like to prove that the Cholesky factor of the extended matrix has the form $$\left( \begin{array}{cc} L & 0 \\ c^t & d \end{array} \right)$$ where $L$ is, again, the Cholesky factor of $A$, $c$ an appropriate $N\times 1$ real vector, and $d$ an appropriate scalar, positive or 0.

By definition of Cholesky factor, the following should hold: $$\left( \begin{array}{cc} A & a \\ a^t & 1 \end{array} \right) = \left( \begin{array}{cc} L & 0 \\ c^t & d \end{array} \right) \left( \begin{array}{cc} L^t & c \\ 0 & d \end{array} \right) = \left( \begin{array}{cc} LL^t & Lc \\ L^tc^t & c^t c + d^2 \end{array} \right)$$ where I just carried out the matrix product. This is promising, and means that we have to prove that we can choose $c$ and $d$ so that these two statements hold: $$a=Lc$$ $$1=c^tc+d^2$$ The first is easy because $L$ is invertible: $$c=L^{-1}a$$ Then second equation becomes $$1=a^t(L^{-1})^tL^{-1}a+d^2$$ or $$1=a^tA^{-1}a+d^2$$ or $$d=\sqrt{1 - a^tA^{-1}a }$$ which gives a real $d$ so long as $a^t A^{-1} a<1$, but I am not sure one can prove this. If that helps, the entries of $A$ and inner products of unit vectors. I have not been able to find numerical counterexamples, but the elements of $a$ are not necessarily small and in the worst case its norm is close to $N$. Is there something about the norm of $A^{-1}$ or of $L^-1$ that can help me out here?

Thanks, Stefano

Answer 1

To make this work, you should explicitly assume that $a^tA^{-1}a<1$; otherwise, the bordered matrix $$ B:=\begin{bmatrix}A & a\\a^t & 1\end{bmatrix} $$ would not be positive definite anymore (and thus the Cholesky factorization would not exist).

The simplest way to see it is to see this is to realize that $$ XBX^t=\begin{bmatrix}A&0\\0&1-a^tA^{-1}a\end{bmatrix}=:C, \quad X:=\begin{bmatrix}I & 0 \\ -a^TA^{-1} & 1\end{bmatrix}, $$ that is (from the Sylvester's inertia theorem), the matrix $B$ has the same inertia as the matrix $C$. Consequently, the matrix $C$ has $N$ positive eigenvalues (since $A$ is SPD) and one eigenvalue with the same sign as that of $1-a^tA^{-1}a$.

Note that $a^tA^{-1}a<1$ is the necessary and sufficient condition for $B$ being SPD.

Answer 2

In general it does not work, because $a^tA^{-1}a$ can be bigger than 1.

For example. If $A$ is symmetric positive definite with all entries bigger than $0$ and the entries in the diagonal equal to 1 then we can prove that there are elements in the diagonal of $A^{-1}$ bigger than 1. Suppose the first element in the diagonal of $A^{-1}$ is bigger than 1, then if $a=(1-\epsilon,\epsilon,\ldots,\epsilon)$ and $\epsilon>0$ really small then $a^tA^{-1}a$ is very close to $e_1^tA^{-1}e_1>1$, where $e_1=(1,0,\ldots,0)$.

Suppose $A$ is symmetric positive definite with all entries bigger than $0$ and the entries in the diagonal equal to 1. By Fiedler's inequality $A\circ A^{-1}-Id$ is positive semidefinite, where $\circ$ is the Hadamard product.

Since the elements in the diagonal of $A$ are 1 then the elements in the diagonal of $A^{-1}$ must be greater or equal to 1. If they are all equal to 1 then the diagonal of $A\circ A^{-1}-Id$ contains only zeros and the $trace(A\circ A^{-1}-Id)=0$, but this implies $A\circ A^{-1}-Id=0$, since it is positive semidefinite. Thus, $A\circ A^{-1}=Id$. Since all the off-diagonal elements of $A$ are not zero, it implies that all off-diagonal elements of $A^{-1}$ are zero. Thus, $A^{-1}=Id$ and $A=Id$. This is a contradiction.