# Existence of a non-null and non-negative vector in $F\cup F^\perp$

In $$\mathbb{R}^n$$ ($$n\ge 1$$) endowed with the usual dot product, for any linear subspace $$F$$, does there exist a non-null vector with non-negative coordinates in $$F\cup F^\perp$$?

• @gmvh this has nothing to do with rings-and-algebras, which you added.
– YCor
Oct 11, 2020 at 11:14
• ... but the key is to use convex geometry (this is why I added the tag).
– YCor
Oct 11, 2020 at 11:23
• @YCor: well, linear algebra is listed as a subtopic of ra.rings-and-algebras, which is why I added it; which top-level tag would you suggest?
– gmvh
Oct 11, 2020 at 12:07
• @gmvh if any, mg.metric-geometry fits better. To avoid filling comments here, I replied more in general in the Editor's lounge (particular message here)
– YCor
Oct 11, 2020 at 12:14

Yes. For any two closed convex cones $$C,D$$ we have $$(C+ D)^\circ=C^\circ\cap D^\circ$$, where $$C^\circ$$ is the dual cone: $$C^\circ=\{y\in\mathbf{R}^n:\forall c\in C:\langle y,c\rangle\ge 0\}$$. A standard duality theorem is $$C^{\circ\circ}=C$$ for every closed convex cone $$C$$. Hence, the dual equality holds: $$(C\cap D)^\circ=C^\circ+ D^\circ$$.

Let $$P$$ be the cone of non-negative vectors. Apply this to $$P$$ and $$F$$. Assume that $$P\cap F=\{0\}$$. Then $$(P\cap F)^\circ =\mathbf{R}^n$$. Since $$P^\circ=P$$ and $$F^\circ=F^\bot$$, this yields $$P+F^\bot=\mathbf{R}^n$$. Fix any nonzero $$\xi\in P$$ (this requires $$n\ge 1$$ which I discretely added to the assumptions). Then $$-\xi=p+\eta$$ for some $$p\in P$$ and $$\eta\in F^\bot$$. Hence $$-\eta=p+\xi$$ is a nonzero element in $$P\cap F^\bot$$.

• Note that this works equally when $P$ is replaced with any self-dual cone.
– YCor
Oct 11, 2020 at 15:07
• In the same space, if for $d\geq 1$, $(F_i)_{1\leq i\leq d}$ are linear subspaces such that for $i\neq j$, $F_i\perp F_j$ and $\oplus_{1\leq i\leq d}F_i=\mathbb{R}^n$, is it possible to adapt this proof to find a non-null non-negative vector in one of these spaces? Oct 17, 2020 at 21:15
• @G.Panel No, in dimension 3 just rotate the three main axes by an orthogonal rotation of angle $\pi/3$ with axis the diagonal. That is, take $F_1,F_2,F_3$ as the lines spanned by $(-1,2,2)$, $(2,-1,2)$, $(2,2,-1)$.
– YCor
Oct 17, 2020 at 21:30

Yes. This follows from Farkas' lemma. Let $$\vec{v}_1$$, $$\vec{v}_2$$, ..., $$\vec{v}_k$$ be a basis of $$F$$ and let $$\vec{e}_1$$, $$\vec{e}_2$$, ..., $$\vec{e}_n$$ be the standard basis of $$\mathbb{R}^n$$. Suppose that there is no nonzero nonnegative vector in $$F^{\perp}$$. In other words, suppose there is no nonzero solution to the linear inequalities: $$\vec{v}_i \cdot \vec{x} = 0, \ 1 \leq i \leq k \qquad \qquad \vec{e}_j \cdot \vec{x} \geq 0, \ 1 \leq j \leq n.$$

Then Farkas' lemma tells us that there must be some linear relation $$\sum a_i \vec{v}_i + \sum b_j \vec{e}_j = 0$$ with nonnegative coefficients (and not all coefficients zero). Then $$- \sum a_i \vec{v}_i$$ is an element of $$F$$ with nonnegative entries. Moreover, we can't have $$- \sum a_i \vec{v}_i = 0$$, as the $$\vec{v}_i$$ are linearly independent and the $$\vec{e}_j$$ are as well.

• This argument should be rewritten more carefully; it is right in concept but needs work on the details. Oct 11, 2020 at 15:23

Would you like an elementary proof ? By this, I mean a calculus proof, one which does not invoque Hahn-Banach (Farkas Lemma involves HB).

Let $$P$$ be the orthogonal projector over $$F$$, and $$K$$ be the cone of non-negative vectors. Denote $$S$$ the unit sphere. The continuous function $$x\mapsto\|Px\|$$ achieves its maximum over the non-void compact subset $$S\cap K$$, at some vector $$a$$. It amounts to saying that $$a$$ maximizes $$f(x):=\frac{\|Px\|^2}{\|x\|^2}$$ over $$K\setminus\{0\}$$.

Comparing $$f(a)$$ with $$f(a+t\vec e_i)$$, we find that $$\partial_{x_i}f(a)$$ vanishes if $$a_i>0$$, and is $$\le0$$ if $$a_i=0$$. This gives either $$(Pa)_i=\lambda^2a_i$$, where $$\lambda=\|Pa\|/\|a\|\le1$$, or $$(Pa)_i\le0$$. We infer that the vector $$b:=a-Pa$$ belongs to $$K\cap F^\bot$$.

If $$b\ne0$$, we are done. If instead $$b=0$$, then $$a=Pa$$, meaning that $$a\in F$$, and we are done too.

The proof is similar when $$K$$ is replaced by a self-dual convex cone.

• It's a finite-dimensional Hahn-Banach that is used in the previous arguments, and this proved in roughly the same lines (still it's good to have the whole result starting from very basic level).
– YCor
Oct 15, 2020 at 16:25
• @YCor. I fully agree. My post doesn't raise any doubt about AC. It is just that even finite-dimensional HB is not taught in Calculus, at least in France. Oct 15, 2020 at 16:50
• Unless I missed something, fortunately in France we don't have any math course named with the depressing name "calculus" :) (But I see, it's not part of any of analysis//geometry 1st/2nd year course at least.)
– YCor
Oct 15, 2020 at 16:55

That is proved in Cor. 3', p. 309 of [1]. In fact, Cor. 3' is even stronger:

Let $$P$$ be the nonnegative cone.
If $$F\cap P=\{0\}$$, then $$F^\perp\cap P^o\ne\emptyset$$; i.e., $$v_n>0\ \forall n$$ for some $$v\in F^\perp$$.

[1] https://core.ac.uk/download/pdf/82596353.pdf Notes on Linear Inequalities, I: The intersection of the Nonnegative Orthant with Complementary Orthogonal Subspaces* ADI BEN-ISRAEL, JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS 9, 303-314 (1964)