1
$\begingroup$

Suppose I have a non-negative, symmetric $(n+1)\times(n+1)$ block matrix $$ M = \begin{bmatrix} A & B \\ B^T & 1 \end{bmatrix} $$ where $A$ is an $n\times n$ positive-definite matrix and $B$ is a column vector. I would like to show that $M$ is positive-definite. Using determinant identities, and Schurs compliment, I can reduce the problem to showing that

$$ \det ( A + B B^T ) < 2 |A| \qquad \text{or} \qquad \det( A- B B^T) > 0 $$ I could also equivillantly show that $1-B^TA^{-1}B > 0$ or $A-BB^T$ is positive-definite.

I understand this is is not possible in general, however I have a specific form for $A$, $B$, given by a function of in indicies $A_{i,j} = f(i,j)$, $B_i = f(n+1, i)$. If I can reduce any of these expressions to an algebraic equation involving my function $f(i,j)$ then I can probably verify that it is true.

I've already checked numerically that $M$ is positive-definite for any $n$ (well $n<10^4$).

What I've tried, ideas, comments

1) f(i,j) is pretty messy so I don't write it here

2) There is a theorem (from Gershgorin circle theorem) that is all diagonal entries are positive and the diagonal entry is larger than the sum of all other components in the corresponding column (or row) than it is positive-definite. This is NOT true in my case. i.e. $A_{i,i} \ngtr \sum_{j, j\neq i}A_{i,j}$.

3) The Laplace expansion in cofactors/minors/antisymmetric tensors seems hopeless

4) I've been thinking about explicitly constructing a Cholsky decomposition $M = \begin{bmatrix} L_{1,1} & 0 \\ L_{1,2} & L_{2,2} \end{bmatrix} \begin{bmatrix} L_{1,1}^T & L_{1,2}^T \\ 0 & L_{2,2} \end{bmatrix}$, which would prove it's positive-definite. In this case if $A=L L^T$, then $L_{1,1} = L$, $L_{2,2} = \sqrt{1-B^TA^{-1}B}$ Then I have $L_{1,2} = B^T (L^T)^{-1}$. Actually, is this a sufficient proof?

5) This is cetainly not true for arbitrary $A,B$. Hopefully, for my specific form of $A,B$ given by the function $f(i,j)$ I hope I can reduce the positivity to an algebraic equation involving $f(i,j)$.

Any ideas?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ with $x = [x_A,-x_B]^T$ I find that $x^T M x = x_A^T A x_A - 2 x_B B^T x_A + x_B^2$ so it depends. $\endgroup$ – reuns Jan 13 '16 at 1:15
1
$\begingroup$

This is not true in general, so you need some additional conditions on what $A, B$ can be.

Write a vector $\mathbf{x}=(x,x_{n+1})\in\mathbb{R}^{n+1}$ and compute $\mathbf{x}^TM\mathbf{x}$: $$\mathbf{x}^TM\mathbf{x}=x^TAx+x_{n+1}^2+2x_{n+1}\cdot x^TB,$$ thus if $B$ is "big" relative to $A$, we can make the RHS negative with an appropriate choice of $\mathbf{x}$.

Indeed, in the very simple case for which $n=1$, suppose $A=1$, $B=2$, and choose $\mathbf{x}=(1,-1)^T$ so we have $\mathbf{x}^TM\mathbf{x}=-2$.

$\endgroup$
  • $\begingroup$ Right, I agree it's not true in general. But in my case the coefficients in $A$ are given by $f(i,j)$ a function which is symmetric, non-negative, monotonically increasing in $i$ and $j$. And $B_i = f(n+1, i)$. I am hoping that the condition for positivity can be re-written as some algebraic equation such as $\sum_i A_{i,i} -2B_i^2 = \sum_i \left( f(i,i) - 2f((n+1,i)^2 \right)$ from which I could prove using varies properties of $f$. $\endgroup$ – John Jan 13 '16 at 1:53
  • $\begingroup$ This particular $A,B$ satisfy this condition on $f$ $\endgroup$ – charlestoncrabb Jan 13 '16 at 1:56
  • $\begingroup$ Right, but the equation has no hope of a solution since it depends on the arbitrary paramter $x_{n+1}$ and even on $x_i B_i$ which is also arbitrary. $\endgroup$ – John Jan 13 '16 at 5:01
  • $\begingroup$ What equation are you referring to? $\endgroup$ – charlestoncrabb Jan 13 '16 at 5:13
  • $\begingroup$ $x^TMx = x^T A x + x_{n+1}^2 + 2 x_{n+1} x^T B > 0$ would reduce to $\sum_{i,j} x_i x_j f_{ij} + 2 x_{n+1} \sum_i x_i f_{n+1, i} + x_{n+1}^2 >0 $ which I cannot break into a condition on $f$. At best it reduces to $\sum_i \left( x_i x_j f_{i,j} + 2 x_{n+1} x_i f_{n+1,i} + x_{n+1}^2 x_i^2/||x_i|| \right) > 0$. I would hope it could break down futher into a definite relation between $f$'s. $\endgroup$ – John Jan 13 '16 at 19:41

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.