Acotar el número de coeficientes no nulos en una combinación cónica

Question

Estoy buscando una prueba para el siguiente enunciado con el fin de entender una prueba sobre la programación de números enteros que estoy leyendo.

Vectores dados $x_1, \ldots, x_s \in \mathbb R^n$ , coeficientes no negativos $\lambda_1, \ldots, \lambda_s \in \mathbb R_{\geq 0}$ y un vector $v = \sum_{i=1}^s \lambda_i x_i$ entonces existen coeficientes $\lambda_1', \ldots, \lambda_s' \in \mathbb R_{\geq 0}$ de los cuales como máximo $n$ son distintos de cero con $v = \sum_{i=1}^s \lambda_i' x_i$ .

En otras palabras: dado un conjunto finito $B$ de vectores reales, cada vector del cono poliédrico generado por $B$ puede escribirse como una combinación cónica de como máximo $n$ vectores de $B$ .

Answer 1

Gracias a dineshdileep El comentario de la Sra. B. de la casa de la familia de la que es miembro, me ha llevado a ver Teorema de Caratheodory y su demostración y lo adaptó a una afirmación sobre conos poliédricos en lugar de politopos:

Propuesta: Dejemos que $x_1, \ldots, x_s \in \mathbb R^n$ , $\lambda_1, \ldots, \lambda_s \in \mathbb R_{\geq 0}$ y $v = \sum_{i=1}^s \lambda_i x_i$ . Entonces hay $\lambda'_i \geq 0$ con $v = \sum_{i=1}^s \lambda'_i x_i$ y como máximo $n$ de la $\lambda_i'$ son distintos de cero.

Prueba: Sin pérdida de generalidad, supongamos que $\lambda_i > 0$ para todos $i = 1, \ldots, s$ . Si $s \leq n$ no hay nada que probar, así que dejemos $s > n$ . Entonces el conjunto $\{\, x_i \mid i = 1, \ldots, s \,\}$ es linealmente dependiente. Con $\mu_1, \ldots, \mu_s \in \mathbb R$ dejar $\sum_{i=1}^s \mu_i x_i = 0$ sea una combinación lineal no trivial de cero. Sea

$$k := \mathop{\text{arg min}}_{i = 1, \ldots, s} \;\left\{\, \left|\frac{\lambda_i}{\mu_i}\right| : \mu_i \neq 0 \,\right\} $$ y $\alpha := \frac{\lambda_j}{\mu_j}$ . Para todos los $i = 1, \ldots, s$ tenemos

$$\lambda_i - \alpha \mu_i = \lambda_i - \mathop{\text{sgn}}(\mu_i \mu_k) \left| \frac{\lambda_k}{\mu_k} \mu_i \right| $$ y dos casos:

\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}

Por lo tanto, para $i = 1, \ldots, s$ tenemos $\lambda_i' := \lambda_i - \alpha \mu_i \geq 0$ y en particular $\lambda'_k = 0$ .

Repitiendo esto un número finito de veces se completa la prueba. $\square$