Determinar si un vector está o no en un cono

Question

Determinar si el vector $\langle 0,7,3 \rangle$ pertenece al cono generado por

$$\langle 1,1,1\rangle \qquad \langle -1,2,1\rangle \qquad \langle 0,-1,1\rangle \qquad \langle 0,1,0\rangle$$

Es decir, se me pide que determine si $\langle 0,7,3 \rangle$ es una combinación lineal de los otros cuatro vectores de la lista. Tengo una solución (que ahora me doy cuenta que es no correcto) $$ \langle 0,7,3 \rangle=(2)\langle 1,1,1\rangle+(2)\langle -1,2,1\rangle+(-1)\langle 0,-1,1\rangle+(0)\langle 0,1,0\rangle. $$ Mi pregunta es más bien cómo podría establecer un sistema lineal de ecuaciones para la pregunta en cuestión. Podría meter varios vectores más y multiplicarlos todos por $0$ también para tener $\langle 0,7,3 \rangle$ en una variedad de conos, pero eso es bastante trivial (basta con multiplicar otros vectores por $0$ ). ¿Cómo podría configurar la pregunta original aquí como una matriz aumentada para poder reducir las filas de forma efectiva?

Pregunta: ¿Puede alguien encontrar pesos no negativos para $\langle 1,1,1\rangle$ , $\langle -1,2,1\rangle$ y $\langle 0,-1,1\rangle$ que dará $\langle 0,7,3 \rangle$ ?

Answer 1

El vector dado está en el cono dado si y sólo si el siguiente programa lineal es factible

$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & \begin{bmatrix} 1 & -1 & 0 & 0\\ 1 & 2 & -1 & 1\\ 1 & 1 & 1 & 0\end{bmatrix} \begin{bmatrix} t_1\\ t_2\\ t_3\\ t_4\end{bmatrix} = \begin{bmatrix} 0\\ 7\\ 3\end{bmatrix}\\ & t_1, t_2, t_3, t_4 \geq 0\end{array}$$

Afortunadamente, el problema es lo suficientemente baja dimensión que podemos abordar con álgebra lineal y no tenemos que recurrir a la programación lineal.

Utilizando SymPy, calculamos la RREF (forma escalonada reducida) de la matriz aumentada:

>>> from sympy import *
>>> M = Matrix([[1,-1, 0, 0, 0],
                [1, 2,-1, 1, 7],
                [1, 1, 1, 0, 3]])
>>> M.rref()
(Matrix([
[1, 0, 0,  1/5,  2],
[0, 1, 0,  1/5,  2],
[0, 0, 1, -2/5, -1]]), [0, 1, 2])

Así, el conjunto de soluciones es la línea parametrizada por

$$\begin{bmatrix} t_1\\ t_2\\ t_3\\ t_4\end{bmatrix} = \begin{bmatrix} 2\\ 2\\ -1\\ 0\end{bmatrix} + \gamma \begin{bmatrix} -\frac{1}{5}\\ -\frac{1}{5}\\ \frac{2}{5}\\ 1\end{bmatrix}$$

Si $\gamma \in \left[ \frac 52, 10 \right]$ obtenemos puntos en el octante no negativo. Eligiendo $\gamma = 5$ obtenemos

$$\begin{bmatrix} t_1\\ t_2\\ t_3\\ t_4\end{bmatrix} = \begin{bmatrix} 1\\ 1\\ 1\\ 5\end{bmatrix}$$

que no es negativo. Por lo tanto, el vector dado está efectivamente en el cono dado.

Answer 2

La idea es preguntar si existen $a,b,c$ tal que $(0,7,3)=a(1,1,1)+b(-1,2,1)+c(0,1,0)+d(0,-1,1)$ . Ahora coloquemos estos vectores en las columnas de una matriz tal que $ \begin{bmatrix} 1 & -1 & 0& 0& 0 \\ 1 & 2 & 1& -1& 7 \\ 1 & 1 & 0& 1& 3 \end{bmatrix} $

Ahora la idea es simplemente reducir la fila de esta matriz. Obsérvese que ponemos el vector que buscamos representar en la columna más a la derecha.

Answer 3

Vectores $\langle 1,1,1\rangle,\langle -1,2,1\rangle,\langle 0,-1,1\rangle$ son linealmente independientes, por lo que generan todo el $\mathbb{R}^3$ espacio.

Por la misma razón, podría haber utilizado $\langle -1,2,1\rangle,\langle 0,-1,1\rangle,\langle 0,1,0\rangle$ en su lugar.