15
$\begingroup$

Consider the normed vector space $E=\mathbb{R}^n$. Define

$ P=\{x \in \mathbb{R}^n: x_i \geq 0, \forall i \}$.

Let $M$ be a subspace such that $M \cap P = \{0\}$. I want to see that $M^\perp \cap {\rm Int}(P) \neq \emptyset $. This seems obvious geometrically, any idea how a short proof would look like?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Daniel, $0 \notin \rm{Int}(P)$. $\endgroup$ – chango Feb 6 '12 at 16:16
3
$\begingroup$

Here is a proof based on another fact that seems geometrically obvious, and which I will prove below.

Lemma For any set of vectors $v_1,\ldots,v_n$ in a real vector space $V$ for which there exists no non-trivial relation $\vec0=\alpha_1 v_1+\cdots+\alpha_n v_n$ with $\alpha_i\geq0$ for all $i$, there exists a linear form $f$ on $V$ such that $f(v_i)>0$ for all $i$. Under the weaker hypothesis that there exists no relation $\vec0=\alpha_1 v_1+\cdots+\alpha_n v_n$ with $\alpha_i>0$ for all $i$, there exists a linear form $f$ on $V$ such that $f(v_i)\geq0$ for all $i$ and $f(v_i)>0$ for at least one $i$.

Conversely, in both cases, such a linear form immediately witnesses the impossibility of relations of the indicated kind.

Now suppose $M$ is a subspace with $M\cap P=\{\vec0\}$, and, for a contradiction, also $M^\perp\cap\mathrm{Int}(P)=\emptyset$. From the first fact we see that the $n$ images of the canonical basis $\{e_1,\ldots,e_n\}$ of $\mathbb R^n$ orthogonally projected onto $M^\perp$ satisfy the conditions of the first part of the lemma: if there were a non-trivial relation with non-negative coefficients between those projections, then the corresponding non-trivial linear combination of the vectors $e_i$ themselves would lie in $M\cap P$ without being $\vec0$. So the lemma says there is a linear form on $M^\perp$ with strictly positive values on those projections. It can be realised as the scalar product with a vector $v\in M^\perp$, which therefore has $\langle v \mid e_i \rangle>0$ for all $i$; in other words, $v=(v_1,\ldots,v_n)$ with $v_i>0$ for all $i$.

Similarly, $M^\perp\cap\mathrm{Int}(P)=\emptyset$ means that the orthogonal projections of the basis vectors $e_i$ onto $M$ admit no relation between them with all coefficients strictly positive, since the corresponding linear combination would lie in $M^\perp\cap\mathrm{Int}(P)$. By the second part of the lemma this means that there is a non-zero linear form on $M$ that takes non-negative values on all those projections. It can be realised as the scalar product with a vector $w\in M$, which therefore has $\langle w \mid e_i \rangle\geq0$ for all $i$; in other words, $w=(w_1,\ldots,w_n)$ with $w_i\geq0$ for all $i$ and $w_i>0$ for at least one $i$. But then $\langle v\mid w\rangle=v_1w_1+\cdots+v_nw_n>0$, contradicting $v\in M^\perp$ and $w\in M$ so that $v\perp w$.

Now for the proof of the lemma. In both statements we may assume without loss of generality that $V$ is the span, as a vector space, of the vectors $v_1,\ldots,v_n$: that case will provide us with a linear form on the span of those vectors, which can then be arbitrarily extended to the whole space. We shall use the fundamental fact that the cone of the non-negative linear combinations of some finite set of vectors can also be described as the cone of vectors where some finite set of linear forms all take non-negative values (the Minkowski-Weyl theorem).

The hypothesis in the first part of the lemma implies that the cone $C$ of non-negative linear combinations of $v_1,\ldots,v_n$ does not contain any subspace of dimension${}>0$: if it did one could add the combinations giving two opposite non-zero vectors in the subspace to get a non-trivial relation with non-negative coefficients. This means that no vector vanishes under all the linear forms that define $C$, and in particular none of the vectors $v_i$ do. But then taking the sum of all these linear forms gives a linear form that takes a strictly positive value on all the vectors $v_i$, proving this part.

