Skip to main content
Notice removed Draw attention by Louis Deaett
Bounty Ended with Max Alekseyev's answer chosen by Louis Deaett
edited tags
Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152
Notice added Draw attention by Louis Deaett
Bounty Started worth 50 reputation by Louis Deaett
Source Link

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