checking whether a vector is in the affine hull

[fbreuer]

There are two ways to check whether a vector is in the affine hull of a set of points:

1. Via ranks

The dimension of the affine hull of vectors v_1,...,v_n can be calculated via get_poly_dim, i.e. dim(aff(v_1,...,v_n)) = get_poly_dim(M) where M is the matrix with the v_1,...,v_n as rows. Using this notation, we can check whether a vector w is contained in the affine hull of v_1,...,v_n as follows:

If dim(aff(v_1,...,v_n,w)) > dim(aff(v_1,...,v_n)), then w is not contained in the affine hull. Otherwise w is contained in the affine hull.

So we need only use get_poly_dim twice to check this. (Checking whether the zero vector is in the matrix will do us no good.)

Note that the dimensions will differ only by 1! So small numerical errors in the rank computation may lead to a wrong result here.

2. By solving linear systems

To check if w is contained in the affine hull of the vectors v_1,...,v_n one can simply check if the linear system Mx=(w-v_n) has a solution, where M is the matrix with columns (!!!) v_1-v_n, v_2-vn, ..., v{n-1}-v_n.

If Mx = (w-v_n) has a solution, w is contained in the affine hull. Otherwise w is not contained in the affine hull.

If there is only one w that has to be check, we only need to solve one linear system here, whereas with the previous method, we needed to compute two ranks. However, if we need to do this check for many w, then there is no significant difference in theoretical complexity.

[stambizzle]

The ranks method is what I have currently implemented, and it involves n + 2 rank calculations, where n is the number of rows in the data set. If it doesn't matter whether the vector we are checking is zero, then this will be a very easy fix!

[fbreuer]

Yes! It should be straightforward. Thanks to the way get_poly_dim works, no vector gets special treatment.