Suppose given $n\ge 1$ and a subspace $U$ in $\mathbb{Q}^n$. It is given as $\mathbb{Q}$-span of certain known vectors.


For $x \in U$, we let the Hamming weight of $x$ be the number of its nonzero entries.


Is it possible to find an element of minimal Hamming weight in $U\smallsetminus\{0\}$? Is there an algorithm?


(All I could find is concerned with the case of vector spaces over finite fields. Or, on the other hand, with vectors of minimal Euclidean length in lattices.)



Vectors with minimal Hamming weight in a rational vector space?
Here is an Integer Linear Programming approach to this problem.


First, let's multiply given vectors by a suitable integer to make them all having integer components. Second, we notice that if certain rational coefficients deliver the minimum Hamming weight, then by scaling them, we can obtain integer coefficients delivering the same weight. Therefore, we can focus on the problem of finding an integer linear combination of integer vectors with the smallest nonzero number of nonzero components.


Let $v\_1,\dots,v\_m$ be given integer vectors. Let $c\_i$ for $i\in\{1,\dots,m\}$ be integer variables corresponding to the coefficients in a linear combination. For each component $j\in\{1,\dots,n\}$, we further introduce two binary variables $p\_j,q\_j\in\{0,1\}$ and three inequalities:
$$\sum\_{i=1}^m v\_{ij} c\_i \geq p\_j - Mq\_j,$$
$$\sum\_{i=1}^m v\_{ij} c\_i \leq -q\_j + Mp\_j,$$
$$p\_j + q\_j \leq 1,$$
where $M$ is a large positive constant (chosen empirically). The third inequality here restricts values to three possible cases: $(p\_j,q\_j)=(1,0)$ when the $j$-th component in the linear combination is positive; $(p\_j,q\_j)=(0,1)$ when the $j$-th component is negative; and $(p\_j,q\_j)=(0,0)$ when the $j$-th component is zero. Notice that the large value of $M$ when it comes with a nonzero coefficient makes the corresponding inequality silent (automatically satisfied).


Next, we exclude the zero linear combination by requiring
$$\sum\_{j=1}^n p\_j + q\_j \geq 1.$$


Finally, since $\sum\_{j=1}^n p\_j + q\_j$, in fact, equals the weight of the linear combination, our objective is
$$\text{minimize}\quad \sum\_{j=1}^n p\_j + q\_j.$$


