# How should I prove a set is convex?

Given a set $$\mathbf{S} = \{ \mathbf{x}\:|\: \mathbf{x}^T\mathbf{V}\mathbf{x}=1 \}$$ where $\mathbf{V}$ is a positive semidefinite matrix. How to prove this set is convex?

I tried in the following way:

First, let $\mathbf{x_1}$ and $\mathbf{x_2}$ are two elements of $\mathbf{S}$. I get $\mathbf{x_1}^T\mathbf{V}\mathbf{x_1} = 1$ and $\mathbf{x_2}^T\mathbf{V}\mathbf{x_2} = 1$.

Second, try a derivation of $\mathbf{x_3}^T\mathbf{V}\mathbf{x_3} = 1$, where $\mathbf{x_3}$ is $t\mathbf{x_1}+(1-t)\mathbf{x_2}$.

What I got is :

$$t^2+(1-t)^2+t(1-t)(\mathbf{x_2}^T\mathbf{V}\mathbf{x_1} + \mathbf{x_1})^T\mathbf{V}\mathbf{x_2}$$

where I don't how to prove this derivation equals to 1.

-
Are you sure that there is equality in the definition of $S$? –  Julián Aguirre Jan 21 '13 at 13:38
Consider the special case when your $x$ comes from $\mathbb{R}^2$, $V$ is the identity, and $S$ is a circle. –  ACARCHAU Jan 21 '13 at 13:43
Your set is NOT convex! –  Mercy Jan 21 '13 at 13:48
Note that the set $S$ is symmetric about the origin, i.e. $x \in S$ iff $-x \in S$. Yet $0 \notin S$. Presumably inequality was meant in the definition of $S$. –  hardmath Jan 21 '13 at 13:51
Since $S$ is contained in a real vector space, we have to show that for all $t \in [0,1]$, $(1-t)x+ty=1$. The condition $x^Tx=1$ implies that matrix is unitary, and so letting $x_1=x$ and $x_2=y$ in the equation above, you can check that it is convex. –  Jaivir Baweja Jan 21 '13 at 13:55

Let $$B:\mathbb{R}^n\times\mathbb{R}^n \to \mathbb{R},\ B(x,y)=x^TVy,\ Q:\mathbb{R}^n \to \mathbb{R},\ Q(x)=B(x,x).$$ Let us also define $$\nu: X:=\mathbb{R}^n\setminus Q^{-1}(0) \to \mathbb{R}^n,\ \nu(x)=\frac{x}{\sqrt{Q(x)}}.$$ Then $S=Q^{-1}(1)$, and for every $x \in X$ we have $$Q(\nu(x))=(\nu(x))^TV\nu(x)=\frac{x^TVx}{Q(x)}=\frac{Q(x)}{Q(x)}=1,$$ i.e. $\nu(X) \subset S$.

For every $x,y \in X$ with $B(x,y)\ne \sqrt{Q(x)Q(y)}$ (e.g. for $B(x,y) \le 0$), and every $t \in [0,1]$ we have \begin{eqnarray} Q((1-t)\nu(x)+t\nu(y))&=&(1-t)^2Q(\nu(x))+2t(1-t)B(\nu(x),\nu(y))+t^2Q(\nu(y))\\ &=&t^2+(1-t)^2+2t(1-t)\frac{B(x,y)}{\sqrt{Q(x)Q(y)}}. \end{eqnarray} Therefore $$Q((1-t)\nu(x)+t\nu(y))=1 \iff \frac{B(x,y)}{\sqrt{Q(x)Q(y)}}=1 \iff B(x,y)=\sqrt{Q(x)Q(y)}.$$ Hence $S$ is not convex

-
That's an incredibly complicated way to go about showing it's not convex. Why don't you just note that $x \in S$ and $-x \in S$, but $\frac{1}{2}(x + (-x)) = 0$ is not? :) –  cardinal Jan 21 '13 at 14:39
Is what I did false or just complicated? –  Mercy Jan 21 '13 at 14:40
Well, in a sense, both: You haven't shown that the set $\{(x,y) \in X \times X : B(x,y)^2 \neq Q(x) Q(y) \}$ is nonempty. ;-) –  cardinal Jan 21 '13 at 14:51
You added your edit in the meantime, actually. (I was dragged away from the computer midstream.) Cheers. –  cardinal Jan 21 '13 at 14:54
@Mercy: You can be sure that if Yanpeng turns in your solution, it will be easy to track for plagiarism. (+1) –  cardinal Jan 21 '13 at 14:57

Many authors allow the empty set to be convex as vacuously satisfying the definition. The only case in which set $S$ might be said to be convex is this, where "positive semi-definite matrix" $V$ is zero.

Otherwise the set $S$ is nonempty, and any $x \in S$ must necessarily be nonzero. But as previous commenters point out, then $-x \in S$ and convexity requires $0 \in S$. Contradiction.

-
thanks for your answer @hardmath –  Yanpeng Jan 21 '13 at 15:32