Word Metric is a Metric

Theorem

Let $\left({G, \circ}\right)$ be a group, and let $S$ be a generating set for $G$ which is closed under inverses (that is, $x^{-1} \in S \iff x\in S$).

Let $d_S$ be the associated word metric.

Then $d_S$ is a metric on $G$.

Proof

Let $g, h \in G$.

It is given that $S$ is a generating set for $G$.

It follows that there exist $s_1, \ldots, s_n \in S$ such that $g^{-1} \circ h = s_1 \circ \cdots \circ s_n$.

Therefore $d_S \left({g, h}\right) \le n$, establishing that $\R$ is a valid codomain for the mapping $d_S$ with domain $G \times G$.

This is the form a mapping must have to be able to be a metric.

Now checking the other defining properties for a metric in turn:

M1

Clearly the empty sequence can be formed with elements from $S$.

It also has length zero.

Therefore, we have for any $g \in G$ that $d_S \left({g, g}\right) = 0$.

M2

Let $g, h, k \in G$. Let $d_S \left({g, h}\right) = n, d_S \left({h, k}\right) = m$.

Let $s_1, \ldots, s_n, r_1, \ldots, r_m \in S$ be such that:

$g^{-1} \circ h = s_1 \circ \cdots \circ s_n$

$h^{-1} \circ k = r_1 \circ \cdots \circ r_m$

From these equations, obtain:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle g^{-1} \circ k\)	\(=\)	\(\displaystyle \left({g^{-1} \circ h}\right) \circ \left({h^{-1} \circ k}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({s_1 \circ \cdots \circ s_n}\right) \circ \left({r_1 \circ \cdots \circ r_m}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \implies\)	\(\displaystyle \)	\(\displaystyle g \circ s_1 \circ \cdots s_n \circ r_1 \circ \cdots r_n\)	\(=\)	\(\displaystyle k\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Therefore, $d_S \left({g, k}\right) \le m +n = d_S \left({g, h}\right) + d_S \left({h, k}\right)$.

M3

Let $g, h \in G$. Let $d_S \left({g, h}\right) = n$.

Furthermore, let $s_1, \ldots, s_n \in S$ be such that:

$g^{-1} \circ h = s_1 \circ \cdots \circ s_n$

From Inverse of Group Product, obtain:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({g^{-1} \circ h}\right)^{-1}\)	\(=\)	\(\displaystyle \left({s_1 \circ \cdots \circ s_n}\right)^{-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle h^{-1} \circ g\)	\(=\)	\(\displaystyle s_n^{-1} \circ \cdots \circ s_1^{-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

By assumption $S$ is closed under taking inverses, and hence the latter expression yields a valid sequence for the metric $d_S$.

It follows that $d_S \left({h, g}\right) \le d_S \left({g, h}\right)$.

Switching the roles of $g$ and $h$ in the above, we obtain the converse inequality, and hence equality.

M4

There is only one word of length zero, namely the empty word.

However, the empty word sends an element $g$ to itself.

Hence $g, h \in G, g \ne h \implies d_S \left({g, h}\right) > 0$.

Thus $d_S$ is a metric.

$\blacksquare$