Under the weaker hypothesis of the second part of the lemma, $C$ may contain a subspace of positive dimension, but not the whole space: in that case every $v_i$ would occur in some relation with non-negative coefficients (found using a non-negative expression for $-v_i$), and adding them up would give a relation with all strictly positive coefficients. Then the set of linear forms defining $C$ contains at least one linear form that takes a non-zero value on at least one $v_i$. It takes non-negative values on all of $C$ and in particular on every vector $v_i$, as required.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Very nice. But I don't understand why you need the paragraph that begins "Similarly, $M^\perp\cap\mathrm{Int}(P)=\emptyset$ means" (and thus also the second part of the lemma and its proof in the last paragraph). Isn't $v$ itself in $M^\perp\cap\mathrm{Int}(P)$? $\endgroup$ – joriki Feb 9 '12 at 9:47
  • $\begingroup$ @joriki: You're absolutely right. It is just that the actual vectors $v,w$ were something I introduced at the very end of my reasoning, and I didn't realise this shortcut. $\endgroup$ – Marc van Leeuwen Feb 9 '12 at 11:15
  • $\begingroup$ @Marc: Thank you. I am not familiar with this theorem. I would have to take a closer look at its statement and your argument. My gut tells me that there's got to be a proof involving Hahn-Banach and I am working on discovering it. $\endgroup$ – chango Feb 9 '12 at 13:43
2
$\begingroup$

This is an elementary proof I discovered using a geometric version of Hahn-Banach. Hope you like it. Thanks to all of you who contributed to the discussion. :)

Suppose $M^\perp \cap \rm{Int}P=\emptyset$. Then since both sets are convex and $\rm{Int}P$ is open, it follows that there exists $0 \neq f \in E^*$ that separates them. That is, there exists $\alpha \in \mathbb{R}$ such that

$f(x) \leq \alpha \leq f(y) \text{ for all } x\in M^\perp, y \in \rm{Int} P. $

By Reisz's Lemma $\exists x^* \in E$, $x^*\neq0$, such that $f(x)=(x,x^*)$. Now it is easy to see that since $M^\perp$ is a subspace, the first inequality implies that $(x,x^*)=0$ for all $x \in M^\perp$, ie $x^* \in (M^\perp)^\perp=M$ (since $E$ is finite dimensional).

