Author |
Topic: Determinant of Matrix Modulo n (Read 659 times) |
|
Michael Dagg
Senior Riddler
Gender: 
Posts: 500
|
 |
Determinant of Matrix Modulo n
« on: Nov 26th, 2005, 6:08pm » |
 Quote  Modify
|
Let An be the n x n matrix [aij] defined by
/ ij (mod n), if n does not divide ij
aij = |
\ n, if n divides ij.
Find det(An), for n >= 1.
|
|
 IP Logged |
Regards,
Michael Dagg
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Determinant of Matrix Modulo n
« Reply #1 on: Nov 26th, 2005, 9:16pm » |
Quote Modify
|
Ah. I had to compute the first 8 to see what's going on:
First define
[ x ] = -floor(-x)-1 = floor(x - epsilon),
so that for i=2,...,n, after subtracting i*(row 1) from (row i), we have
aij - ij = -n*[ ij/n ]
in the i,j-th spot (i>1). Note that the first column is now (1,0,...0), so
det(A) = (-n)n-1 det([ij/n])i,j>1.
Now if n=5 or n>6, we may pick 1 < k < n/2 relatively prime to n (if n=2m+1, take k=m; if n=4m or 4m+2, k=2m-1). Then for 1< i < n, ik/n is not an integer, so
[ ik/n ] + [ i(n-k)/n ] = i-1 = [ i(n-1)/n ].
And if i=n, we have
[ k ] + [ n-k ] = n-2 = [ n-1 ].
It follows that (col k) + (col n-k) = (col n-1) in the (n-1)x(n-1) matrix ([ij/n])i,j>1, so det(A)=0.
It's a simple matter to compute
det(A1) = 1, det(A2) = -2, det(A3) = 32, det(A4) = 43, det(A6) = -65.
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Determinant of Matrix Modulo n
« Reply #2 on: Nov 27th, 2005, 6:13am » |
Quote Modify
|
Nicely done.
Your solution is shorter than mine for I made use of the Euler phi-function, phi(n), to characterize integers less than n that are relatively prime to n with phi(n) >= 4, and then except when n = 1,2,3,4, or 6.
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print