14
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ 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". $\endgroup$ – Wadim Zudilin May 27 '10 at 8:40
  • 5
    $\begingroup$ These are $\textit{group}$ generators, their inverses aren't in the set. Cf my comment to coudy's answer. $\endgroup$ – Victor Protsak May 27 '10 at 9:14
  • 2
    $\begingroup$ 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... $\endgroup$ – Wadim Zudilin May 27 '10 at 10:36
  • 2
    $\begingroup$ 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. $\endgroup$ – Homology May 27 '10 at 11:35
  • 1
    $\begingroup$ @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 $\endgroup$ – Unknown May 27 '10 at 12:26
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Quite helpful!! $\endgroup$ – Unknown May 27 '10 at 17:47
  • 1
    $\begingroup$ In this book, prime matrices are termed "undecomposable matrices " $\endgroup$ – Unknown Jun 4 '10 at 0:56
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Victor Protsak May 27 '10 at 9:12
  • 2
    $\begingroup$ @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. $\endgroup$ – coudy May 27 '10 at 11:28
  • 1
    $\begingroup$ Right! I was a bit hasty. Not "the field of naturals" just the naturals. $\endgroup$ – Unknown May 27 '10 at 12:13
  • 4
    $\begingroup$ 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. $\endgroup$ – Pete L. Clark May 27 '10 at 14:11
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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})$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.