Determinant of GCD Matrix

We shall prove a general result as follow : Let $A$ be a $n \times n$ matrix, with entries $a_{ij}=\gcd(i,j)$ for $1 \le i,j \le n$ . Then $\displaystyle \det(A) = \prod_{i=1}^n \varphi(i)$ , where $\varphi(i)$ is the Euler's totient function.

Proof : Let the matrix $S=(s_{ij})$ be an $n \times n$ matrix defined as follow : $s_{ij} = e_{ij} \cdot \sqrt{\varphi(j)}$ , where $e_{ij}=1$ if $j \mid i$ , otherwise $e_{ij}=0$ . The $ij$ -th element of $SS^t$ ( $S^t$ is the transposed matrix of $S$ ) is :

$\displaystyle (SS^t)_{ij} = \sum_{k=1}^n s_{ik}s_{jk} = \sum_{k \mid i, k \mid j} \varphi(k) = \sum_{k \mid \gcd(i,j)} \varphi(k) = \gcd(i,j)$

Therefore, $SS^t = A$ . Note that $S$ is a lower triangular matrix with the elements on the main diagonal are $\sqrt{\varphi(i)}, \, i=\overline{1,n}$ , we have $\displaystyle \det(A)=\det(SS^t)=\big(\det(S)\big)^2=\prod_{i=1}^n \varphi(i)$ . (Q.E.D.)

Now come back with the origin problem, set $n=16$ , we have $\displaystyle \det(A)=\prod_{i=1}^{16} \varphi(i) = 3397386240$ . Then the last 3 digits of $\det(A)$ are $240$ .

determinant of 1 1 1 1 1 1 1 1 1 2 1 2 1 2 1 2 1 1 3 1 1 3 1 1 1 2 1 4 1 2 1 4 1 1 1 1 5 1 1 1 1 2 3 2 1 6 1 2 1 1 1 1 1 1 7 1 1 2 1 4 1 2 1 8 c8=c8-c4,c7=c7-c1,c6=c6-c2,c5=c5-c1,c4=c4-c2,c3=c3-c1,c2=c2-c1 matrix becomes 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 2 0 0 2 0 0 1 1 0 2 0 0 0 0 1 0 0 0 4 0 0 0 1 1 2 0 0 4 0 0 1 0 0 0 0 0 6 0 1 1 0 2 0 0 0 4 r6=r6-r3,c4=c4-1/2 c8,c2=c2-1/4 c8,c1=c1-1/4 c8-1/6 c7-1/4 c5,r2=r2-r1, matrix becomes 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 2 0 0 2 0 0 1 1 0 2 0 0 0 0 0 0 0 0 4 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 4 now the determinant is=1 1 1 2 2 4 2 6*4=768

First find the LU decomposition of matrix A such that LU=A where L is a lower triangular and U is an upper triangular matrix.

Let L and U be two n \times n matrices

L {i,j} = 1 if j|i L {i,j} = 0 otherwise

U {i,j} = \phi if i|j \phi is euler quoitent function (returns number of +ve integer less than n and coprime with n) U {i,j} = 0 otherwise

compute (i,j)th entry of LU LU {i,j} = \displaystyle \sum {k=1}^16 L {i,k} U {k,j} = gcd(i,j)

Hence det(A) = det(LU) = det(L)*det(U) = \prod_{i=1}^{16} \phi (i) = 3397386240

Let $\phi(N)$ be Euler's phi function , which is the number of integers smaller than $N$ that are coprime to $N$ .

Claim: $\displaystyle \sum_{k | N} \phi(k) = N$ .

Proof: Treat the LHS as $\displaystyle \sum_{k |N} \sum_{\gcd (i, k)=1} 1$ . We will prove this statement by establishing a bijection between each term in the LHS and a positive integer $n \leq N$ . For each positive integer $n \leq N$ , construct the unique pair of integers $\left (\frac {N} {\gcd(n,N)}, \frac {n} {\gcd(n,N)} \right)$ . In this pair, the first number divides $N$ , while the second number is coprime to the first number. Conversely, given an integer $k$ that divides $N$ , and an integer $i \leq k$ with $\gcd(i,k)=1$ , we can construct the integer $\frac {i \times N} {k} \leq N$ . It is clear that these two functions are inverses of each other, so we have established a bijection. Clearly there are $N$ positive integers less than or equal to $N$ , and counting the pairs $(k,i)$ , the sum is $\sum_{k|N} \phi(k)$ . $_\square$

