An algorithm to find non-trivial linear dependencies

Question

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)$.

Answer 1

I am not quite sure what precisely your question is. But I'll assume that it is this: Given a set of $v$ vectors inside $F^n$, what is the complexity of computing the set of all minimal circuits in the set of vectors?

Now note that complexity depends on what one considers to be the input size. In this case, one cannot just look at $n$, rather $v$ must be taken into account, too. For one can construct arbitrarily large sets where every subset of size $n$ forms a basis (e.g. for $n=2$, take the set of vectors $(1,x)$ where $x$ is arbitrary). So then minimal circuits are precisely the subsets of size $n+1$. Hence the output size is $\binom{v}{n+1}$. For fixed $n$ this is clearly unbounded as $v$ increases. Therefore the complexity can't even be in $O(2^n)$, or in $O(f(n))$ for any real-valued function $f$.

On the other hand, if you consider only $v$ as input and assume $n$ to be fixed, then exhaustive search involves computing the determinant of a number of matrices. The exact number is bounded above by $\sum_{i=2}^n \binom{v}{i}$, which is a polynomial in $v$ of degree $n$. Hence the complexity of this approach is in $O(v^n)$ (we can neglect the time to compute the determinants, as it only depends on $n$, which here is a constant).

This is also essentially the answer (modulo a now non-constant factor for computing the determinants) if you consider both $v$ and $n$ as input sizes, by the example above: Since the output can have size $\binom{v}{n+1}$, there can't be an algorithm asymptotically "faster" than $O(v^n)$.

You may want to argue that one can modify the output, e.g. by not outputting the minimal circuits of size $n+1$ (these can be easily identified if all smaller minimal circuits are known). But that won't help, as you can e.g. construct examples where the minimal circuits are all subsets of size $k$, for any $2\leq k\leq n+1$.

Answer 2

There are results pertaining to the finite field case. According to this paper, for a finite field $F_q$ and a set of $r$ points $x_1,\dotsc,x_r\in F_q^n$ deciding whether there exists a subset of $k$ dependent points among them is NP-complete and requires $poly(n)\min(\binom{r}{k}, q^{\Theta(n+k^2)})$ time (assuming 3-SAT requires exponential time).

The algorithm for $q^{\Theta(n+k^2)}$ part is based on FFT. Moreover, the algorithm not only checks existence, but also counts the solutions (approximates — in the case of minimal dependent $k$-subsets, i.e. circuits). Also, one can find a specific solution by running the algorithm on sequentially increased inputs and paying overhead of $O(rk)$.