3
$\begingroup$

$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

  • 0
    @Davide that is a norm of matrix L2012-10-28

2 Answers 2

3

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

  • 0
    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$?2012-10-28
1

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 $