Let $B$ be an 8 by 8 matrix with entries

$b_{i,j} = \begin{cases} \sqrt{\phi(j)} & \mbox{ if } j | i \\ 0 & \mbox{ otherwise } \\ \end{cases}$

We calculate that the $(i,j)$ entry in $BB^T$ is given by $\displaystyle \sum_{k|i, k|j} \sqrt{\phi(k)} \sqrt{\phi(k)} = \sum_{k|\gcd(i,j)} \phi(k) = \gcd (i,j)$ by the above claim.

Hence $B B^T = A$ . Since $B, B^T$ are triangular matrices, we can easily calculate that

$\begin{aligned} \det(A) = \det (B B^T) &= \det(B)\det(B^T) \\ &= \left(\prod_{i=1}^{16} \sqrt{\phi(i)}\right)^2 \\ &= \prod_{i=1}^{16} \phi(i) \\ &= 1 \times 1 \times 2 \times 2 \times 4 \times 2 \times 6 \times 4 \times 6 \times 4 \times 10 \times 4 \times 12 \times 6 \times 8 \times 8\\ \end{aligned}$

The last 3 digits are $240$ .

given that A is a 16X16 matrix, with entries ai,j=gcd(i,j) for 1≤i,j≤16

using LU decomposition method

The (i,j)'th entry of L(a 16X16 matrix) is

[L]i,j={1 if j|i } or {0 otherwise} ( where j|i means j is a divisor of i)

and for U we have

[U]i,j={φ(j) if i|j} or {0 otherwise}

here we have L a lower triangular matrix while U is an upper triangular matrix.

now compute the (i,j)'th entry of LU

[LU]i,j = ∑(k=1 to k=16) { [L]i,k * [U]j,k } = ∑(k|i and k|j) φ(k)=gcd(i,j)

this proves that LU=A and since det(A)=det(L)det(U) we deduce

det(A)=∏(i=1 to i=16) φ(i)Let p1, p2…, pm be distinct prime factors of n.

As it is known, the totient function of n equals:

φ(n) = n(1 – 1/p1)…(1 – 1/pm)we have

φ(1) = 1

φ(2) = 2*(1-1/2) = 1

φ(3) = 3*(1-1/3) = 2

φ(4) = 4*(1-1/2) = 2

φ(5) = 5*(1-1/5) = 4

φ(6) = 6(1-1/2)(1-1/3) = 2

φ(7) = 7*(1-1/7) = 6

φ(8) = 8*(1-1/2) = 4

φ(9) = 9*(1-1/3) = 6

φ(10) = 10(1-1/2)(1-1/5) = 4

φ(11) = 11*(1-1/11) = 10

φ(12) = 12(1-1/2)(1-1/3) = 4

φ(13) = 13*(1-1/13) = 12

φ(14) = 14(1-1/7)(1-1/2) = 6

φ(15) = 15(1-1/3)(1-1/5) = 8

φ(16) = 16*(1-1/2) = 8

therefore we have det(A)=∏(i=1 to i=16) φ(i) = φ(1)φ(2)φ(3) .......φ(15) φ(16) = (2^22) (3^4)*10 whose last three digits are 240.

hence answer is 240

Let A be an 16 by 16 matrix, with entries ai,j=gcd(i,j) for 1≤i,j≤16

using LU decomposition method

Define two 16×16 matrices L,U in the following way. The (i,j)'th entry of L is

[L]i,j={1 if j|i or 0 otherwise} ( where j|i means j is a divisor of i)

and for U we have

[U]i,j={φ(j) if i|j or 0 otherwise}

here we have L a lower triangular matrix while U is an upper triangular matrix. Let us compute the (i,j)'th entry of LU

[LU]i,j = ∑(k=1 to k=16) { [L]i,k * [U]j,k } = ∑(k|i and k|j) φ(k)=gcd(i,j)

