Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
1  
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 $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.