Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a question that is not of particular significance, but I would love to understand the underlying principles.

Suppose we have two square 3x3 matrices, $M_1$ and $M_2$ with

$$M_1 = \begin{pmatrix} a_1 & a_2 & a_3 \\ a_4 & a_5 & a_6 \\ a_7 & a_8 & a_9 \end{pmatrix} \qquad\text{and}\qquad M_2 = \begin{pmatrix} b_1 & b_2 & b_3 \\ b_4 & b_5 & b_6 \\ b_7 & b_8 & b_9 \end{pmatrix}$$

with the coefficients $a_n,b_n \in \mathbb{Z}$ and $1 \leq a_n,b_n \leq 9$

What is the probability that the matrices' determinants are coprime, when uniformly random coefficients satisfying the conditions are chosen.

I am familiar with the Riemann's $\zeta$ function way to find out the probability of two random integers being coprime, but I have no clue how to apply that here with additional conditions on the numbers given.

I did test it mechanically, using Mathematica and the result is around 30%, but I would like to see a proper way to do it.

I would love to at least get a few pointers as what to research to tackle this problem.

Thank you very much!

share|improve this question
    
Don't know anything about your result, but let me state this one : If $A = (a_{ij})$ and $B = (b_{ij})$ with $a_{ij} \equiv b_{ij} (\, \mathrm{mod} \, m \,)$ for some $m$ then $\det(A) \equiv \det(B) (\, \mathrm{mod} \, m \, )$. –  Patrick Da Silva May 14 '11 at 18:42
    
did you figure out why you got 30%? I guess you should get something of the order of 43% when simulating the problem. –  Fabian May 17 '11 at 7:17
    
@Fabian: That was a while a go, so I don't really remember well, what the exact results were. I was using a Monte-Carlo algorithm to test on a relatively small sample. Quite possibly it was about 37% or even more. –  Tibor May 17 '11 at 10:08

2 Answers 2

up vote 6 down vote accepted

This answer was obtained numerical, but it is nevertheless exact

There are $N=9^9$ possibilities to choose the matrix $m$ (each with equal probability). There are 1913 possible outcomes for $\det m$. The most likely is $\det m =0$. The probability for this event is $$P[\det m = 0] = \frac{218605}{14348907} \approx 1.5\%.$$ The rest is distributed over different integer number. The largest determinant is a matrix with $\det m = 1216$. There are 3 possibilities for this matrix (therefore the probability is $P[\det m = 1216] = 3/N$). There are also 3 matrices for which $\det m=-1216$. (in fact this is always true. If there are $n$ matrices with $\det m= x$ then there are exactly $n$ matrices with $\det m=-x$). To find out if the determinants are coprime the sign does not matter, therefore we only need to know the probabilities $$P[|\det m| = x].$$ Generically, the probability decreases for increasing $\det m$.

The absolute value of the determinant may assume 957 values. Therefore, there are $957*(957+1)/2 =458403$ pairs of matrices $m_1$ and $m_2$. Out of them there are 274487 pairs coprime. (The fraction of matrices which are coprime is $274487/458403 \approx 60\%$)

Counting each of the pair of matrices $m_1, m_2$ with the proper probability, we obtain the probability that two matrices are coprime $$P[ m_1 \text{ and } m_2 \text{ are coprime}]= \frac{7253958722902984}{16677181699666569} \approx 43\%.$$

share|improve this answer

This paper actually shows that the probability two large matrices with integer entries are co-prime is $\frac{1}{3}$, which actually is a bigger version of your question.

share|improve this answer
    
Where? How exactly? –  t.b. May 14 '11 at 19:23
1  
Are you sure the case $1\le a_n, b_n \le 9$ is addressed there? All I see are probabilities defined as limits for the upper bound on the numbers going to infinity. –  joriki May 14 '11 at 21:39
1  
The case $1\le a_n,b_n\le9$ is a finite (albeit extremely large) calculation, I doubt there will be any nice answer, no doubt that's why calculations are done for limits. I suspect for the finite case one can't do any better than to run a large and well-distributed sample and take that as an estimate. –  Gerry Myerson May 15 '11 at 0:36
1  
@Chandru1: ok, will do. You missed an important part (and you didn't quote verbatim in your last comment): The authors write: "We show below that the probability that two large integer matrix have coprime determinant is about $1/3$." (my emphasis). The results are of an asymptotic nature and thus do not address the specific question of the OP. Of course, I agree that this is related to the question, but please read closely before you claim a certain paper you obviously haven't even looked at properly contains an answer to a question. As it is, this is at best worth a comment. –  t.b. May 15 '11 at 7:22
1  
@Chandru1: No, please don't (edit: I mean don't delete it - CW is fine). But please update this answer and point out what emerged from this discussion, i.e., the paper does not quite address the question at hand and state that what it contains are asymptotic results showing that for large $n$ the probability approaches approximately $1/3$ and thus sort of supports the result obtained by the OP experimentally. –  t.b. May 15 '11 at 7:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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