1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – J. M.'s eventual burnout ♦
    May 24, 2020 at 17:03
  • 1
    $\begingroup$ @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. $\endgroup$
    – Lagrenge
    May 24, 2020 at 17:10
  • 1
    $\begingroup$ "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. $\endgroup$
    – J. M.'s eventual burnout ♦
    May 24, 2020 at 17:13
  • $\begingroup$ It boils down to a linear programming constraint satisfaction problem. $\endgroup$
    – Daniel Lichtblau
    May 24, 2020 at 20:23

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.