Intersection between orthogonal complement of a subspace and a set

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?

-
Daniel, $0 \notin \rm{Int}(P)$. – chango Feb 6 '12 at 16:16

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.

-
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)$? – joriki Feb 9 '12 at 9:47
@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. – Marc van Leeuwen Feb 9 '12 at 11:15
@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. – chango Feb 9 '12 at 13:43

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$

-
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$. – Marc van Leeuwen Feb 11 '12 at 11:49
[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. – Marc van Leeuwen Feb 11 '12 at 11:59
@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$). – chango Feb 11 '12 at 13:52
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$. – Marc van Leeuwen Feb 11 '12 at 14:10
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. – Marc van Leeuwen Feb 13 '12 at 8:43

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

-
I have come up with an elementary proof that only uses Hahn-Banach. I will post it soon... – chango Feb 11 '12 at 9:29