Persi asked me the other day to find other bi-invariant metrics on besides the Hamming metric and the Cayley metric. A metric on a group is called bi-invariant if
for any . It is necessarily of the form where is a class function on . Conversely, every class function gives rise to a bi-invariant bivariate function as above. To be a metric, needs to satisfy
- The triangle inequality: .
- Nondegeneracy: if and only if .
- symmetry: .
These translate to conditions on :
- if and only if .
Symmetry is not absolutely necessary for to enjoy many of the utilities of a metric: for instance the relative entropy is only a pseudometric because it’s not symmetric, nonetheless it’s very useful for analyzing convergence rate of Markov processes.
The Hamming distance is based on , where is the number of fixed points in , or 1-cycles. Nondegeneracy and symmetry are easily checked. To show the triangle inequality, simply observe that and if a number is a fixed point of and of , then it’s fixed by as well.
The Cayley distance is based on where is the standard notation for the total number of cycles in . It’s the graph metric based on the Cayley graph structure on with generating set being the set of transpositions .
This morning I thought of some other bi-invariant metrics on any finite group , which are probably well-known. The idea is to imbed the group into another group that’s equipped with a bi-invariant metric . The easiest way is to look at the representations of , and imbed as a subgroup of or . One then takes the -induced metric on . Note that not all representations are faithful: for instance the signature representation of has as its kernel; therefore we need faithful representations to get nondegeneracy. But symmetry and triangle inequality are automatic.
A worked out example: One could take the imbedding of into . The image is the set of unsigned permutation matrices. For each permutation matrix , one can diagonalize it according to its cycle type. For instance, if corresponds to an -cycle , then its eigenvalues are . So its distance from the identity is given by
where is the periodic extension of the function for . The formula above is obtained by calculating the length of the global geodesic from the identity to , given by
The infinitesimal Riemannian distance on coincides with Hilbert Schmidt length, hence can be calculated easily.
More generally, if has cycle types , then it can be put in block diagonal form, where an block has eigenvalues , . Thus
Thus we see explicitly that is a class function. We call a function a square-root like function if it is concave increasing function on that vanishes at . By precomposing with any square-root like function , we get a new class function that induces a new bi-invariant metric on . Thus we have an infinite family of bi-invariant metric on any finite group . It seems sensible to define a partial ordering on the set of bi-invariant metrics on with if for some square-root like function . One just has to check that for both square-root like.