Therefore, from the second inequality we have $(y,x^*) \geq 0$ for all $y\in \rm{Int}P$. Finally, one only needs to note that $e_i \in \overline{\rm{Int}P}$ for all $i=1,\cdots,n$. The continuity of the inner product now implies that $(e_i,x^*) \geq 0$ for all $i$. I.e., $x^* \in P \cap M$ and $x^* \neq 0$, a contradiction. $\square$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I've made some small corrections to expressions, for readability. The argument is simple indeed (though I don't quite understand why Reisz's Lemma is needed, matrix representation of linear forms in finite dimension suffices). Curiously the dual approach starting with $M\cap\mathrm{Int}P=\emptyset$, although seemingly more direct, won't work, unless one adds small open balls around each $e_i$ to $\mathrm{Int}P$. One gets a linear form $f$ with $f(x)=0<f(y)$ for all $x\in M$, $y\in\mathrm{Int}P$; write $f(x)=(x,y_0)$, and since $f(e_i)>0$ for all $i$, conclude $y_0\in M^\perp\cap\mathrm{Int}P$. $\endgroup$ – Marc van Leeuwen Feb 11 '12 at 11:49
  • $\begingroup$ [Continued] Actually the above needs $f(x)=0<f(y)$ for all $x\in M$, $y\in\mathrm{Int}P$ and for each $y=e_i$, which is why the small open balls around the $e_i$ were needed (which of course should be taken to remain disjoint from $M$). The resulting proof is in fact very similar to my second answer, if you look closely. $\endgroup$ – Marc van Leeuwen Feb 11 '12 at 11:59
  • $\begingroup$ @Marc: Thanks for your comments. Reisz's Lemma says that in a Hilbert space every continuous linear map is a map of the form $(x,x^*)$ for some fixed vector $x^*$ in the space. You don't actually needed if you think of $M^\perp=\{ f \in E^*: f(x)=0 \forall x \in M \}$ but in the context of this problem I am thinking of $M^\perp=\{ y \in E: (x,y)=0 \forall x \in M \}$. Regarding your second comment, the strict inequality is not necessary as you pass to the limit (with, say $y^i_n \to e_i$ and the $\{y^i_n\}_n\subset \rm{Int}P$). $\endgroup$ – chango Feb 11 '12 at 13:52
  • $\begingroup$ That is not what I read at Riesz's lemma, but maybe it amounts to that in Hilbert spaces; anyway seems a bit heavy for the finite dimensional case. I did interpret $M^\perp$ as in your second expression. Finally for your last remark (strict inequality), I don't think that limit argument would do, since it would only give $(e_i,y_0)\geq0$, which is not enough for $y_0\in\mathrm{Int}P$. On the other hand my argument is not quite good either, as adding open balls destroyes convexity of $\mathrm{Int}P$. $\endgroup$ – Marc van Leeuwen Feb 11 '12 at 14:10
  • 1
    $\begingroup$ Please read my first comment carefully. I am not critcising your answer, which is perfect. I am commenting on my own failed attempt to do this more directly starting with $M\cap\mathrm{Int}P=\emptyset$ (which is an easy though weak consequence of $M\cap P=\{0\}$). I thought my frequent mention of $y_0$, which does not occur in your argument, made this obvious. On the other hand my "argument" does not have any $x^*$ in it. I initially thought one could rework your solution to avoid reasoning by contradiction, but it becomes quite ugly, so forget it. My second answer is direct though. $\endgroup$ – Marc van Leeuwen Feb 13 '12 at 8:43
2
$\begingroup$

Based on the comments of my previous answer, I realise that one can simplify the argument considerably. First of all, if $M$ is a hyperplane, then the result is easily proved as follows. One can define $M$ by a linear equation $M=\{(x_1,\ldots,x_n)\in\mathbb R^n\mid x_1a_1+\cdots+a_nx_n=0 \}$ where one can take at least one of the coefficients $a_i$ to be positive. This being so, no other $a_j$ can be non-positive, since otherwise taking $x_i=-a_j$, $x_j=a_i$ and all other coordinates $x_k=0$ would give a non-zero vector in $M\cap P$. But if all $a_j$ are positive, one has $(a_1,\ldots,a_n)\in M^\perp\cap \mathrm{Int}(P)$.

Now what remains is to show that any subspace $M$ intersecting $P$ in $\vec0$ only can be extended to a hyperplane $H$ with the same property, because it then follows that $M^\perp\supseteq H^\perp$ which as we have seen meets $\mathrm{Int}(P)$. Projecting onto $M^\perp$, we need to find an appropriate image for $H$; this needs to be a hyperplane $H'$ of $M^\perp$ that meets the image $\cal C$ of $P$ (by orthogonal projection) only in $\vec0$. But since $P$ meets $M$ only in $\vec0$, its image $\cal C$ is a convex cone that is disjoint from $\mathrm{Int}(-\cal C)$. But the Hahn-Banach separation theorem (on OP's request) provides a linear form that separates $\cal C$ and $\mathrm{Int}(-\cal C)$, and its kernel provides the requested $H'$ (this could also be done using the first part of the lemma in my other answer). Finally take $H=H'\oplus M$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I have come up with an elementary proof that only uses Hahn-Banach. I will post it soon... $\endgroup$ – chango Feb 11 '12 at 9:29

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.