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.

Let $A=[a_{ij}]_{n×n}$ be the matrix defined by letting $a_{ij}$ be the rational number such that $$a_{ij}=\gcd(i,j ).$$ How prove that $A$ is invertible, and compute $\det(A)$? thanks in advance

share|improve this question

2 Answers 2

up vote 10 down vote accepted

There is a general trick that applies to this case.

Assume a matrix $A=(a_{i,j})$ is such that there exists a function $\psi$ such that $$ a_{i,j}=\sum_{k|i,k|j}\psi(k) $$ for all $i,j$.

Then $$ \det A=\psi(1)\psi(2)\cdots\psi(n). $$ To see this, consider the matrix $B=(b_{i,j})$ such that $b_{i,j}=1$ if $i|j$ and $b_{i,j}=0$ otherwise. Note that $B$ is upper-triangular with ones on the diagonal, so its determinant is $1$.

Now let $C$ be the diagonal matrix whose diagonal is $(\psi(1),\ldots,\psi(n))$.

A matrix product computation shows that $$ A=B^tCB\quad\mbox{hence}\quad \det A=(\det B)^2\det C=\psi(1)\cdots\psi(n). $$

Now going back to your question. Consider Euler's totient function $\phi$. It is well-known that $$ m=\sum_{k|m}\phi(k) $$ so $$ a_{i,j}=gcd(i,j)=\sum_{k|gcd(i,j)}\phi(k)=\sum_{k|i,k|j}\phi(k). $$

Applying the general result above, we find: $$ \det A=\phi(1)\phi(2)\cdots\phi(n). $$

share|improve this answer
    
hi your approach is so nice thanks –  Maisam Hedyelloo Feb 10 '13 at 20:45
    
@MaisamHedyelloo Thanks. I've always liked this exercise. –  1015 Feb 10 '13 at 20:56

This is a nice result. We have $$ \det(A)= \phi(1)\phi(2)\dots\phi(n), $$ where $\phi$ is Euler's phi function, $\phi(n)$ being the number of positive integers $i\le n$ that are relatively prime with $n$. It satisfies $$ \sum_{j\mid n}\phi(j)=n, $$ which we use below.

Let's write $a_n$ for the determinant of the $n\times n$ version of $A$. The sequence $a_1,a_2,a_3,\dots$ begins $$ 1, 1, 2, 4, 16, 32, 192, \dots $$ which OEIS catalogs as $A001088$.

A cute short proof that only uses basic linear algebra (LDU decomposition) appears in a recent note,

Warren P. Johnson. An $LDU$ Factorization in Elementary Number Theory, Math. Mag. 76 (5), (2003), 392–394. MR1573717.

What one shows is that $$ A=L\Phi L^T $$ where $L$ is the $n\times n$ matrix whose $i,j$ entry is $1$ if $j$ divides $i$, and is $0$ otherwise, and $\Phi$ is the diagonal matrix whose $i,i$ entry is $\phi(n)$. Note that $L$ is lower diagonal, with $1$s as entries along its main diagonal, so $\det(L)=\det(L^T)=1$, and the result follows once we prove that $A=L\Phi L^T$, as claimed. Johnson calls this Le Paige's result, who established it to compute $\det(A)$ (originally found by H. J. S. Smith around 1875, according to the references at the OEIS site).

To prove Le Paige's result, simply expand $L\Phi L^T$, and note that its $i,j$ entry is $$ \sum_{k=1}^n L_{ik}\Phi_{kk}(L^T)_{kj}=\sum_{k=1}^n L_{ik}\phi(k) L_{jk}=\sum_{k\mid i,k\mid j}\phi(k) =\sum_{k|{\rm gcd}(i,j)} \phi(k)={\rm gcd}(i,j)=A_{ij}, $$ where I use $B_{ij}$ to denote the $i,j$ entry of the matrix $B$.

share|improve this answer
    
I see this argument is the same as julien's. It is a cute example, I will have to use it in my linear algebra class. –  Andres Caicedo Feb 10 '13 at 20:38

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.