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

-

## 1 Answer

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9131439924240112, "perplexity_flag": "head"}