# An algorithm to find non-trivial linear dependencies

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

-
The PSLQ algorithm is used to find (probable) linear dependencies - the context is somewhat different, but if you're not familiar with the algorithm, it may be worth your while to have a look at it. Also, the LLL algorithm is used to find shortest vectors in a lattice, but if the input vectors are linearly dependent I suppose it finds the zero vector, so it might also be worth a shot. – Gerry Myerson Feb 8 '11 at 22:49
@Gerry Actually both of these algorithms pertain to integer dependencies. If you use them for linear dependencies over a field, then without some new idea, they work very hard just to do something easy. – Greg Kuperberg Feb 9 '11 at 12:55
@Greg, of course you're right - but in the last paragraph of the question, the field is the rationals, and there's a rational dependence if and only if there's an integer dependence. I can't reconcile your saying that finding linear dependencies over a field is easy with your guess that it's NP-hard to determine whether there are any linear dependencies. What am I missing? – Gerry Myerson Feb 9 '11 at 23:51
@Gerry It's a point that also confused me for a while in this case. The answer is that a problem can have more than one regime. The lattice problem is already hard when there are no linear dependencies and $v=n$; in fact that's the standard case. But this is a trivial regime for the present problem, even though I suspect that it is NP-hard in other regimes. – Greg Kuperberg Feb 10 '11 at 6:31
The circuits of a matroid are the minimal dependent sets. What you are calling circuits are the dependent sets of the matroid. This is consistent with the motivation from graph theory, where a circuit is what you think it is. – Andy B Jun 8 '11 at 16:07

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

-
Max makes a good point, the running time can't be faster than the time to output the answer. On the other hand if the answer is "all the sets of size n+1" that is short and perhaps you could find it quickly. Maybe it depends on having a special form to the set of vectors. If a group acts on the set of vectors then one can look at the orbits on the subsets. Certainly one could use a Gray code to run through subsets switching in and out one thing at a time. (cont) – Aaron Meyerowitz Feb 9 '11 at 5:18
Suppose one happens to have a found that a certain set (like half the vectors) are in general position in that any $n$ are independent, I wonder if that can be exploited for a speed up. Projection into subspaces might help focus a search, but I don't clearly see how. – Aaron Meyerowitz Feb 9 '11 at 5:19
This is the question, except that I am interested in an abbreviated output that only lists the non-trivial minimal circuits. Call a minimal circuit trivial if it has cardinality $n+1$. You know that if none of its subsets are a circuit, then it is a circuit, so there is no need to produce it. Also, yes I know that the output could still be long, but let's rate the performance of the algorithm as a function of the length of the input plus the output. – Greg Kuperberg Feb 9 '11 at 9:16
As I said in the last paragraph of my answer: You can generate examples were the minimal circuits are all subsets of size $n$. So none of them is "trivial" in your notation, but you still have an exponential number of them. So, the problem remains exponential in the general case. Of course, for special cases, were you know the output is small, you may be able to find a solution very quickly. But that's not unusual; factoring numbers into prime factors is also in general hard, but there are numbers which are trivial to factor (e.g. primes, which can be recognized as such in polynomial time). – Max Horn Feb 9 '11 at 10:07
To elaborate some more: I tis fairly easy to catch the examples where all the minimal circuits are small, say of bounded maximal size $k$. And likewise, it is fairly easy to handle the case where all minimal circuits are big, say of size at least $n-k$. But as $n$ increases, you can construct examples where the minimal circuits are of approximately size $n/2$, and then there is no "easy" way to find them, and you still get exponential output, no matter how clever you encode it. – Max Horn Feb 9 '11 at 10:09

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

-