# Inverse of a monoid homomorphism

It is a well-known fact that

$f\colon a \mapsto \left(\begin{array}{cc} 1 & 1\\ 0 & 1\\ \end{array}\right), ~ b \mapsto \left(\begin{array}{cc} 1 & 0\\ 1 & 1\\ \end{array}\right)$

is a monomorphism from the free monoid generated by $a$ and $b$ to the matrix monoid $\mathbb{Z}^{2\times 2}$.

1. Is there an efficient algorithm which computes the length of $f^{-1}(X)$ from $X \in \mathbb{Z}^{2\times 2}$ (that is, the number of symbols in corresponding word $x$, if $f^{-1}(X) = \{x\}$)?

2. Is there an efficient algorithm which computes $f^{-1}(X)$ from $X \in \mathbb{Z}^{2\times 2}$?

3. Is there a standard reference for this problem?

-

Yes; see the Wikipedia article on Smith normal form. In two dimensions you are essentially using the Euclidean algorithm.

Edit: The basic observation here is that if $M = \left[ \begin{array}{cc} x & y \\\ z & w \end{array} \right]$ is an integer matrix, then

$$M f(a^{-1}) = \left[ \begin{array}{cc} x & y - z \\\ z & w - z \end{array} \right]$$

and similarly

$$M f(b^{-1}) = \left[ \begin{array}{cc} x - y & y \\\ z - w & w \end{array} \right].$$

If in addition $\det M = 1$ and $x, y, z, w$ are non-negative integers, then exactly one of these operations will give a matrix with the same properties (this is equivalent to $f$ being a monomorphism). So, as I said, essentially one is performing the Euclidean algorithm on the columns (or, if you multiply from the left instead, on the rows).

As an example, if $M = \left[ \begin{array}{cc} 8 & 5 \\\ 3 & 2 \end{array} \right]$, then

$$M f(b^{-1}) = \left[ \begin{array}{cc} 3 & 5 \\\ 1 & 2 \end{array} \right]$$

$$M f(b^{-1} a^{-1}) = \left[ \begin{array}{cc} 3 & 2 \\\ 1 & 1 \end{array} \right]$$

$$M f(b^{-1} a^{-1} b^{-1}) = \left[ \begin{array}{cc} 1 & 2 \\\ 0 & 1 \end{array} \right] = f(aa)$$

hence $M = f(aabab)$ as desired.

-
I recall it from a proof of structure theorem for finitely generated modules over PIDs. But I don't see how to apply it here. Could you elaborate on this? – Alexis Nov 20 '10 at 0:53
The algorithm for writing a matrix in Smith normal form is precisely the algorithm you want. Like I said, it's essentially the Euclidean algorithm. You can also think about it as a form of row reduction. – Qiaochu Yuan Nov 20 '10 at 11:20
f (aabab) = [[8,5],[3,2]]. Its SNF is [[1,0],[0,1]]. How does it help to recover aabab (or its length = 5) from [[8,5],[3,2]]? – Alexis Nov 20 '10 at 12:41
@Alexis: you need to keep track of the intermediate steps, not just the final answer. I will edit with an example. – Qiaochu Yuan Nov 20 '10 at 13:33
Thanks! – Alexis Nov 20 '10 at 13:43