# How to check positive linear dependence of vectors/matrices?

Suppose I have a bunch of vectors or matrices $$v,v_1,v_2,\ldots, v_n$$, living in an $$N$$ dimensional linear space. How to check (using mathematica) if $$v$$ is positively dependent on the set $$\{v_1,v_2,\ldots,v_n\}$$ ($$v$$ lives in the "convex cone" or "positive cone" spanned by $$\{v_1,\ldots,v_n\}$$)? That is, does there exists non-negative real numbers $$c_1,c_2,\ldots c_n\geq 0$$ such that $$v=\sum^n_{i=1}c_i v_i.$$ Also, if such nonnegative coefficients exists (possibly not unique), how to find them (just one possible solution is OK)?

• 1. Couldn't you just check the rank of $(v_1, v_2, \dots, v_n,v)$? 2. Would it not do to just solve the implied linear equation by your sum, and then check that the components of the solution vector are all nonnegative? May 24, 2020 at 17:03
• @J.M. That $v$ is linearly dependent on $\{v_1,\ldots,v_n\}$ does not necessarily mean they are positively dependent, so matrix rank doesn't help much~(of course they cannot be positively dependent if they are not even linearly dependent, but in my case linear dependence is guaranteed). There can be infinitely many solutions, and I don't know how to determine if there is one that has non-negative coordinates. May 24, 2020 at 17:10
• "in my case linear dependence is guaranteed" - then you should perhaps emphasize this in your question. The only further suggestion I can give is to use something like Reduce[]. Actually, now that I think about it, it seems this could be recast as an LP problem; you'd just have to check that the appropriate minimum value is zero. May 24, 2020 at 17:13
• It boils down to a linear programming constraint satisfaction problem. May 24, 2020 at 20:23

You can find one possible solution with FindInstance.

For example, operating in $$N$$=m dimensions (as N is a reserved keyword in Mathematica) and using n vectors,

m = 3;
n = 4;

V = RandomVariate[NormalDistribution[], {n, m}]  (* the vectors v_i *)
(*    {{0.512956, -2.44836, 1.64427},
{0.893093, -1.62577, -0.0144412},
{1.2746, 0.678006, -1.75192},
{0.844172, 0.8864, 0.615265}}    *)

v = RandomVariate[NormalDistribution[], m]       (* the target vector v *)
(*    {0.771292, -1.06991, 0.578498}    *)

cc = Array[c, n];  (* the unknowns *)

If FindInstance returns an empty list {} then there is no solution.