Word Metric is Metric
 | This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
Theorem
Let $\struct {G, \circ}$ be a group.
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 $\map {d_S} {g, h} \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:
Metric Space Axiom $(\text M 1)$
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 $\map {d_S} {g, g} = 0$.
Thus Metric Space Axiom $(\text M 1)$ is seen to be fulfilled.
$\Box$
Metric Space Axiom $(\text M 2)$: Triangle Inequality
Let $g, h, k \in G$.
Let $\map {d_S} {g, h} = n, \map {d_S} {h, k} = 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:
| \(\ds g^{-1} \circ k\) | \(=\) | \(\ds \paren {g^{-1} \circ h} \circ \paren {h^{-1} \circ k}\) | ||||||||||||
| \(\ds \) | \(=\) | \(\ds \paren {s_1 \circ \cdots \circ s_n} \circ \paren {r_1 \circ \cdots \circ r_m}\) | ||||||||||||
| \(\ds \leadsto \ \ \) | \(\ds g \circ s_1 \circ \cdots s_n \circ r_1 \circ \cdots r_n\) | \(=\) | \(\ds k\) |
Therefore, $\map {d_S} {g, k} \le m + n = \map {d_S} {g, h} + \map {d_S} {h, k}$.
Thus Metric Space Axiom $(\text M 2)$: Triangle Inequality is seen to be fulfilled.
$\Box$
Metric Space Axiom $(\text M 3)$
Let $g, h \in G$.
Let $\map {d_S} {g, h} = 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:
| \(\ds \paren {g^{-1} \circ h}^{-1}\) | \(=\) | \(\ds \paren {s_1 \circ \cdots \circ s_n}^{-1}\) | ||||||||||||
| \(\ds h^{-1} \circ g\) | \(=\) | \(\ds s_n^{-1} \circ \cdots \circ s_1^{-1}\) |
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 $\map {d_S} {h, g} \le \map {d_S} {g, h}$.
Switching the roles of $g$ and $h$ in the above, we obtain the converse inequality, and hence equality.
Thus Metric Space Axiom $(\text M 3)$ is seen to be fulfilled.
$\Box$
Metric Space Axiom $(\text M 4)$
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 \map {d_S} {g, h} > 0$.
Thus Metric Space Axiom $(\text M 4)$ is seen to be fulfilled.
$\Box$
Thus $d_S$ is a metric.
$\blacksquare$