Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: Vectors summing to zero
Replies: 24   Last Post: Sep 9, 2010 8:48 AM

 Messages: [ Previous | Next ]
 Gerry Myerson Posts: 4,919 Registered: 12/6/04
Re: Vectors summing to zero
Posted: Aug 31, 2010 6:57 PM

In article <Xns9DE57E5A722F2txb1bxtgmailcom@94.75.214.39>,
TXB <txb1bxt@gmail.com> wrote:

> I have a collection of vectors that span some n-dimensional space.

I take it this is a *finite* collection of vectors.

> These vectors are typically unit vectors of the dimensional space or the
> difference of two unit vectors. I want to find all the three-vector
> combinations that sum to zero. Currently I do this by selecting every
> possible 3 vector combination to see if a non-trivial linear combination
> exists that sums to zero. Specifically, I select a vector (v1) and perform
> a least-squares solution to find a and b so that a*v2 + b*v3 = v1.

I suspect it would take less work if instead you form a matrix
whose columns are the three vectors and then use row-reduction
(a.k.a. Gaussian elimination) to see whether you get a matrix of rank 2.
If you do, then there's a linear dependence relation for the three
vectors, and it's easy to work out what it is from the reduced matrix
and decide if it's three vectors adding to zero.

> If the
> sum is zero (and a, b = +1 or -1), I record the grouping of (v1, v2, and
> v3) and continue. This is working, however, I feel like there is a simpler
> methodology that I am missing.

Maybe this is better than both least squares and row reduction:
Form all the sums of 2 vectors and then look to see whether the list
of sums has any member in common with the list of negatives of
the original vectors. This may run faster if you sort the list of sums,
say, by value of 1st component, breaking any ties by sorting on
the value of the 2nd component, etc.

> Eventually I use this information to create
> an adjacency matrix for these vectors and display it as a graph.

I don't know what you mean by "an adjacency matrix for these vectors."

--
Gerry Myerson (gerry@maths.mq.edi.ai) (i -> u for email)