5
$\begingroup$

Definitions and notations: Let $M$ to be the $n$-dimensional Euclidean space $\mathbb{R}^n$ and $N$ its dual space $M^\ast = \mathrm{Hom}_\mathbb{R}(M, \mathbb{R}).$ A subset $C \subset N$ is said to be cone if it is spanned by finitely many elements $v_1, \dots, v_s \in \mathbb{Z}^n$; $$ C = \{ r_1v_1 + \dots + r_sv_s \in N \mid 0 \leq r_1, \dots, r_s \in \mathbb{R} \}. $$ (This is abuse of notation. $\mathbb{Z}^n$ is regarded as a subset of $N$ with an identification $N = \mathbb{R}^n$.) For a cone $C \subset N$, the subset $C^\vee \subset M$ defined as follows is said to be dual cone of $C$; $$ C^\vee = \{ \mu \in M \mid \text{$\langle \nu, \mu \rangle := \nu(\mu) \geq 0$ for all $\nu \in C$} \}. $$

Problem: As a homework, I was required to prove the following statement about dual cones.

Let $C, D$ be cones and $C^\vee + D^\vee = \{ \xi + \eta \mid \xi \in C^\vee,\ \eta \in D^\vee \}$. Prove that $(C \cap D)^\vee = C^\vee + D^\vee$.

Attempt: I already have proved one inclusion relation $(C \cap D)^\vee \supset C^\vee + D^\vee$. But I have been at a loss how to show the other inclusion relation $(C \cap D)^\vee \subset C^\vee + D^\vee$. I think I need to decompose every $\mu \in (C \cap D)^\vee$ into $\mu = \xi + \eta$ so that $\xi \in C^\vee$ and $\eta \in D^\vee$. But how can I find out such a nice ones?

I would greatly appreciated if you gave me a hint rather than a complete answer since this is a homework.

$\endgroup$
3
  • $\begingroup$ You've only define $X^\vee$ for $X$ a cone. Do you know that $C\cap D$ is a cone? $\endgroup$ Commented Sep 26, 2013 at 15:13
  • $\begingroup$ @ThomasAndrews Thank you for your comment. As you pointed out, I should have shown $C \cap D$ is a cone, first. I had thought it is a trivial but it turns out it isn't. Let me think for a while... $\endgroup$
    – Orat
    Commented Sep 26, 2013 at 16:52
  • $\begingroup$ I found a statement in a book. It says $C \cap D$ is a cone, indeed. To my surprise, the proof is technical and long than I expected (almost 2 pages proof including a lemma)! Anyway, $C \cap D$ is a cone and problem makes sense. $\endgroup$
    – Orat
    Commented Sep 27, 2013 at 14:14

2 Answers 2

2
+200
$\begingroup$

One approach is to first prove $C = C^{\vee\vee}$. Then, with the aid of the fact that $C \subseteq D$ implies $D^\vee \subseteq C^\vee$, the direction you want is made much easier.

Relevant here is Farkas's lemma. Let me know if these hints are too obscure.

Edit: Here is some more detail. The easier direction $C^\vee + D^\vee \subseteq (C \cap D)^\vee$ has been proven; we want to show $(C \cap D)^\vee \subseteq C^\vee + D^\vee$.

Preliminaries: for a finite-dimensional vector space $M$ over $\mathbb{R}$ there is a canonical isomorphism $M \cong \hom(M^\ast, \mathbb{R})$, i.e., an isomorphism $i: M \stackrel{\sim}{\to} M^{\ast\ast}$, where for $v \in M$ we define $i(v)$ by the rule $i(v)(f) := f(v)$ (for any $f \in M^\ast$).

Define the dual of a cone $D \subseteq M^\ast$ to be $D^\vee = \{v \in M: \; \forall_{f \in D} i(v)(f) \geq 0\}$.

  • Step 1: check that if $C_1 \subseteq C_2$ where $C_1$, $C_2$ are cones in $M$, then $C_2^\vee \subseteq C_1^\vee$ (easy). Similarly for cones in $M^\ast$.

  • Step 2: Using the definitions, show $C \subseteq C^{\vee\vee}$.

Using a famous result called Farkas's lemma, we can also prove the reverse inclusion: $C^{\vee\vee} \subseteq C$.

  • Step 3: prove this. Hints: suppose $v \notin C$ and show $v \notin C^{\vee\vee}$. This translates to showing there exists $f \in C^\vee$ such that $i(v)(f) = f(v) < 0$, or that there exists $f \in M^\ast$ such that $f(u) \geq 0$ for all $u \in C$, but $f(v) < 0$. For this, use Farkas's lemma.

  • Step 4: conclude $C = C^{\vee\vee}$ for all cones $C$ in $M$. Of course the same applies to cones $D$ in $M^\ast$ as well.

  • Step 5: use steps 1 and 4 to conclude the bi-implication $C_1 \subseteq C_2 \Leftrightarrow C_2^\vee \subseteq C_1^\vee.$ The forward implication is just step 1; for the backward implication, use both steps 1 and 4.

