10
$\begingroup$

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

Suppose we have two square $3 \times 3$ 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!

  • 0
    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 \, )$.2011-05-14
  • 0
    did you figure out why you got 30%? I guess you should get something of the order of 43% when simulating the problem.2011-05-17
  • 0
    @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.2011-05-17

2 Answers 2

6

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\%.$$

2

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.

  • 0
    Where? How exactly?2011-05-14
  • 0
    It looks very interesting! I will look into it more deeply tomorrow. I didn't know that this problem had any actual applications (I posed it to myself a while ago :))2011-05-14
  • 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.2011-05-14
  • 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.2011-05-15
  • 0
    joriki makes my remark much more precise but I was trying to make the exact same point. I fully agree with him (and my intuition tells me that Gerry's right as well). I repeat: could you please point to the place where this question is answered in that paper?2011-05-15
  • 0
    @Theo: I saw that in the introduction part and gave the link. In the introduction part it is given that *we will show below that the probability 2 integer matrices have relatively prime determinants is \frac{1}{3}*. So on seeing this i thought this link could be useful.2011-05-15
  • 0
    @Theo: And if you are asking a question directed to me please use @user. So that I can understand you want to ask/convey something to me.2011-05-15
  • 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.2011-05-15
  • 0
    @Theo: Should i delete it now.2011-05-15
  • 0
    @Theo: I have made it *Community Wiki*. thats the best i could do.2011-05-15
  • 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.2011-05-15