Given a list of vectors in R3 how many unique planes are generated?

Question

While investigating packings of spheres I ran into this problem where I have a list of vectors and I want to know how many planes they generate. I'm generating these lists of vectors that point from the center of a sphere to a contact point on the outside surface of the sphere and I want to know how many of these vectors are coplanar. For example I want an algorithm that will do the following..

Given the vectors {1,2,3}, {2,4,6}, and {0,6,9} it should report that there is only one unique plane generated by either one of the first two and the third.

All of my attempts haven't gotten anywhere because every time I count how many planes are generated I drastically over count. I feel like this should be an easy thing to do and I'm also curios if there is any linear algebra that can somehow come to the rescue. If I can determine how many planes are generated and what those planes are I think it will be easy to determine how many vectors lie in each plane which is the last part of this problem. If anyone can think of a more general approach to any dimension two or greater that would actually be ideal but for now this is all I'm concerned with.

Answer 1

You can use Gaussian elimination to determine the dimension of the span of several vectors. (the space that is created by all linear combinations of these - also called rank of the matrix)

Create a matrix from your vectors by writing the vectors in the rows of your matrix. Then use Gaussian elimination and count the number of Rows that still have non-zero entries. This is the dimension of the spanned vectorspace.

Since you use vectors from R^3 this will never be greater than 3. However a plane is a 2-dimensional vectorspace, so you need to find all combinations of vectors that result in a 2-dimensional span, which can be easily found by iterating over your vectors once you have implemented gaussian elimination.

Edit:

An example since it seems that this can still lead to confusion:

you have a set of 3 vectors: (1,0,0); (0,1,0); (0,0,1)

You can create 3 different planes from these (by combining any two of these vectors you get a different plane.) To formally check if that statement is true you need to do the following for every pair v1,v2 of vectors:

1. check whether v1,v2 are linear independant - if they aren't, they don't create a plane, so you go ahead and pick the next two vectors. (in this example they always are linear independant)
2. Check for each other vector in your list, if it (v3) does not lie within the created plane (it is not coplanar to v1,v2). To do this use gaussian elimination on the matrix (v1,v2,v3) and confirm that the rank of the matrix is 3.

If the matrix in step 2 has a rank of 2, this means that the vectors v1,v2,v3 are coplanar. Thus you can pick any two of these vectors to generate the exact same plane.

As an example: you start with vectors (1,0,0) and (0,1,0). Then you check several other vectors and find that two of them are coplanar to your initial vectors (for example (1,1,0) and (-1,-1,0)). This means that for your list of unique planes, you may add the plane generated by any two out of these four vectors, but not add any other combination of these.

Note: this works for finding 2 dimensional planes in higher dimensions as well of course. You can even check for higher dimensional planes, but this needs some adapting in the number of vectors you compare and the rank for which you check.