# How to find the minimum Hamming distance?

I have a vector $$v = (9, 2, 3, 4, 8)$$.

Vector space over $$\mathbb{Z}_{11}$$ is generated by a set: $$e_{1} = (4, 2, 0, 0, 1)$$, $$e_{2} = (1, 9, 0, 1, 0)$$, $$e_{3} = (5, 0, 1, 0, 0)$$, $$e_{4} = (0, 7, 0, 0, 0)$$, $$e_{5} = (6, 0, 2, 4, 9)$$.

I want to find the minimum Hamming distance between $$v$$ vector and any vector from given vector space.

My only idea is to make 5 nested loops, which would generate all vectors from the vector space and compute Hamming distance between every single wector and $$v$$.

How can I make this better?

• (1) Generate a nicer basis using RowReduce[basis,Modulus->11]. (2) In future please post actual code e.g. the basis generators in copy/pastable format. Apr 15, 2021 at 15:51
• @DanielLichtblau: Thank you for your valuable comment. See the addition to my answer. Apr 15, 2021 at 16:46

First, since

Mod[Det[{{4, 2, 0, 0, 1}, {1, 9, 0, 1, 0}, {5, 0, 1, 0, 0}, {0, 7, 0,
0, 0}, {6, 0, 2, 4, 9}}], 11]


0

, this space is not whole $$\mathbb{ Z}_{11}^5$$. We form that space as a finite set of linear combinations of the vectors {4, 2, 0, 0, 1}, {1, 9, 0, 1, 0}, {5, 0, 1, 0, 0}, {0, 7, 0, 0, 0}, {6, 0, 2, 4, 9} by $$\mod_{11}$$

Partition[Flatten[Table[Mod[a*{4, 2, 0, 0, 1} + b*{1, 9, 0, 1, 0} + c*{5, 0, 1, 0, 0} +
d*{0, 7, 0, 0, 0} + e*{6, 0, 2, 4, 9}, 11], {a, 0, 10}, {b, 0, 10}, {c , 0, 10},
{d, 0, 10}, {e, 0, 10}]], 5]


Then we map HammingDistance from {9, 2, 3, 4, 8} on that set and find the minimum distance by

Min[Map[Function[y, HammingDistance[{9, 2, 3, 4, 8}, y]],
Partition[Flatten[Table[ Mod[a*{4, 2, 0, 0, 1} + b*{1, 9, 0, 1, 0} + c*{5, 0, 1, 0, 0} +
d*{0, 7, 0, 0, 0} + e*{6, 0, 2, 4, 9}, 11], {a, 0, 10}, {b, 0, 10}, {c, 0, 10}, {d, 0, 10},
{e, 0, 10}]], 5]]]


1

Addition.Following the helpful comment by @DanielLichtblau, we may somewhat improve the code, finding a basis of the space under consideration which consists of four elements

RowReduce[{{4, 2, 0, 0, 1}, {1, 9, 0, 1, 0}, {5, 0, 1, 0, 0}, {0, 7,
0, 0, 0}, {6, 0, 2, 4, 9}}, Modulus -> 11][[1 ;; 4]]


{{1,0,0,0,3},{0,1,0,0,0},{0,0,1,0,7},{0,0,0,1,8}}

and then

Min[Map[Function[y, HammingDistance[{9, 2, 3, 4, 8}, y]],Partition[Flatten[
Table[Mod[a*{1, 0, 0, 0, 3} + b*{0, 1, 0, 0, 0} + c*{0, 1, 0, 0, 7} + d*{0, 0, 0, 1, 8}, 11], {a, 0, 10}, {b, 0, 10}, {c, 0,
10}, {d, 0, 10}]], 5]]] // AbsoluteTiming


{0.0674779, 1}

• The execution of the latest code on my antique comp takes 0.845529 sec. Apr 15, 2021 at 11:20
• If there were an analog of RowSpace command of Maple in Mathematica, the code could be more efficient. Apr 15, 2021 at 13:06