# How to find all minimal dependent sets of a set of vectors effectively?

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.

• Keyword: matroid algorithms. For example, link.springer.com/chapter/10.1007/978-3-540-24587-2_50 Sep 29 '19 at 10:20
• I bowlegged you may find this implemented in sage, the matroid pack Sep 29 '19 at 15:12
• @FrançoisG.Dorais: This is probably a naive question, but how can matroid algorithms be faster than doing actual linear algebra? Sep 30 '19 at 4:21
• @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. Sep 30 '19 at 14:49

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.

• 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? Sep 30 '19 at 6:41
• 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. Oct 6 '19 at 22:17
• thank you very much. Oct 25 '19 at 6:04