Can an element of a finitely generated cone be expressed as a conic combination of a linearly independet subset?

176 Views Asked by At

Given a finite family of vectors $A = \{a_1,\dots,a_k\}$ in $\mathbb R^n$ let $\operatorname{cone}(A)$ be their conical hull - the set of vectors $b$ that can be written as a nonnegative linear combination of the $a_i$: $b = \sum_{i=1}^k x_i a_i$, $x_i \ge 0$.

Let $A= \{a_1,\dots, a_k\} \subset \mathbb R^n$ be given and let $C = \operatorname{cone}(A)$.Take some $b \in C$.

Question: Is it in general possible to express $b$ as a conical combination of a linearly independent subset $A_b$ of $A$?

Visually it seems clear that this should be possible but my proof efforts have not been successful so far.

1

There are 1 best solutions below

0
On BEST ANSWER

I found a proof, the statement holds for any $b \ne 0$.

Suppose $b \ne 0$ can be expressed as a conic combination of the $a_i$, wlog suppose $$ b = \sum_{i=1}^l x_i a_i $$ with $l \ge 1$ and $x_i > 0 \, \forall i$.

If the $a_1,\dots,a_l$ are l.i. we are done; otherwise there exist nontrivial numbers $\mu_i$ s.t. $0 = \sum_{i=1}^l \mu_i a_i$. Then for any number $\lambda$, $$ b = \sum_{i=1}^l (x_i - \lambda \mu_i) a_i. $$

Pick $\lambda$ maximal such that $x_i - \lambda \mu_i \ge 0 \, \forall i$. Then these new coefficients are nonnegative and at least one of them is zero. Hence $b$ is a conic combination of at most $l-1$ of the $a_i$. After finitely many steps we get a linearly independent subset.