## Bi-invariant metrics on the symmetric groups, and a partial ordering on them

Persi asked me the other day to find other bi-invariant metrics on ${S_n}$ besides the Hamming metric and the Cayley metric. A metric ${\rho}$ on a group ${G}$ is called bi-invariant if

$\displaystyle \rho(\sigma,\tau) = \rho(a \sigma b, a \tau b), \ \ \ \ \ (1)$

for any ${a, b, \sigma, \tau \in G}$. It is necessarily of the form ${\rho(\sigma,\tau) = \rho_0(\sigma \tau^{-1})}$ where ${\rho_0}$ is a class function on ${G}$. Conversely, every class function ${\rho_0}$ gives rise to a bi-invariant bivariate function ${\rho}$ as above. To be a metric, ${\rho}$ needs to satisfy

1. The triangle inequality: ${\rho(a,b) + \rho(b,c) \ge \rho(a,c)}$.
2. Nondegeneracy: ${\rho(a,b) = 0}$ if and only if ${a=b}$.
3. symmetry: ${\rho(a,b) = \rho(b,a)}$.

These translate to conditions on ${\rho_0}$:

1. ${\rho_0(ab^{-1}) + \rho_0(b c^{-1}) \ge \rho(a c^{-1})}$.
2. ${\rho_0(a) = 0}$ if and only if ${a=id}$.
3. ${\rho(a) = \rho(a^{-1})}$.

Symmetry is not absolutely necessary for ${\rho}$ 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 ${\rho_0(\sigma) = n- \alpha_1(\sigma)}$, where ${\alpha_1(\sigma)}$ is the number of fixed points in ${\sigma}$, or 1-cycles. Nondegeneracy and symmetry are easily checked. To show the triangle inequality, simply observe that ${ac^{-1} = (ab^{-1}) (bc^{-1})}$ and if a number ${k}$ is a fixed point of ${\sigma}$ and of ${\tau}$, then it’s fixed by ${\sigma \tau}$ as well.
The Cayley distance is based on ${\rho_0(\sigma) = l(\sigma)}$ where ${l(\sigma)}$ is the standard notation for the total number of cycles in ${\sigma}$. It’s the graph metric based on the Cayley graph structure on ${S_n}$ with generating set being the set of transpositions ${(i,j)}$.
This morning I thought of some other bi-invariant metrics on any finite group ${G}$, which are probably well-known. The idea is to imbed the group ${G}$ into another group that’s equipped with a bi-invariant metric ${\tilde{\rho}}$. The easiest way is to look at the representations of ${G}$, and imbed ${G}$ as a subgroup of ${GL(n,{\mathbb C})}$ or ${GL(n,{\mathbb R})}$. One then takes the ${\tilde{\rho}}$-induced metric ${\rho}$ on ${G}$. Note that not all representations are faithful: for instance the signature representation of ${S_n}$ has ${A_n}$ 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 ${S_n}$ into ${SU(n)}$. The image is the set of unsigned permutation matrices. For each permutation matrix ${A}$, one can diagonalize it according to its cycle type. For instance, if ${A}$ corresponds to an ${n}$-cycle ${\sigma}$, then its eigenvalues are ${\omega_n^j:=e^{2\pi i j/ n}}$. So its distance from the identity is given by

$\displaystyle \rho_0(\sigma)=\sqrt{\sum_{j=1}^n f(2\pi j/n)^2} \ \ \ \ \ (2)$

where ${f}$ is the periodic extension of the function ${|\theta|}$ for ${\theta \in [-\pi,\pi]}$. The formula above is obtained by calculating the length of the global geodesic from the identity to ${\sigma = U \Lambda U^{-1}}$, given by

$\displaystyle \gamma(t) = U \text{Diag}(t,tf(2\pi /n), tf(4 \pi/n), \ldots, tf(2(n-1) \pi/n)) U^{-1}. \ \ \ \ \ (3)$

The infinitesimal Riemannian distance ${\gamma'(t)}$ on ${SU(n)}$ coincides with Hilbert Schmidt length, hence can be calculated easily.
More generally, if ${\sigma}$ has cycle types ${(a_1,a_2, \ldots, a_k)}$, then it can be put in block diagonal form, where an ${a \times a}$ block has eigenvalues ${e^{2\pi i j/a}}$, ${j =0,\ldots, a-1}$. Thus

$\displaystyle \rho_0(\sigma) = \sqrt{\sum_{j=1}^k \sum_{s=1}^{a_j} f(2\pi s/n)^2}. \ \ \ \ \ (4)$

Thus we see explicitly that ${\rho_0}$ is a class function. We call a function ${g}$ a square-root like function if it is concave increasing function ${g}$ on ${{\mathbb R}_+}$ that vanishes at ${0}$. By precomposing ${\rho_0}$ with any square-root like function ${g}$, we get a new class function ${g \circ \rho_0}$ that induces a new bi-invariant metric on ${S_n}$. Thus we have an infinite family of bi-invariant metric on any finite group ${G}$. It seems sensible to define a partial ordering on the set of bi-invariant metrics on ${G}$ with ${\rho > \rho'}$ if ${\rho' = g \circ \rho}$ for some square-root like function ${g}$. One just has to check that ${(g_1 \circ g_2)''< 0}$ for ${g_1,g_2}$ both square-root like.