7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dominique Mar 1 '13 at 16:47
  • $\begingroup$ but how do you make sure that none of the coefficients of this linear combination is less than $0$? $\endgroup$ – born Mar 1 '13 at 18:46
  • 2
    $\begingroup$ Just a thought: I think you are looking at a version of caratheodory's theorem. $\endgroup$ – dineshdileep Mar 1 '13 at 21:33
2
$\begingroup$

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$

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