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