1
$\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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Keyword: matroid algorithms. For example, link.springer.com/chapter/10.1007/978-3-540-24587-2_50 $\endgroup$
    – François G. Dorais
    Commented Sep 29, 2019 at 10:20
  • $\begingroup$ I bowlegged you may find this implemented in sage, the matroid pack $\endgroup$
    – Joao Costalonga
    Commented Sep 29, 2019 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
    Commented Sep 30, 2019 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
    Commented Sep 30, 2019 at 14:49

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Sep 30, 2019 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
    Commented Oct 6, 2019 at 22:17
  • $\begingroup$ thank you very much. $\endgroup$
    – Jianrong Li
    Commented Oct 25, 2019 at 6:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .