Let $F_0, F_1, \ldots, F_m$ be a $n \times n$ symmetric matrices. We define $$F(x) := F_0 + x_1 F_1 + \cdots + x_m F_m$$ Show that if there does not exist $x \in \Bbb R^m$ such that $F(x)$ is positive definite, then there does exist a positive semidefinite matrix $H \neq 0$ such that $$\sup_x \mbox{tr} \left( F(x) H \right) \leq 0$$

Can you solve it? Contraposition may be useful, but I have no idea.

  • 1
    $\begingroup$ can you use SDP duality? $\endgroup$
    – LinAlg
    Jul 4 '20 at 13:31
  • $\begingroup$ I cannot find the connection between SDP duality and this problem... $\endgroup$ Jul 4 '20 at 13:56

Recall that $\langle A,B \rangle = \operatorname{tr}(AB)$ defines an inner product over the set of symmetric matrices.

The set $S_1 = \{F(x):x \in \Bbb R^n\}$ and the set $S_2$ of positive definite matrices are both convex, and we are given that these two sets are disjoint. By the hyperplane separation theorem, there exists a non-zero matrix $H$ and a constant $c$ such that we have $\langle X,H \rangle \leq c \leq \langle Y, H\rangle$ for all $X \in S_1$ and $Y \in S_2$.

Because $0$ lies in the closure of $S_2$, we have $c \leq \langle 0,H \rangle = 0$.

Claim: $\langle Y,H \rangle \geq 0$ holds for all positive definite $Y$.

Proof of Claim: Suppose that this does not hold. Then, there exists a positive definite $Y$ for which $\langle Y,H \rangle < 0$. For any positive $k$, we note that $kY$ is also positive definite, and $\langle kY,H \rangle = k\langle Y,K \rangle$. This means that $\inf_{Y \in S_2} \langle Y,H \rangle = -\infty$, which contradicts our earlier statement that we always have $\langle Y,H \rangle \geq c$ for some (finite) constant $c$. $\square$

Because $H$ is such that $\langle Y,H \rangle \geq 0$ holds for all positive definite $Y$, it must hold that $H$ is positive semidefinite. Thus, there is indeed a non-zero positive semidefinite matrix $H$ for which $\langle X, H \rangle \leq c \leq 0$ for all $X \in S_1$, which was what we wanted.

  • $\begingroup$ Thank you for your answer, but I still have a question. Why S1 and S2 are disjoint? there may exist a positive semidefinite matrix included in both S1 and S2. $\endgroup$ Jul 4 '20 at 16:19
  • $\begingroup$ @eosa I've fixed it; see my latest edit. $S_2$ should have been the positive definite matrices $\endgroup$ Jul 4 '20 at 16:25
  • $\begingroup$ Thanks, but sorry I have another question. Why H is positive semi-definite? $\endgroup$ Jul 5 '20 at 13:34
  • $\begingroup$ I had left something out there; see my latest edit. If $H$ is a matrix such that $\langle Y, H \rangle \geq 0$ for all positive definite $Y$, then $H$ must be positive semidefinite $\endgroup$ Jul 5 '20 at 13:36
  • $\begingroup$ Thanks, but I have two questions. First, Why H is symmetric? Second, Why ⟨𝑌,𝐻⟩≥0 holds for all positive definite Y? $\endgroup$ Jul 5 '20 at 13:44

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.