# 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$