# Minimize Sum of Hamming Distances

Problem: Given an $$n \times m$$ matrix with binary values $$(0,1)$$, find a binary vector that minimizes the sum of Hamming Distances to the rows.

Example: If the matrix is {{$$1,1,1$$},{$$0,0,0$$},{$$1,0,1$$}} we want to return the vector {$$1,0,1$$} which has a sum of HammingDistances of $$1 + 2 + 0 = 3$$.

Current Attempt: We can use a pure function to compute the HammingDistances between the rows of the input matrix (x) and a vector(y).

agreement[x_, y_] := HammingDistance[#, y] & /@ x


However, we can't plug this directly in to the built-in Minimize function. The following gives an invalid constraint error.

Minimize[agreement[{{1,1,1},{0,0,0},{1,0,1}}, y], y]

• Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Take the tour! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! Jul 15, 2022 at 18:16
• Generally speaking, one question, one problem, unless there's a strong reason to think the same solution will solve both problems. There's probably some overlap in yours, but the problems seem distinct to me. (I take it, in the last example, the triplets of numbers should be vectors, right?) Jul 15, 2022 at 18:19
• You can format inline code and code blocks by selecting the code and clicking the {} button above the edit window. The edit window help button ? is useful for learning how to format your questions and answers. You may also find the meta Q&A, How to copy code from Mathematica so it looks good on this site, helpful Jul 15, 2022 at 18:20

Keep agreement[] from evaluating on symbolic y with the _?... pattern tests. Also total up the Hamming distances.

ClearAll[agreement];
agreement[
x_?(MatrixQ[#, NumericQ] &),
y_?(VectorQ[#, NumericQ] &)] :=
HammingDistance[#, y] & /@ x // Total;

Minimize[
{agreement[{{1, 1, 1}, {0, 0, 0}, {1, 0, 1}}, Array[y, 3]],
Thread[0 <= Array[y, 3] <= 1]},
Array[y, 3] \[Element] Integers]

(*  {3, {y[1] -> 1, y[2] -> 0, y[3] -> 1}}  *)

• Beautiful, thank you!
– B A
Jul 15, 2022 at 18:38
• This strategy of using pattern tests to prevent evaluating on the symbolic expressions for maximizing/minimizing user-defined functions seems generally applicable so I appreciate the explanation!
– B A
Jul 15, 2022 at 18:40
• @BA I believe it works here with Minimize because the domain is bounded. If it's infinite, you probably have to use NMinimize.... Jul 15, 2022 at 18:45