7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @gmvh this has nothing to do with rings-and-algebras, which you added. $\endgroup$
    – YCor
    Oct 11, 2020 at 11:14
  • $\begingroup$ ... but the key is to use convex geometry (this is why I added the tag). $\endgroup$
    – YCor
    Oct 11, 2020 at 11:23
  • $\begingroup$ @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? $\endgroup$
    – gmvh
    Oct 11, 2020 at 12:07
  • 1
    $\begingroup$ @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) $\endgroup$
    – YCor
    Oct 11, 2020 at 12:14

4 Answers 4

8
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Note that this works equally when $P$ is replaced with any self-dual cone. $\endgroup$
    – YCor
    Oct 11, 2020 at 15:07
  • $\begingroup$ 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? $\endgroup$
    – G. Panel
    Oct 17, 2020 at 21:15
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – YCor
    Oct 17, 2020 at 21:30
5
$\begingroup$

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.

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

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – YCor
    Oct 15, 2020 at 16:25
  • $\begingroup$ @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. $\endgroup$ Oct 15, 2020 at 16:50
  • $\begingroup$ 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.) $\endgroup$
    – YCor
    Oct 15, 2020 at 16:55
0
$\begingroup$

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)

$\endgroup$

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.