Prime/undecomposable matrices

Question

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:

1.On prime matrices over distributive lattices

2.Algorithm for obtaining the proper relatively prime matrices of polynomial matrices

3.Prime matrices

Please specify whether I can get the article/journal or book for free.

Thanks.

Answer 1

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.

Answer 2

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.

Answer 3

I got the results, which I'll describe below, for my own pleasure, without consulting anything, in 1971/2 in Ann Arbor, then I had a private seminar for a few kids at the U. of Texas at Austin in the fall of 1972, nothing official. The main topic was an elementary theory of diophantine approximations. Otherwise, I considered these things to be well known and even classic hence it was an end of the story to me. (I feel that Minkowski knew these things anyway). I also learned casually that there is some knowledge of this topic in computer science.

Let $\ SL(Z_{\ge 0})\ $ be the monoid of matrices with non-negative integer entries, which have determinant equal 1.

THEOREM $\ SL(Z_{\ge 0})\ $ is a free monoid which has a $2$-element free base consisting of $$ L\ :=\ \left[\begin{array}{cc} 1 & 0\\ 1 & 1\end{array}\right]\qquad \mbox{and}\qquad R\ :=\ \left[\begin{array}{cc} 1 & 1\\ 0 & 1\end{array}\right]. $$

PROOF (a sketch) Consider the infinite table:

$$ \left[\begin{array}{cccccccccccccccc} 1/0 &&&&&&&&&&&&&&&& 0/1 \\ 1/0 &&&&&&&& 1/1 &&&&&&&& 0/1 \\ 1/0 &&&& 2/1 &&&& 1/1 &&&& 1/2 &&&& 0/1 \\ 1/0 && 3/1 && 2/1 && 3/2 && 1/1 && 2/3 && 1/2 && 1/3 && 0/1 \\ 1/0 & 4/1 & 3/1 & 5/2 & 2/1 & 5/3 & 3/2 & 4/3 & 1/1 & 3/4 & 2/3 & 3/5 & 1/2 & 2/5 & 1/3 & 1/4 & 0/1 \\ \end{array}\right] $$ etc.

It's a pleasant(!) exercise to show that every matrix $\ M\in SL(Z_{\ge 0})\ $ appears in the above table in exactly one row, in an exactly one place -- just remove the quotient signs ''$/$'', treat each fraction as a 2-dimensional (vertical) vector.

Observe that the fractions in each row go down from $\ \infty\ $ to $\ 0.\ $ I call a pair of such fractions (always reduced in this table) to be neighbors. Any reduced fraction which is between two neighbors has its denominator equal at least the sum of the denominators of the said neighbors.

End of Proof (well, of the sketch).

REMARK I saw later a computer science text which features the above table, and a name was attached to this table.

REMARK I remember that in one of the 2 volumes of Development of the Minkowski Geometry of Numbers by Harris Hancock, there was one line of the above table, perhaps only the half of the line between $0/1$ and $1/1$ (in this order, I think, which is reverse to the order above). I have a feeling that Minkowski knew what I have learned and you can see right now, that there is an increasing function of $[0;\infty]$ onto itself which maps non-negative rational numbers of the form $\ k/2^n\ $ onto the entire set of non-negative numbers $\ \mathbb Q_{\ge 0}\ := \mathbb Q\cap[0;\infty],\ $ and that this mapping maps $\ \mathbb Q_{\ge 0}\ $ onto the set of all non-negative numbers consisting of the rational numbers and of quadratic irrationals.

REMARK This table is very closely related to continued fractions (another exercise).

I don't know any references but for the two mentioned above (about Minkowski and a computer science textbook) -- sorry for this.

Answer 4

One can consider an alternative concept of prime matrix as follows:

A matrix $A\in M_n(\mathbb{Z})$ is prime if for any factorization $A=BC$ we have either $Det(B)\in \{-1,1\}$ or $Det(C)\in \{-1,1\}$. So we may ask for existence of a singular prime matrix thanks to the fact that every singular matrix is a product of idempotents . On the other hand one may investigate the question of uniquness of factorization of elements of $M_n(\mathbb{Z})\cap GL(n,\mathbb{R})$, module $\pm SL(n,\mathbb{Z})$.