This is from Artin's Algebra(2nd Edition) Ch.2 M.15. The question is:
"Determine the semigroup generated by the two real elementary matrices $A=\left(\begin{array}{cc} 1 & 1\\ 0 & 1 \end{array}\right)$ and $B=\left(\begin{array}{cc} 1 & 0\\ 1 & 1 \end{array}\right)$, and prove that every element of $S$ can be expressed uniquely as a product of the two matrices."
What I know so far: if $\left(\begin{array}{cc} a & b\\ c & d \end{array}\right)=B^{b_{1}}A^{a_{1}}\cdots B^{b_{k}}A^{a_{k}}$, where $a_i$ and $b_i$ are positive integers, then
- $a,b,c,d$ are all positive integers, and $\gcd(a,c)=\gcd(b,d)=1$, and
- $a/c$ and $b/d$ can be expressed as continued fractions: $$\frac{a}{c}=\frac{1}{b_{1}+\frac{1}{a_{1}+\cdots\frac{1}{a_{k-1}+\frac{1}{b_{k}}}}},$$ $$\frac{b}{d}=\frac{1}{b_{1}+\frac{1}{a_{1}+\cdots\frac{1}{b_{k}+\frac{1}{a_{k}}}}}.$$
I have not come up with a way to prove the uniqueness. I also believe that there must be some better representation of $S$. Can anyone help me? Thanks.
If $M=\pmatrix{r&s\\t&u}$ is a nonsingular matrix with nonnegative integer matrices, then $AM=\pmatrix{r+t&s+u\\t&u}$ so the first row minus the second row of $AM$ is a nonnegative nonzero row vector. Similarly taking the first row minus the second row of $BM$ gives a non-positive row vector. Therefore in a product of $A$s and $B$s we can detect uniquely whether the first matrix is $A$ or $B$. Cancelling that and repeating, then we can determine uniquely the entire sequence of $A$s and $B$s.