0
$\begingroup$

In my research, I need to find the set of all minimal dependent sets of a given set of vectors. One method is to check every subset of the given set. But this method is very slow when the set of vectors is large. For example, let $S$ be the set of all positive roots of type $B_5$ root system. Then $S$ consists of the following vectors \begin{align} &a_5, \quad a_4+2 a_5, \quad a_4+a_5, \quad a_3+a_4+2 a_5, \quad a_3+2 a_4+2 a_5, \\ &a_3+a_4+a_5, \quad a_2+a_3+a_4+2 a_5, \quad a_2+a_3+2 a_4+2 a_5, \quad a_2+2 a_3+2 a_4+2 a_5, \\ &a_2+a_3+a_4+a_5, \quad a_1+a_2+a_3+a_4+2 a_5, \quad a_1+a_2+a_3+2 a_4+2 a_5, \\ &a_1+a_2+2 a_3+2 a_4+2 a_5, \quad a_1+2 a_2+2 a_3+2 a_4+2 a_5, \quad a_1+a_2+a_3+a_4+a_5, \\ &a_4, \quad a_3+a_4, \quad a_2+a_3+a_4, \quad a_1+a_2+a_3+a_4, \quad a_3, \\ &a_2+a_3, \quad a_1+a_2+a_3, \quad a_2, \quad a_1+a_2, \quad a_1, \end{align} where $a_i$'s are simple roots.

I let the computer run for one day but didn't get the result. Is there some effective method to compute all minimal dependent sets of a given set of vectors? Could this be done in Sage or Maple or other software? Thank you very much.

$\endgroup$
  • 2
    $\begingroup$ Keyword: matroid algorithms. For example, link.springer.com/chapter/10.1007/978-3-540-24587-2_50 $\endgroup$ – François G. Dorais Sep 29 at 10:20
  • $\begingroup$ I bowlegged you may find this implemented in sage, the matroid pack $\endgroup$ – Joao Costalonga Sep 29 at 15:12
  • $\begingroup$ @FrançoisG.Dorais: This is probably a naive question, but how can matroid algorithms be faster than doing actual linear algebra? $\endgroup$ – Sam Hopkins Sep 30 at 4:21
  • 1
    $\begingroup$ @SamHopkins: For vector matroids, the matroid algorithms use linear algebra in the background. The matroid properties are used to find all minimal circuits in polynomial time rather than searching all possible subsets. $\endgroup$ – François G. Dorais Sep 30 at 14:49
3
$\begingroup$

Install a recent version of Macaulay2. Open a Macaulay2 session in a terminal and issue the commands below (the ones starting with "i" for input).

i1 : loadPackage "Matroids" 

i2 : M = matroid transpose matrix {{0,0,0,0,1}, {0,0,0,1,2}, {0,0,0,1,1}, {0,0,1,1,2}, {0,0,1,2,2}, {0,0,1,1,1}, {0,1,1,1,2}, {0,1,1,2,2}, {0,1,2,2,2}, {0,1,1,1,1}, {1,1,1,1,1}, {1,1,1,2,2}, {1,1,2,2,2}, {1,2,1,2,2}, {1,1,1,1,1}, {0,0,0,1,0}, {0,0,1,1,0}, {0,1,1,1,0}, {1,1,1,1,0}, {0,0,1,0,0}, {0,1,1,0,0}, {1,1,1,0,0}, {0,1,0,0,0}, {1,1,0,0,0}, {1,0,0,0,0}}

o2 = a matroid of rank 5 on 25 elements

o2 : Matroid

i3 : time circuits M
     -- used 9.12867 seconds

o3 = {set {0, 1, 2}, set {0, 1, 3, 4}, set {0, 2, 3, 4}, set {1, 2, 3, 4}, set {0, 3, 5}, set {1, 2, 3, 5}, set {0, 1, 4, 5}, set {2, 4, 5}, set {1, 3, 4, 5},
     ---------------------------------------------------------------------------------------------------------------------------------------------------------
     set {0, 1, 6, 7}, set {0, 2, 6, 7}, set {1, 2, 6, 7}, set {3, 4, 6, 7}, set {1, 3, 5, 6, 7}, set {2, 3, 5, 6, 7}, set {0, 4, 5, 6, 7}, set {1, 4, 5, 6,
     ---------------------------------------------------------------------------------------------------------------------------------------------------------
     7}, set {0, 3, 6, 8}, set {1, 2, 3, 6, 8}, set {1, 4, 6, 8}, set {0, 2, 4, 6, 8}, set {2, 3, 4, 6, 8}, set {0, 5, 6, 8}, set {1, 2, 5, 6, 8}, set {3, 5,
     ---------------------------------------------------------------------------------------------------------------------------------------------------------
     6, 8}, set {1, 3, 7, 8}, set {0, 2, 3, 7, 8}, set {0, 1, 4, 7, 8}, set {2, 4, 7, 8}, set {0, 3, 4, 7, 8}, set {0, 1, 5, 7, 8}, set {2, 5, 7, 8}, set {4,
     ---------------------------------------------------------------------------------------------------------------------------------------------------------
     5, 7, 8}, set {2, 3, 6, 7, 8}, set {0, 4, 6, 7, 8}, set {1, 5, 6, 7, 8}, set {0, 6, 9}, set {1, 2, 6, 9}, ...

i4 : # circuits M

o4 = 12181     

The matroid in i2 is the vector matroid of the matrix whose columns are the 25 (coefficients of the) given vectors and the 12181 circuits of the matroid are computed in fewer than 10 seconds.

$\endgroup$
  • $\begingroup$ thank you very much. Denote by $x_1, \ldots, x_{25}$ the $25$ vectors. How to store the 12181 circuits in a text file? What does "o3" represented in your codes? $\endgroup$ – Jianrong Li Sep 30 at 6:41
  • $\begingroup$ The gray code above is a copy/paste from an actual Macaulay2 session. i3 is the third input while o3 is the corresponding output. See this page for writing to files. $\endgroup$ – Aaron Dall Oct 6 at 22:17
  • $\begingroup$ thank you very much. $\endgroup$ – Jianrong Li Oct 25 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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