Solving linear programming without solving linear programming Let $v_1, \cdots, v_n$ be vectors in $\mathbb R^k$, and let $M$ be the Gram matrix of them.
It's possible to determine from $M$ and $k$ whether the only vector that has nonnegative inner product with every $v_m$ is the zero vector. This is because $M$ determines $v_1, \cdots, v_n$ up to orthogonal transformations.
Nevertheless, the process of determining is as hard as linear programming. With this in mind, my question is:
Question: Are there sufficient conditions on $M$ and $k$ to ensure that the zero vector is the only vector that has nonnegative inner product with every $v_m$, without using linear programming?
What I would expect as answers are analytic conditions on the matrix $M$ and $k$ without quantifiers for any fixed $n$ and $k$.
Example: Assume $n=k+1$, and $X$ is the $n$-dimensional matrix with positive elements on the diagonal and negative elements elsewhere. Then $X$ as a Gram matrix satisfies the property.
 A: $\newcommand\R{\mathbb R}$Suppose that $\det M_{J,J}\ne0$ for some set $J\subseteq[n]:=\{1,\dots,n\}$ of cardinality $|J|=k$, where $M_{J,J}:=(v_i\cdot v_j\colon (i,j)\in J\times J)$, the $(J\times J)$-submatrix of the Gram matrix $M$. Suppose also that $Mc=0$ for some $c=[c_1,\dots,c_n]^\top\in\mathbb R^n$ such that $c_j\ge0$ for all $j\in[n]$ and $c_j>0$ for all $j\in J$.
Then the zero vector is the only vector that has nonnegative inner product with every $v_i$.

Indeed, let $v:=\sum_{j\in[n]}c_j v_j\in\R^k$. Then
$$v_i\cdot v=\sum_{j\in[n]}c_j v_i\cdot v_j=(Mc)_i=0 \tag{1}\label{1}$$
for all $i\in[n]$. Since $\det M_{J,J}\ne0$ and $|J|=k$, the rank of the Gram matrix $M$ is $\ge k$. That is, the rank of the system $(v_1,\dots,v_n)$ of vectors is $\ge k$ (so, in fact, $=k$). So, by \eqref{1},
$$0=v=\sum_{j\in[n]}c_j v_j\in\R^k.\tag{2}\label{2}$$
Take now any $w\in\R^k$ such that $w\cdot v_j\ge0$ for all $j\in[n]$. By \eqref{2},
$$0=\sum_{j\in[n]}c_j w\cdot v_j.\tag{3}\label{3}$$
Since $c_j\ge0$ for all $j\in[n]$, all the summands in the sum in \eqref{3} are $\ge0$ and therefore $=0$. Since $c_j>0$ for all $j\in J$, it follows that $w\cdot v_j=0$ for all $j\in J$. But the rank of the system $(v_j\colon j\in J)$ of vectors is the same as the rank of $M_{J,J}$, which latter is $k$. We conclude that $w=0$, as claimed.

Letting $c_j=1$ for all $j\in[n]$ and taking any subset $J$ of $[n]$ of cardinality $k$, we see that the sufficient conditions given in beginning of this answer generalize the conditions in your Example.
I think it should be not hard to show that these sufficient conditions are also necessary. However, since you asked only for sufficient conditions, this addition should be the subject of another question, perhaps posted elsewhere.
