TransWikia.com

How to find efficiently all positive linear dependencies between some vectors

Mathematica Asked on January 9, 2021

I’ve got these vectors

vecs=
{{0,1,0,0,0,0,0,-1,0},    {1,-1,1,0,0,0,-1,1,-1},  {1,0,-1,1,0,-1,1,0,-1},
 {1,0,-1,1,0,0,-1,0,1},   {1,0,0,-1,0,1,0,0,-1},   {1,0,0,-1,1,-1,1,-1,1},
 {1,0,0,0,-1,0,0,1,0},    {-1,0,1,0,0,-1,1,0,-1},  {-1,0,1,0,0,0,-1,0,1},
 {-1,1,-1,1,-1,1,0,0,-1}, {-1,1,-1,1,0,-1,1,-1,1}, {-1,1,0,-1,0,1,0,-1,1}, 
 {-1,1,0,-1,1,-1,0,1,0},  {0,-1,0,0,1,0,0,0,-1},   {0,-1,0,1,-1,1,0,-1,1},
 {0,-1,0,1,0,-1,0,1,0},   {0,-1,1,-1,0,1,-1,1,0},  {0,0,-1,0,0,0,1,0,0}}

And I would like to find all linear dependencies with positive coefficients between them. I started with

ns = NullSpace[Transpose[vecs]] 

which gave me

{{2,2,-1,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,3},  {2,-1,2,0,-1,0,0,0,0,0,0,0,0,0,0,0,3,0}, 
 {2,-1,-1,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0},  {1,1,1,0,1,0,0,0,0,0,0,0,3,0,3,0,0,0}, 
 {2,-1,-1,0,-1,0,3,0,0,0,0,0,0,3,0,0,0,0}, {-1,2,2,0,-1,0,0,0,0,0,0,3,0,0,0,0,0,0}, 
 {-1,2,-1,0,2,0,0,0,0,0,3,0,0,0,0,0,0,0},  {-1,2,-1,0,-1,3,0,0,0,3,0,0,0,0,0,0,0,0}, 
 {-1,-1,2,0,2,0,0,0,3,0,0,0,0,0,0,0,0,0},  {-1,-1,-1,3,2,0,0,3,0,0,0,0,0,0,0,0,0,0}}

so there is one linear dependence with nonnegative coefficients (the fourth one). To check whether there are others, I made a system of inequalities with

ineqs = Simplify[Union[Map[# >= 0 &, Table[x[k], {k, Length[ns]}].ns]]]

which returns

{x[1]>=0,x[2]>=0,x[3]>=0,x[4]>=0,x[5]>=0,x[6]>=0,x[7]>=0,x[8]>=0,x[9]>=0,x[10]>=0,
 2 x[1]+2 x[2]+2 x[3]+x[4]+2 x[5] >= x[6]+x[7]+x[8]+x[9]+x[10],
 2 x[1]+x[4]+2 (x[6]+x[7]+x[8])   >= x[2]+x[3]+x[5]+x[9]+x[10],
 2 x[2]+x[4]+2 (x[6]+x[9])        >= x[1]+x[3]+x[5]+x[7]+x[8]+x[10],
 2 x[3]+x[4]+2 (x[7]+x[9]+x[10])  >= x[1]+x[2]+x[5]+x[6]+x[8]}

but my notebook runs out of memory on both Solve[ineqs] and Reduce[ineqs].

What is the proper way?

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP