Question

Let $X$ be an n point finite set equipped with a metric $d$. An isometry is a map $\varphi$ $:X \mapsto X$ satisfying that $d(\varphi(x),\varphi(y))=d(x,y)$ for any $x,y \in X$. Identify $X$ with the set {$1,2,...,n $}. We can say every isometry is an element of $S_n$(the permutation group of n elements) and the isometry group of $X$ (denote it by $Iso(X,d)$) is a subgroup of $S_n$. The question is the following: if there is no isometry moving $i$ to $j$,what can we say about $Iso(X,d)$ ? Are there any books about this literature? Thanks.

Answer 1

As secretman says, the condition that there exist $i$ and $j$ in $X$ such that no isometry carries $i$ to $j$ is precisely to say that the action of the isometry group on $X$ is not transitive. If that's really your question, that seems to be all that can be said, and I doubt there any books on the subject.

One might simply ask: what can be said about isometry groups of finite metric spaces? This is a rather broad question, but nevertheless it seems interesting. Here is what I was able to come up with via a short amount of thought and googling:

1) Every finite group $G$ occurs up to abstract group isomorphism as the full isometry group of a finite metric space. Indeed, in this 1976 paper, D. Asimov proved that if $G$ is finite of cardinality $k$, there exists a finite subset $X_G$ of Euclidean $k-1$-space (with the induced metric), of cardinality $k^2-k$, such that the full isometry group of $X_G$ is isomorphic to $G$.

2) On the other hand, it is not true that every permutation group is the isometry group of a finite space: i.e., if $X = \{1,\ldots,n\}$ and $G$ is subgroup of $S_n$, then there need not be a metric $\rho$ on $X$ such that $G = \operatorname{Aut}(X,\rho)$. For a simple example, take $n = 3$ and let $G$ be the subgroup of order $3$, i.e., $G$ is generated by $\sigma = (123)$. Since $\sigma$ is an isometry,

$\rho(1,2) = \rho(\sigma(1),\sigma(2)) = \rho(2,3) = \rho(\sigma(2),\sigma(3)) = \rho(1,3)$.

Thus all pairwise distances between the three elements of $X$ are equal and the isometry group is the full $S_3$.

More generally, let $\rho$ be a metric on $X$ and $G \subset \operatorname{Sym}(X)$ the isometry group. Let $X^{(2)}$ be the set of (unordered!) two-element subsets of $X$: there is a natural action of $\operatorname{Sym}(X)$ -- and hence also of $G$ -- on $X^{(2)}$. Now the observation here is that if $G$ acts transitively on $X^{(2)}$ -- e.g. if $G$ is doubly transitive as a permutation group on $X$, but this condition is weaker -- then that means that all pairs of points in $X$ have the same distance, and therefore $G = \operatorname{Sym}(X)$.

It strikes me that one could take this construction a step further: we may define a graph $G$ with vertex set $X^{(2)}$ by decreeing two vertices $\{x_1,x_2\}$, $\{y_1,y_2\}$ to be adjacent iff $\rho(x_1,x_2) = \rho(y_1,y_2)$. Then $G$ is precisely the group of graph automorphisms of $G$. This is sort of a "combinatorialization" of the problem, although I don't know whether it's actually useful for anything. This is false, as Aleksander Horawa has pointed out to me. I'm not sure what I was thinking when I wrote this. As he points out, it is at least true that when $\# X \geq 3$, the induced homomorphism from the isometry group of $X$ to the automorphism of the graph is injective (even this fails when $\# X = 2$).

Answer 2

In accordance with Huichi Huang's comment on secretman's answer, we can say the following: If no isometry sends $i$ to $j$, then there exists some $k$ (Edit: different from $i$ and $j$) with $d(i,k)\neq d(j,k)$. Why? Because if $d(i,k)=d(j,k)$ for all $k$, then the transposition $(ij)\in S_n$ is an isometry of $X$.

Answer 3

What do you mean? The action isn't transitive, that's all. Note also that an isometry is not necessarily bijective, so you can only say the group of bijective isometries embeds in $S_n$.