this proves that LU=A and since det(A)=det(L)det(U) we deduce

det(A)=∏(i=1 to i=16) φ(i)

Let p1, p2…, pm be distinct prime factors of n. As it is known, the totient function of n equals:

φ(n) = n(1 – 1/p1)…(1 – 1/pm)

we have φ(1) = 1

φ(2) = 2*(1-1/2) = 1

φ(3) = 3*(1-1/3) = 2

φ(4) = 4*(1-1/2) = 2

φ(5) = 5*(1-1/5) = 4

φ(6) = 6 (1-1/2) (1-1/3) = 2

φ(7) = 7*(1-1/7) = 6

φ(8) = 8*(1-1/2) = 4

φ(9) = 9*(1-1/3) = 6

φ(10) = 10 (1-1/2) (1-1/5) = 4

φ(11) = 11*(1-1/11) = 10

φ(12) = 12 (1-1/2) (1-1/3) = 4

φ(13) = 13*(1-1/13) = 12

φ(14) = 14 (1-1/7) (1-1/2) = 6

φ(15) = 15 (1-1/3) (1-1/5) = 8

φ(16) = 16*(1-1/2) = 8

therefore we have det(A)=∏(i=1 to i=16) φ(i) = φ(1) φ(2) φ(3) ....... φ(15)*φ(16) = 3397386240 i.e the last three digits are 240.

hence answer is 240

I start by working out the dterminant of A when A is a much smaller matrix and starting growing it and see if you can see a pattern in the values of a determinant. A1=[1] det[A1]=1 A2=[11][12] det[A2]=2-1=1

and so on . I tried this method on a spreadsheet program but I did not see a useful pattern .so write out the matrix and solve its determinant, using the non-recursive method. IT will be solved over a quite long period of time. then the determinant is 3397386240 hence the last three digits are 240.

Find all the elements of the matrix and bash.

This can be written as a subcase of Smith determinants. In particular, given a 2-dimensional matrix A with entries a_i,j=gcd(i,j) with 1<=i, j<=n, the determinant of A is equal to phi(1) phi(2) ...*phi(n), where phi(n) is Euler's totient function.

Therefore, our answer is simply the last 3 digits of phi(1) phi(2) ...*phi(16), which we can routinely calculate to be 240.

The determinant here is called a Smith Determinant, and be calculated using the formula \det \left( A \right) =\prod _{i=1}^{n}\phi \left( i \right), where A is an n x n GCD matrix, and \phi \left( n \right) is the Euler's totient function. In our case A is a 16 x 16 matrix, so we have

\det \left( A \right) = \prod _{i=1}^{16}{\it \phi} \left( i \right) = (1)(1)(2)(2)(4)(2)(6)(4)(6)(4)(10)(4)(12)(6)(8)(8) = 3397386240.

The last three digits are 240, which is our answer.

Let $\phi (n)$ be the number of positive integers not greater than $n$ and co-prime with $n$ . We have $\phi (n) = n (1-\frac{1}{p_1} )(1-\frac{1}{p_2}) ...(1-\frac{1}{p_k})$ with $p_1, p_2, ..., p_k$ are some primer divisors of $n$ . Using some transformations for row and column of the given matrix, we have $\det A = \prod_{i=1}^{16} \phi(i)$ . It is easy to find out that the last 3 digits of $det(A)$ is 240.

When wanting to calculate the gcd of such a matrix, there is a very useful theorem that will do just that. It states that $\det(A_n) = \prod_{k=1}^n \phi(n)$ . In this case, $n=16$ , therefore $\det(A_{16} = \phi(1) \cdot \phi(2) \cdot \ldots \cdot \phi(16) = 2 \cdot 2 \cdot 4 \cdot 2 \cdot 6 \cdot 4 \cdot 10 \cdot 4 \cdot 12 \cdot 6 \cdot 8 \cdot 8$ . We can easily see that the last digit of this is 0 since it is a multiple of 10. Dividing by 10 and taking the rest mod 100, we get the other two digits, namely 24. This gives us $\boxed{240}$