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.



How to find all minimal dependent sets of a set of vectors effectively?
Install a recent version of [Macaulay2](http://www2.macaulay2.com/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. 


