# Bounding the number of nonzero coefficients in a conic combination

I'm looking for a proof for the following statement in order to understand a proof about integer programming I'm reading.

Given vectors $x_1, \ldots, x_s \in \mathbb R^n$, nonnegative coefficients $\lambda_1, \ldots, \lambda_s \in \mathbb R_{\geq 0}$ and a vector $v = \sum_{i=1}^s \lambda_i x_i$, then there exist coefficients $\lambda_1', \ldots, \lambda_s' \in \mathbb R_{\geq 0}$ of which at most $n$ are nonzero with $v = \sum_{i=1}^s \lambda_i' x_i$.

In other words: given a finite set $B$ of real vectors, every vector in the polyhedral cone generated by $B$ can be written as a conical combination of at most $n$ vectors of $B$.

• If $s \geq n$ and more than $n$ $\lambda$'s are nonzero, you're writing a linear combination of more than $n$ vectors in $R^n$. Those vectors cannot be linearly independent. So you can remove some of them and still generate the same cone. – Dominique Mar 1 '13 at 16:47
• but how do you make sure that none of the coefficients of this linear combination is less than $0$? – born Mar 1 '13 at 18:46
• Just a thought: I think you are looking at a version of caratheodory's theorem. – dineshdileep Mar 1 '13 at 21:33

Thanks to dineshdileep's comment I had a look at Caratheodory's theorem and its proof and adapted it to a statement about polyhedral cones instead of polytopes:

Proposition: Let $x_1, \ldots, x_s \in \mathbb R^n$, $\lambda_1, \ldots, \lambda_s \in \mathbb R_{\geq 0}$ and $v = \sum_{i=1}^s \lambda_i x_i$. Then there are $\lambda'_i \geq 0$ with $v = \sum_{i=1}^s \lambda'_i x_i$ and at most $n$ of the $\lambda_i'$ are nonzero.

Proof: Without loss of generality, assume that $\lambda_i > 0$ for all $i = 1, \ldots, s$. If $s \leq n$, there is nothing to proof, so let $s > n$. Then the set $\{\, x_i \mid i = 1, \ldots, s \,\}$ is linearly dependent. With $\mu_1, \ldots, \mu_s \in \mathbb R$ let $\sum_{i=1}^s \mu_i x_i = 0$ be a nontrivial linear combination of zero. Let

$$k := \mathop{\text{arg min}}_{i = 1, \ldots, s} \;\left\{\, \left|\frac{\lambda_i}{\mu_i}\right| : \mu_i \neq 0 \,\right\}$$ and $\alpha := \frac{\lambda_j}{\mu_j}$. For all $i = 1, \ldots, s$, we have

$$\lambda_i - \alpha \mu_i = \lambda_i - \mathop{\text{sgn}}(\mu_i \mu_k) \left| \frac{\lambda_k}{\mu_k} \mu_i \right|$$ and two cases:

\begin{cases} \lambda_i - \alpha \mu_i \geq \lambda_i \hphantom{{}- \frac{\lambda_i}{\mu_i}{\mu_i}} \geq 0 & \mathop{\text{sgn}}(\mu_i \mu_k) = -1 \\ \lambda_i - \alpha \mu_i \geq \lambda_i - \frac{\lambda_i}{\mu_i}{\mu_i} = 0 & \mathop{\text{sgn}}(\mu_i \mu_k) = \hphantom{-{}}1. \end{cases}

Therefore for $i = 1, \ldots, s$ we have $\lambda_i' := \lambda_i - \alpha \mu_i \geq 0$ and in particular $\lambda'_k = 0$.

Repeating this a finite number of times completes the proof. $\square$