# Vectors with minimal Hamming weight in a rational vector space?

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.)

• Well, you can look at all vectors with weight one (there are only $n$ of them up to scaling) to see if they belong to $U$, if not move to weight two, and so on... but presumably you want a faster algorithm. Dec 28 '20 at 10:41
• For weight $2$, I would need to check whether the intersections with $n(n-1)/2$ subspaces of dimension $2$ are nonzero. This amounts to adding two standard basis vectors to my $\mathbb{Q}$-linear basis of $U$ and to check the resulting tuple of vectors for linear independence. Likewise for larger weights. In practice, this algorithm will work in small cases. Dec 30 '20 at 11:09

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.$$