Is this set of matrices convex? 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.
 A: 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.
A: 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.
