Show that $C=\{x: Ax\le 0\},$ where $A$ is an $m\times n$ matrix, has at most one extreme point, the origin.

I tried to do the proof by contradiction but I don't know how to continue.

Attempt: (By contradiction)

Let's suppose $C$ has more than 1 extreme point, i.e. 2 extreme points, let's say $x,y\in C$ are such that

if $x=\lambda x_1+(1-\lambda)x_2,x_1,x_2\in C,\lambda\in(0,1),$ then $x=x_1=x_2$.

Similarly, $y=\lambda y_1+(1-\lambda)y_2,y_1,y_2\in C,\lambda\in(0,1),$ then $y=y_1=y_2$, by definition.

Also we have that $Ax\le0,Ay\le0$ and the same happens for $x_i$ and $y_i$.

What can I do from here?

Could anyone help me, please?


Take $x\in C$ non zero. We will show that $x$ is not an extreme point.

Since $Ax\leq 0$ it implies that $A(2x)\leq 0$ therefore $2x \in C$. Also $0\in C$.

Now, notice that $$x= \frac{1}{2} \cdot 2x+\frac{1}{2} 0.$$

Hence, $x$ is not an extreme point.

  • 2
    $\begingroup$ You beat me to it (+1). $\endgroup$
    – quasi
    Feb 1 '18 at 6:03
  • $\begingroup$ Wow, you came back Clark:) $\endgroup$
    – user441848
    Feb 1 '18 at 6:04

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.