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.


About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s