# Prove that $(C \cap D)^\vee = C^\vee + D^\vee$.

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.

• You've only define $X^\vee$ for $X$ a cone. Do you know that $C\cap D$ is a cone? Commented Sep 26, 2013 at 15:13
• @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...
– Orat
Commented Sep 26, 2013 at 16:52
• 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.
– Orat
Commented Sep 27, 2013 at 14:14

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$.

• 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$.
– Orat
Commented Oct 5, 2013 at 8:49
• 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"). Commented Oct 5, 2013 at 11:03
• 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?
– Orat
Commented Oct 6, 2013 at 9:49

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.$$
• Your 3 and 4 are wrong as stated. However, I've outlined some steps in my edited answer which should help. Commented Oct 6, 2013 at 14:06
• @user43208 Thank you so much. I finally filled in the details of the outlined proof.
– Orat
Commented Oct 9, 2013 at 10:30