# 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? – J. M.'s technical difficulties May 24 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. – Lagrenge May 24 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. – J. M.'s technical difficulties May 24 at 17:13
• It boils down to a linear programming constraint satisfaction problem. – Daniel Lichtblau May 24 at 20:23

## 1 Answer

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 *)
FindInstance[Join[Thread[cc.V == v], Thread[cc >= 0]], cc]
(*    {{c[1] -> 0.570869, c[2] -> 0., c[3] -> 0.264421, c[4] -> 0.167536}}    *)

cc /. First[%]    (* extract the coefficients *)
(*    {0.570869, 0., 0.264421, 0.167536}    *)


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