Finally, to prove $(C_1 \cap C_2)^\vee \subseteq C_1^\vee + C_2^\vee$, it is enough (by step 5) to prove

$$(C_1^\vee + C_2^\vee)^\vee \subseteq (C_1 \cap C_2)^{\vee\vee} = C_1 \cap C_2$$

For this, we just prove $(C_1^\vee + C_2^\vee)^\vee \subseteq C_1$ and similarly $(C_1^\vee + C_2^\vee)^\vee \subseteq C_2$. By one of the steps above, this is equivalent to $C_1^\vee \subseteq (C_1^\vee + C_2^\vee)^{\vee\vee}$. But it is trivial that $C_1^\vee \subseteq C_1^\vee + C_2^\vee$. Similarly, $C_2^\vee \subseteq C_1^\vee + C_2^\vee$.

$\endgroup$
3
  • $\begingroup$ I've never heard of that lemma before. Thank you for telling me. If I understand you correctly, the outline of the proof that you suggest is the following, right? (1)$C + D$ is a cone, (2)$C^\vee + D^\vee = (C + D)^\vee$, (3)$C + D \subseteq C \cap D$, and (4)$C^\vee + D^\vee \supseteq (C \cap D)^\vee$. $\endgroup$
    – Orat
    Commented Oct 5, 2013 at 8:49
  • $\begingroup$ Yes, except that your (3) had a typo. :-) The other thing is to figure out just how Farkas's lemma implies the duality $C = C^{\vee\vee}$. There are two inclusions to be proved: $C \subseteq C^{\vee\vee}$ and the reverse. One inclusion is easy, but the other uses Farkas's lemma (which goes by other names involving the word "alternative"). $\endgroup$
    – user43208
    Commented Oct 5, 2013 at 11:03
  • $\begingroup$ I tried to fill in details of the suggested proof and I post what I've done. I had, however, similar difficulty to prove 3.$(C + D)^\vee \subseteq C^\vee + D^\vee$ as I have had in the original question. I also couldn't prove 4.$C + D \subseteq C \cap D$; I tried to show contradiction but I couldn't. Would you give me some advice to these problems? $\endgroup$
    – Orat
    Commented Oct 6, 2013 at 9:49
1
$\begingroup$

This is my incomplete answer to get some advice.

  1. $X \subseteq Y \implies X^\vee \supseteq Y^\vee$: For $\eta \in Y^\vee$ and $x \in X \subseteq Y$, we get $\langle x, \eta \rangle \geq 0$ and conclude that $\eta \in X^\vee$.
  2. $C + D$ is a cone: Since $C$ and $D$ are cones, there exist some finitely many elements $v_1, \dots, v_s, w_1 \dots, w_t \in \mathbb{Z}^n$ such that $$ C = \Big\{ \sum p_i v_i \mid 0 \leq p_i \in \mathbb{R} \Big\},$$ $$ D = \Big\{ \sum q_j w_j \mid 0 \leq q_j \in \mathbb{R} \Big\}.$$ Hence, $C + D$ is
    $$ \Big\{ \sum p_i v_i + \sum q_j w_j \mid 0 \leq p_i, q_j \in \mathbb{R} \Big\}$$ and is a cone, indeed.

  3. $(C + D)^\vee \subseteq C^\vee + D^\vee$:...

  4. $C + D \subseteq C \cap D$: Let $x \in C + D$. From (2), there exist $p_i, q_j \geq 0$ such that $$ x = \sum p_i v_i + \sum q_j w_j. $$ Assume that $x \not \in C$. By Farkas' lemma (and Riesz representation theorem), there exist $y \in M$ such that $$ \langle y, v_i \rangle \geq 0, \quad \langle y, x \rangle < 0 $$ for all $i$. Since $\langle y, x \rangle = \sum p_i \langle y, v_i \rangle + \sum q_j \langle y, w_j \rangle$, there exist $\hat{\jmath}$ such that $\langle y, w_\hat{\jmath} \rangle < 0$...

  5. $(C \cap D)^\vee \subseteq C^\vee + D^\vee$: From (1), (3), and (4), we get $$ (C \cap D)^\vee \stackrel{(1), (4)}{\subseteq} (C + D)^\vee \stackrel{(3)}{\subseteq} C^\vee + D^\vee.$$
$\endgroup$
2
  • 1
    $\begingroup$ Your 3 and 4 are wrong as stated. However, I've outlined some steps in my edited answer which should help. $\endgroup$
    – user43208
    Commented Oct 6, 2013 at 14:06
  • $\begingroup$ @user43208 Thank you so much. I finally filled in the details of the outlined proof. $\endgroup$
    – Orat
    Commented Oct 9, 2013 at 10:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .