Path: muir.math.niu.edu!fnnews.fnal.gov!uwm.edu!math.ohio-state.edu!howland.reston.ans.net!ix.netcom.com!netcom.com!jgk From: Joe Keane Subject: finding linear dependence Message-ID: Summary: How to do it? Keywords: matrix The following is a problem that i've been working on for a while, and i'd appreciate any suggestions or references on how to do it well. Basically, i have a large collection of vectors, and i want to find out if one can be expressed as a linear combination of a few of the others. Clearly, once the number of vectors is greater than their dimension, there must be some linear dependence, but that isn't interesting to me. The components of the vectors are rational numbers, so all operations are exact, but these numbers can be fairly complicated, and arithmetic operations can take a long time, that is, milliseconds instead of the usual tens of cycles for native integers or floating-point numbers. The algorithm that i use now is slightly more clever than brute force, but it seems like there should be some fairly efficient way to do this. One thought i had is that there could be some method similar to hashing to find combinations that *might* be linearly dependent, then we can always go back and check those with the exact arithmetic. To put some concrete numbers behind this, i have roughly a thousand vectors, each one has maybe ten or twenty components, and i'd like to find combinations of six or so, allowing perhaps a month of CPU time. Thanks for any help. -- Joe Keane, amateur mathematician ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math,comp.programming Subject: Re: finding linear dependence Date: 14 Feb 1996 20:20:29 GMT In article , Joe Keane wrote: >Basically, i have a large collection of vectors, and i want to find out >if one can be expressed as a linear combination of a few of the others. ... >The components of the vectors are rational numbers, so all operations >are exact, but these numbers can be fairly complicated, and arithmetic >operations can take a long time, that is, milliseconds instead of the >usual tens of cycles for native integers or floating-point numbers. ... >To put some concrete numbers behind this, i have roughly a thousand >vectors, each one has maybe ten or twenty components, and i'd like to >find combinations of six or so, allowing perhaps a month of CPU time. Of course on one level the problem is trivial. You have a 1000 x 20 matrix, you want something in the null-space, which is probably 980-dimensional. Pick any 21 components and use row-reduction to find a linear combination which is zero. I see the poster has two objections to this. First, each entry in the matrix is 'large', meaning that every add or multiply is very costly; thus he seeks a row-reduction technique which minimizes the number of arithmetic operations. Second, the resulting linear combination involves many (probably 20) vectors at a time, and he seeks instead linear combinations with all but a few of the coefficients zero. Unless your rational numbers have incredibly many digits, I would imagine it's the second objection which is going to be the more difficult to overcome. ---------------- One possibility which may help for both problems is to work mod p for various small primes p. As has been noted in another thread, it doesn't take too many primes to have a product which is many digits long, so that you can use the Chinese Remainder Theorem to recover integral linear combinations unambiguously from a few mod-p combinations. I believe this is the most efficient method of handling large-number arithmetic anyway (assuming there is a large number of arithmetic operations involved, so that the conversion overhead may be ignored). The poster's second concern makes this more of a combinatorial problem: one ought to consider all sets of 6 vectors at a time and see if they are linearly dependent. There are (1000 choose 6) ~ 10^15 such combinations, which may be too many to do by hand, I suppose. But suppose we decided only to work mod 2. For most sets of 6 vectors in (F_2)^5, there is a unique linear relation among the vectors; that is, one can unambiguously determine the linear relation by examining only the first 5 entries of the vectors (usually). Let the relation be Sum( a_i row_i) = 0. Now, the vectors are linearly dependent iff this relation continues to hold in the other columns. If the other entries are essentially random (mod 2), then Sum( a_i (row_i)_j ) is just as likely to be 1 as 0, so that only (1/2) of the sets identified as dependent from the first 5 columns are still dependent when we examine the sixth. Continuing in this way, we expect only (1/2)^15 of the 6-tuples of vectors to be really dependent mod 2. With your combinations of parameters, it looks to me like if there are any sets of 6 vectors which are rationally dependent, you'll be able to spot them unambiguously just by working modulo the first few primes, assuming that your list of 1000 vectors is more or less randomly generated (modulo the product of the primes.) On the other hand, I don't know an easy way to choose a set of 6 20-tuples of 0's and 1's which are linearly dependent from among a set of 1000. This sounds like one of those covering-designs problems (maybe like Steiner systems) but I'd better not be more specific because I'm not really well versed in this kind of combinatorics. ---------------- Somehow it seems one ought to be able to use the LLL algorithm for finding small lattice points. I can't quite figure out the details, but maybe someone else can jump in here. First note that you won't disturb linear dependence by clearing denominators; multiply each row through by an integer to assume that the whole 1000 x 20 matrix is integral. Adjoin a 1000x1000 identity matrix. Now you have a 1000 x 1020 matrix whose rows may be viewed as generators of a 1000-dimensional lattice in 1020-dimensional space. You definitely no longer have any linear relations. On the other hand, an integral linear relation among the original vectors now supplies a lattice point whose first 20 coordinates are zero. Most of the remaining coordinates are zero too -- all except the ones corresponding to the vectors in the linear combination. So if you measure the "size" of the vector by the number of nonzero entries, the question you ask is more or less, "How do we find small nonzero elements in a lattice?" While it is in general a costly job to find the _smallest_ nonzero element in an integral lattice, there is an algorithm which will find _small_ elements in the lattice quickly. It's known as the LLL algorithm (A.K.Lenstra, H.W.Lenstra and L.Lovasz, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982) pp. 515-534), and it has been incorporated into Maple, Mathematica, and so on. I don't know if you can use a canned package, since even a 20-dimensional lattice can be slow to work with, to say nothing of a 1000-dimensional lattice. Moreover, the LLL algorithm assumes that "smallness" is measured relative to a quadratic form on the lattice. Thus if there is a linear combination of vectors which has small coefficients (in the usual sense), then the LLL routine will find it rather than a vector with lots of zero coefficients and the others large. In the application I proposed, you will be doubly penalized by this algorithm: it will happily form a linear combination of _many_ vectors (maybe all 1000) if it can find a way to do this with small coefficients and yield a 20-tuple with small coefficients too. So you will neither have a true linear dependence nor have a combination of few vectors. One trick can help in principle: scale each of your 20-tuples by some large fixed integer. Then the algorithm will be working harder to ensure that the 20 coefficients of the linear combination are really close to zero. But I suspect that the effect of this transformation will be to include many of the 1000 vectors, rather than few. ---------------- One last comment: I suspect you didn't come by these vectors randomly, but suppose you did. Suppose that you fill a 1000 x 20 array with integers randomly selected modulo a large modulus M. It's highly unlikely that _any_ 6-tuple is linearly dependent. Indeed, throw away all but the first 6 columns of your matrix. If you pick any 6 rows, then as in the mod-2 discussion we see there is only a probability of 1/M that these 6 rows of 6-tuples are linearly dependent. Of course, there are still about 10^15 sets of 6 rows, but if M > 10^15, that still makes it unlikely that _any_ of these will be dependent. Thus if you are dealing with integers which are dozens of digits long, it would be remarkable enough if you could find linear combinations which made the first 6 coeffients vanish. If you found one, of course, you could quickly scan the remaining 14 entries of the vectors to see if the linear relation holds "on the nose". But it would seem to me that when working integrally, if your integers are really big and more or less "random", then you probably don't need all 20 entries of each vector. Keep the first 6 or 7 and flag any linear dependencies among any sets of 6 vectors. (This is assuming you didn't find an efficient solution using the mod-p technique, since we would have to trade a larger set of primes to compensate for shorter vectors.) This is analogous to the situation which faced practitioners of "moonshine madness" in finite group theory. One noticed that the coefficients of the j-function and other modular functions related to it were "small" linear combinations of the entries in the character table of the finite simple group known affectionately as the "Monster". Finding the linear relations was (and is) considered remarkable, clearly not "random". dave ============================================================================== Date: Sun, 18 Feb 1996 18:57:07 -0800 From: Joe Keane To: Dave Rusin Subject: Re: finding linear dependence Thank you, that's a very detailed response, and you're one of the few people that correctly interpreted my question and addressed my concerns. I'll go over it some more and probably have more detailed comments. One thing that's clear is i need to learn more about the LLL algorithm. I ran across it a couple times before, and i've been curious about it, but now it seems to be quite appropriate to this problem. -- Joe Keane, amateur mathematician ============================================================================== Date: Sun, 18 Feb 96 21:19:32 CST From: rusin (Dave Rusin) To: jgk@netcom.com Subject: Re: finding linear dependence >Thank you, that's a very detailed response, and you're one of the few >people that correctly interpreted my question and addressed my concerns. Yes I noticed a poor signal-to-noise ratio in that thread. As far as I can tell nothing is both appropriate and nontrivial except _possibly_ what I wrote. But the more I think about it, the more I feel like if you have N vectors in R^k and you want to find a dependent set of n of them, you pretty much have to traverse over all N^n or so subsets of cardinality N and just check for dependence. (I can cut down by one factor of N which might be helpful if you really want n=6 and N=10000). I did have one other idea but I can't imagine it's really going to be helpful: Look at the Grassmannian manifold G of all (n-1)-dimensional subspaces of R^N. (This has dimension (n-1)(N-n+1). ) Each vector v is contained in lots of subspaces of R^N, and so determines a variety A(v) of G. You want to find n vectors v_i which are dependent, that is, they all lie in the same n-1-dimensional subspace of R^N. That means there is to be an intersection of the corresponding varieties A(v_i). I can't imagine how you would effectively visualize this gigantic variety geometrically, but it was the best I could come up with to encapsulate the idea that some sets of vectors are "too far apart" to be linearly dependent. >One thing that's clear is i need to learn more about the LLL algorithm. >I ran across it a couple times before, and i've been curious about it, >but now it seems to be quite appropriate to this problem. Maybe. I was hoping someone else would see a connection and fill in the details. The ensuing silence makes me think otherwise. LLL is a cool algorithm though. People use it to do things like find algebraic equations satisfied or nearly satisfied by real numbers (e.g. find quartics whose roots are really close to pi, or determine the minimal polynomial of a+b if p(a)=0 and q(b)=0. ) dave