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.
2 Answers
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:
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$.
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$).
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$.
-
$\begingroup$ We can get more information than " there exists some $k$ with $d(i,k)≠d(j,k)$." since we get this from $(ij)\notin Iso(X,d)$. What can we get from any other elements in $S_n$(but not in $Iso(X,d)$ moving $i$ to $j$ (e.g $(ijk),(ijkl)$? $\endgroup$ Nov 16, 2010 at 2:00
-
$\begingroup$ @Owen: You probably want some $k$ different from $i$ and $j$ because $d(i,i)\not=d(j,i)$ is always true. $\endgroup$ Nov 16, 2010 at 7:43
-
$\begingroup$ @Guillaume: Of course, thank you. Fixed. $\endgroup$ Nov 16, 2010 at 13:55