# Isometry on a Hamming cube

Let $E^n$ be a Hamming cube of dimension $n$, and $\phi$ be a mapping from $E^n$ to $E^n$ that preserves Hamming distance, i.e. $d(x,y)=d(\phi (x),\phi (y))$. The question is the following: show that $\phi$ can only be constructed as a permutation of coordinates plus a constant vector, i.e. $\phi (x)=\pi (x)+v$, where $\pi \in S_n$ and $v\in E^n$.

-
category-theory? Must be a better tag.... –  Gerry Myerson Apr 9 '13 at 12:14

This might not be research-level, but here's an answer anyway. I'll take the cube to be $\{0,1\}^n$. Let an isometry $\phi$ be given. Adding a constant vector, if necessary, we can assume that $\phi(\vec0)=\vec 0$. Then the unit vectors (the vectors with exactly one component equal to 1), being the vectors at distance 1 from $\vec 0$, are mapped to each other, in a one-to-one way. That gives us a permutation $\pi$ of the coordinate positions. Finally, to show that $\phi$ acts on all vectors $\vec v$ by permuting components according to $\pi$, proceed by induction on the number of non-zero components of $\vec v$, taking into account which vectors with fewer 1's are at distance 1 from $\vec v$.