1

The set of positive definite matrices is convex. But what about this set?

$$\Omega = \left\{ (\mathbf{A}, \mathbf{b}) \in \mathbb{R}^{n \times n} \times \mathbb{R}^n : (\mathbf{A} - \mathbf{b}\mathbf{b}^\top) \text{ is p.d. } \right\}$$

I didn't have much luck trying to apply the definition.

Lucas
  • 147

2 Answers2

1

Take $(A, b) \in \Omega$ and $(B, c) \in \Omega$ and let $\lambda \in [0, 1]$.

The question is whether $(C, d) := (\lambda A + (1-\lambda) B, \lambda b + (1-\lambda) c)$ is in $\Omega$, that is whether $C - d d^T$ is positive definite. But

\begin{align} C - d d^T &= \lambda A + (1 - \lambda) B - (\lambda b + (1 - \lambda) c) (\lambda b + (1 - \lambda) c)^\top \\ &= \lambda A + (1 - \lambda) B - (\lambda (b - c) + c) (b - (1 - \lambda) (b - c))^\top \\ &= \lambda A + (1 - \lambda) B - \lambda (b - c)b^\top - cb^\top + (1 - \lambda)c(b - c)^\top + \lambda (1 - \lambda) (b - c) (b - c)^T \\ &= \lambda (A - b b^T) + (1 - \lambda) (B - c c^T) + \lambda (1 - \lambda) (b - c) (b - c)^T, \end{align} which is indeed positive definite.

Lucas
  • 147
user66081
  • 3,987
  • 17
  • 29
  • Awesome, thanks! It took me a moment to get to the right-hand side (I needed this intermediate step: $(\lambda \mathbf{b} + (1 - \lambda) \mathbf{c}) (\lambda \mathbf{b} + (1 - \lambda) \mathbf{c})^\top = (\lambda (\mathbf{b} - \mathbf{c}) + \mathbf{c})(\mathbf{b} + (1 - \lambda) (\mathbf{c} - \mathbf{b}))^\top$). – Lucas Jan 28 '15 at 16:34
  • @user66081 That expression for $C$ disgrees with my computation. I think that last term should just be $$ -\lambda(1 - \lambda)[b^Tc + c^Tb] $$ – Ben Grossmann Jan 28 '15 at 21:24
  • I added a few intermediate steps to make it easier to see the equality. – Lucas Feb 08 '15 at 21:28
  • @Omnomnomnom: do you see which step might be wrong? – user66081 Feb 08 '15 at 22:11
0

Note that $(A,b) \in \Omega$ if and only if for all $x \in \Bbb R^n$: $$ x^*Ax - |\langle x,b \rangle|^2 > 0 $$ For $(A,b),(A',b') \in \Omega$ and $t \in (0,1)$, we have $$ x^*(tA + (1-t)A')x - |\langle x,tb + (1-t)b' \rangle|^2 = \\ t\left[x^*Ax - |\langle x,b \rangle|^2\right] + (1-t)\left[x^*A'x - |\langle x,b' \rangle|^2\right] - t(1-t)\text{Re}\left[\langle x,b\rangle \langle x,b'\rangle\right] $$ So, I suspect that the answer is probably no.

Ben Grossmann
  • 225,327