Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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$).

share|improve this answer
add comment

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$.

share|improve this answer
    
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)$? –  Huichi Huang Nov 16 '10 at 2:00
    
@Owen: You probably want some $k$ different from $i$ and $j$ because $d(i,i)\not=d(j,i)$ is always true. –  Guillaume Brunerie Nov 16 '10 at 7:43
    
@Guillaume: Of course, thank you. Fixed. –  Owen Biesel Nov 16 '10 at 13:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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