4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That is splendid, especially the last line --- I knew that the $B$ matrix (your notation) was positive semi-definite but I was not making any use of this. But what is the matrix $X$? (Also, I assume that you mean $a^tA^{-1}a<1$ in your first line, rather than $a^tAa<1$.) $\endgroup$ – Stefano Oct 3 '14 at 11:43
  • $\begingroup$ @Stefano Glad you like it :) Actually, $B$ is semidefinite if $a^tA^{-1}a\leq 0$; $B$ is SPSD singular iff $a^tA^{-1}a=0$. If $a^TA^{-1}a>1$, $B$ is indefinite (with one negative eigenvalue). $\endgroup$ – Algebraic Pavel Oct 3 '14 at 11:45
  • $\begingroup$ Great. I edited the comment to ask what $X$ is, it did not appear in my original post. $\endgroup$ – Stefano Oct 3 '14 at 11:46
  • $\begingroup$ Ooops. Sorry I "left" its definition for later but then forgot to define it. Making edit. $\endgroup$ – Algebraic Pavel Oct 3 '14 at 12:10
  • $\begingroup$ Thanks. Also, I guess you meant to write $XBX^t$ rather than $XAX^t$, right? $\endgroup$ – Stefano Oct 3 '14 at 13:55
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks you for the counterexample. It turns out, though, that we were not using the fact that the extended matrix is known to be positive semi-definite, which guarantees $a^t A^{-1}a<1$, see @algebraic-pavel's answer. $\endgroup$ – Stefano Oct 3 '14 at 11:39

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.