# Efficient algorithm to check if a vector exists in the span of a subset of vectors

I have a binary vector $v \in \mathbb{F}_2^m$ and a set of binary vectors $Q=\{q_1,q_2,\dots,q_n\}$ each belonging to $\mathbb{F}_2^m$ and I know that $v \in \text{span}\{Q\}$ but I want to know if there exists a subset $Q_k \subset Q$ of at most $k$ vectors ( i.e. $|Q_k| \le k < n$ ) such that $v \in \text{span}\{Q_k\}$. Is there a fast algorithm to do this other than the naive way of checking all the subsets of cardinality at most $k$? Assume that all of the operations are done in GF(2).

## 1 Answer

Equivalently, your problem can be stated as:

Given a $m \times n$ matrix $M$ over $\mathbb{F}_2$ and a vector $v \in \mathbb{F}_2^m$, find a vector $x\in \mathbb{F}_2^n$ such that $M x=v$ and the Hamming weight of $x$ is as small as possible.

There are some hardness results for this problem. For instance, this post argues that the problem can't be approximated within a constant factor, within polynomial time (even for randomized algorithms), assuming standard complexity-theory assumptions.

See also https://cs.stackexchange.com/a/59922/755 and https://cstheory.stackexchange.com/a/10112/5038 and https://cstheory.stackexchange.com/q/27460/5038 and https://cstheory.stackexchange.com/q/10396/5038 for related work, including some algorithmic techniques that might be relevant.

• Thank you very much for the comprehensive and insightful answer. I edited it to make the dimensions of the vectors compatible with my original question. – Mohsen Kiskani Jan 18 '17 at 0:24