I have a collection of $N$ linearly independent vectors $\mathbf{v}_i$ over the field $\mathbb{Z}_2$. So the entries of the vectors are in {0,1}. I want to find a set of vectors which span the same space as $\mathbf{v}_i$, but have as few nonzero elements as possible. For example, if the vectors are (1,1,0) and (0,1,0), the desired result would be (1,0,0) and (0,1,0). What is a method to accomplish this, and will the resulting set be unique? In other words, can there be more than one solution?
I first thought of Gram-Schmidt, but it appears that inner products are not defined over finite fields: Inner Product Spaces over Finite Fields
I have an approach, but will it always find the minimal set? How would I prove it? Is there a better/faster approach? Does this type of problem have a name?
v = the list of N linearly independent vectors, and v[i] is the ith vector
for i in 1,2,3,...N:
CONTINUE_SEARCH=True
while CONTINUE_SEARCH:
u = vector in {v excluding v[i]} such that u + v[i] would have the
fewest nonzero elements and would also lower the number of nonzero
elements compared to v[i]. If there is more than one answer for u,
choose the first.
if u exists:
v[i] = v[i] + u, (elementwise addition mod 2)
else:
CONTINUE_SEARCH=FALSE
your approach seems reasonable but it doesn't guarantee finding the minimal set in every scenario. Depending on the order of vectors and choices, you may end up with a set that has more nonzero elements than the minimal set. I think a more efficient method would be to row reduce sparse matrices. It's quite doable in c++