This question is inspired by another MO question about special stratifications of equivariant Grassmannians, that turned out to be a problem of computing non-trivial circuits in a vector matroid. To review, a vector matroid is just a list of vectors or lines in $\mathbb{F}^n$ for a field $\mathbb{F}$, and a "circuit" is a linearly dependent set of vectors. The information in the matroid is exactly the combinatorial information in the set of circuits, or for that matter the set of minimal circuits. (But, matroids are defined by axioms and there are matroids that don't come from a list of vectors in a vector space.)

In response to the question, I computed some vector matroids in Sage. David Joyner's Sage code for this purpose is based on exhaustive searches for the minimal circuits. Of course, every set of $n+1$ vector is a circuit, so you can stop the search at subsets of $n$ vectors. Of course, in searching for minimal circuits, you never need to check a superset of a known circuit. But otherwise I couldn't think of any better algorithm than exhaustive search. Consider especially the difficult case in which there are no circuits of size less than $n$. If there are $v$ vectors total, you would have to search over all $\binom{v}{n}$ sets of $n$ vectors.

I can think of one small acceleration that is still basically an exhaustive search. If you have guessed $k < n$ vectors, you can put the vectors that you have in reduced echelon form, to avoid repeated work when you assume more vectors. You can also use those vectors to reduce the remaining vectors that you haven't yet chosen. This saves a factor of $O(n^2)$ if you had planned to use Gaussian elimination to see if each set of $n$ vectors is linearly dependent. You can even use this method to incrementally compute all $\binom{v}{n}$ determinants.

Is there any better algorithm known? For simplicity suppose that the field is $\mathbb{Q}$, and the vectors are all rescaled to integer vectors. I would guess that it is NP-hard to determine if there are any linear dependencies. If so, then NP-hardness is not the main part of my question. Because, for example, computing the permanent of a matrix is #P-hard, but there is an interesting acceleration: The naive algorithm takes $\tilde{O}(n!)$ time, but there as an important algorithm that works in time $\tilde{O}(2^n)$.

regimefor the present problem, even though I suspect that it is NP-hard in other regimes. $\endgroup$ – Greg Kuperberg Feb 10 '11 at 6:31