2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ (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. $\endgroup$ Apr 15, 2021 at 15:51
  • $\begingroup$ @DanielLichtblau: Thank you for your valuable comment. See the addition to my answer. $\endgroup$
    – user64494
    Apr 15, 2021 at 16:46

1 Answer 1

3
$\begingroup$

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}

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.