# Prime/undecomposable matrices

Prime matrices as defined in the following paper Prime matrices P. F. RIVETT AND N. I. P. MACKINNON carry over many properties of factorization as in natural numbers to matrices over the field of naturals.

I quote the following:

A matrix in a set M of matrices is prime (naturally enough) if it is not the product of any other matrices in the set. We thought we would look for the prime matrices in the set M of all 2 x 2 matrices with entries in the non negative integers and with determinant 1. To our great surprise we discovered that: there are only two primes, and any member of M (except I) can be uniquely factorized into a product of those two.

[EDIT (PLC): For some reason, there seems to be some confusion on which two matrices are in question. They are as follows:]

$$P = \left( \begin{array}{cc} 1 & 0 \\ 1 & 1 \end{array} \right),\ \ Q = \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array} \right)$$

My question is whether there are any other resources on prime matrices and if there has been any generalization beyond 2x2 matrices. What mathematics will I need to pursue the subject further?

I have only three journal articles:

Thanks.

-
But these (I mean thw two matrices) are the two generators, $T=[1,1;0,1]$ and $S=[0,1;-1,0]$ of the modular group! Look at Wikipedia article or better in Serre's "Course in arithmetic". – Wadim Zudilin May 27 '10 at 8:40
These are $\textit{group}$ generators, their inverses aren't in the set. Cf my comment to coudy's answer. – Victor Protsak May 27 '10 at 9:14
Victor, today you really puzzle me: if only nonnegative integers are allowed, then $S$ is missed, so what are the two prime matrices?! Well, if one considers only positive powers, then $T^{-1}$ has to be included as well. But having determinant 1, so staying inside the modular group has no analogy with the prime factorisation in $\mathbb Z$. I guess that the author is just curious... – Wadim Zudilin May 27 '10 at 10:36
T and its transpose seem to work: you can "simplify" any matrix in M by multiplying it (left or right) by the inverse of T or its transpose. – Homology May 27 '10 at 11:35
@Wadim. Thanks. I have found Course in Arithmetic to be helpful in this regard. But there it says S is [0,-1;1,0].... Never mind – Unknown May 27 '10 at 12:26

For a different point of view, you might like to take a look at Section 12.5 and Appendix A in the free on-line version of the following book (in which you'll find some interesting open questions related to "prime matrices" of the type you described):

N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002.

-
Quite helpful!! – Unknown May 27 '10 at 17:47
In this book, prime matrices are termed "undecomposable matrices " – Unknown Jun 4 '10 at 0:56

I would suggest to have a look at books on fuchsian groups, e.g. Beardon, "the geometry of discrete groups", or S. Katok, "fuchsian groups".

They don't talk about primitive matrices in your sense, but really, that's just because that's not the terminology used in the field.

For example, the fact that any integer matrices can be expressed as a product of powers of finitely many elements, is a consequence of the following general result.

The group $SL_2(Z)$ has finite covolume in $SL_2(R)$. That means that the volume of $SL_2(Z)\backslash SL_2(R)$ is finite, and that implies that $SL_2(Z)$ is finitely generated: there exists a finite number of generators such that any element in $SL_2(Z)$ is a product of positive powers of these generators. There may be several ways to express an element in term of these generators, though.

Any discrete subgroup of $SL_2(Z)$ with finite covolume is in fact finitely generated. Uniqueness of the decomposition is not always granted, one has to dive a little deeper into the structure of $SL_2(Z)$ to understand why that holds in that particular case. Let me point out two remarkable properties of that group that ultimately explain why there is uniqueness. First the two standard generators are conjuguated to their inverses, and that allows to take positive powers in the decomposition. And second, $SL_2(Z)$ contains a subgroup of index six which is a free group, so that uniqueness holds trivially for that subgroup. That subgroup is the set of integer matrices that are congruent to the identity modulo 2.

So I think you can get much insight from these books, even if they don't talk about primitive matrices per se.

-
You are missing the point: OP's matrices have $\textit{non-negative}$ entries (even if he mistakenly spoke of "FIELD of naturals"), and in semigroups, almost nothing works in the same way as in groups. E.g. there was a recent MO discussion of the fact that non-negative integer matrices for $n\geq 3$ are not f.g. – Victor Protsak May 27 '10 at 9:12
@Victor. My question was not addressing if the decomposition holds in higher dimension, but if it holds for fuchsian groups, for example for the subgroups of $SL_2(Z)$ obtained from the congruence subgroups. Let me be more specific. You can't have such decomposition for the derived subgroup of the principal congruence subgroup of level 2 because that group is infinitely generated. Sorry for not being clear. – coudy May 27 '10 at 11:28
Right! I was a bit hasty. Not "the field of naturals" just the naturals. – Unknown May 27 '10 at 12:13
I'm a bit confused as to why this is the accepted answer. The question is about free monoids and this answer discusses not necessarily free groups. – Pete L. Clark May 27 '10 at 14:11