Determining whether or not a vector is in a cone

Question

Determine whether or not the vector $\langle 0,7,3 \rangle$ belongs to the cone generated by

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

That is, I am asked to determine whether or not $\langle 0,7,3 \rangle$ is a linear combination of the other four listed vectors. I have a solution (which I now realize is not correct) $$ \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. $$ My question is more so how would I set up a linear system of equations for the question at hand? I could throw in several more vectors and multiply them all by $0$ as well to have $\langle 0,7,3 \rangle$ in a variety of cones, but that is rather trivial (just multiplying other vectors by $0$). How would I set up the original question here as an augmented matrix so I could row reduce it effectively?

Question: Can anyone find nonegative weights for $\langle 1,1,1\rangle$, $\langle -1,2,1\rangle$, and $\langle 0,-1,1\rangle$ that will give $\langle 0,7,3 \rangle$?

Answer 1

The given vector is in the given cone if and only if the following linear program is feasible

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

Fortunately, the problem is sufficiently low-dimensional that we can tackle it with linear algebra and do not have to resort to linear programming.

Using SymPy, we compute the RREF (reduced row echelon form) of the augmented matrix:

>>> 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])

Thus, the solution set is the line parametrized by

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

If $\gamma \in \left[ \frac 52, 10 \right]$, we obtain points in the nonnegative octant. Choosing $\gamma = 5$, we obtain

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

which is nonnegative. Thus, the given vector is indeed in the given cone.

Answer 2

The idea is to ask whether exist $a,b,c$ such that $(0,7,3)=a(1,1,1)+b(-1,2,1)+c(0,1,0)+d(0,-1,1)$. Now let's place these vectors in the columns of a matrix such that $ \begin{bmatrix} 1 & -1 & 0& 0& 0 \\ 1 & 2 & 1& -1& 7 \\ 1 & 1 & 0& 1& 3 \end{bmatrix} $

Now the idea is to simply row reduce this matrix. Note that we put the vector that we're looking to represent on the right most column.

Answer 3

Vectors $\langle 1,1,1\rangle,\langle -1,2,1\rangle,\langle 0,-1,1\rangle$ are linearly independent, so they generate the whole $\mathbb{R}^3$ space.

By the same reason, you might have used $\langle -1,2,1\rangle,\langle 0,-1,1\rangle,\langle 0,1,0\rangle$ instead.