Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Are you sure that there is equality in the definition of $S$? –  Julián Aguirre Jan 21 '13 at 13:38
1  
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
1  
Your set is NOT convex! –  Mercy Jan 21 '13 at 13:48
2  
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
show 3 more comments

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
3  
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
1  
You added your edit in the meantime, actually. (I was dragged away from the computer midstream.) Cheers. –  cardinal Jan 21 '13 at 14:54
1  
@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
show 3 more comments

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.

share|improve this answer
    
thanks for your answer @hardmath –  Yanpeng Jan 21 '13 at 15:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.