# How to prove positive definiteness?

$B_{(n+1)(n+1)}$ = $\begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$

is given, and $A$ is a positive definite matrix where its Cholesky factorization is given by $A=L*L^T$ formula. $A$ is $n\times n$ matrix and $u$ is a n_vector.

Now assuming $\|L\|^{-1}\leq 1$, I need to show that $B$ is a positive definite for all $\|u\|<1$.

Thanks

-
The Schur Complement condition for positive definiteness is useful here. –  littleO Oct 28 '12 at 22:52
What is $\lVert L\rVert$? –  Davide Giraudo Oct 28 '12 at 22:57
Can you maybe provide more detailed solution? –  ASROMA Oct 28 '12 at 22:58
@Davide that is a norm of matrix L –  ASROMA Oct 28 '12 at 23:07

By the Schur complement condition for positive definiteness, $B$ is positive definite iff $A$ is positive definite and $1 - u^T A^{-1} u > 0$. Now, \begin{align*} |u^T A^{-1} u | &\leq \| u \| \| A^{-1} u \| \quad \text{(by Cauchy Schwarts)} \\ &\leq \|u\| \|L^{-T}\| \|L^{-1}\| \|u\| \\ &< 1. \end{align*} (In the last step, I use $\|u\| < 1$ and $\| L^{-1} || = \|L^{-T} \| \leq 1$.)

This shows that $1 - u^T A^{-1} u > 0$, so $B > 0$.

-
I don't know about that Schur complement condition, but something is wrong. Consider the matrix $\begin{bmatrix}1/2&1\\1&1\end{bmatrix}$; this is not positive definite, but it would be according to your condition. –  Martin Argerami Oct 28 '12 at 23:27
@all: I made a mistake it should be $\|L\|^{-1}\leq 1$ –  ASROMA Oct 28 '12 at 23:32
Thanks, I think I fixed the answer now. –  littleO Oct 28 '12 at 23:32
Now if I try to do Cholesky factorization of B, given that the complexity of $A=L*L^T$ is N, will B's complexity be $N+4n^2$? –  ASROMA Oct 28 '12 at 23:46

I will assume that $\|L\|$ refers to the operator norm, and that $\|u\|$ refers to the Frobenius norm.

The way the question is phrased, it is not true that $B$ is positive definite. Let $A=\begin{bmatrix}1&0\\0&1/2\end{bmatrix}$, $u=\begin{bmatrix}0\\3/4\end{bmatrix}$. Then $L=\begin{bmatrix}1&0\\0&1/\sqrt2\end{bmatrix}$, and $$B=\begin{bmatrix}1&0&0\\0&1/2&3/4\\0&3/4&1\end{bmatrix}$$ is not positive definite, as $$\begin{bmatrix}0\\1\\-1/2\end{bmatrix}^TB\begin{bmatrix}0\\1\\-1/2\end{bmatrix}=-\frac18$$

-