4
$\begingroup$

Let A be a $(n-1) \times (n-1)$ matrix whose entries $a_{ij}=d(\gcd(i+1,j+1))$. $d(n)$is the number of divisors of $n$. It seems that the determinant of it is the number of square-frees less than or equal to $n$. How to prove it?

For $a_{ij}=d(\gcd(i,j))$, the determinant is 1,because it is the product $CC^T$,where $c_{ij}=${if j|i then 1 else 0} But this method seems not to work on the $\gcd(i+1,j+1)$ case.

$\endgroup$
  • 2
    $\begingroup$ This would be a very nice property! $\endgroup$ – Peter Jan 13 '15 at 13:56
  • 2
    $\begingroup$ How do you define $gcd(0,0)$ ? $\endgroup$ – Peter Jan 13 '15 at 14:01
  • 1
    $\begingroup$ math.stackexchange.com/questions/495119/what-is-gcd0-0 $\endgroup$ – Eleven-Eleven Jan 13 '15 at 14:05
  • 1
    $\begingroup$ I currently check with PARI/GP, if there are counterexamples. For $n\le 430$, there are none. $\endgroup$ – Peter Jan 13 '15 at 14:11
  • 1
    $\begingroup$ No counterexamples for $n\le 600$. Wow, what a discovery! How did you observe this ? $\endgroup$ – Peter Jan 13 '15 at 14:25
3
$\begingroup$

Let $X$ be the $n \times n$-matrix obtained as follows: in the first row, the $i$-th entry equals $\mu(i)$ where $\mu$ denotes the Möbius function, and in the $j$-th row ($j>1$), the $i$-th entry is $1$ if $i$ divides $j$ and $0$ otherwise.

For example, for $n=8$ we obtain $$ X=\left( \begin{array}{cccccccc} 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \right). $$

Now $XX^t$ contains the matrix of interest $A$ as a submatrix: $$ XX^t = Y = \left( \begin{array}{cccccccc} 6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 2 & 1 & 2 & 1 & 2 \\ 0 & 1 & 2 & 1 & 1 & 2 & 1 & 1 \\ 0 & 2 & 1 & 3 & 1 & 2 & 1 & 3 \\ 0 & 1 & 1 & 1 & 2 & 1 & 1 & 1 \\ 0 & 2 & 2 & 2 & 1 & 4 & 1 & 2 \\ 0 & 1 & 1 & 1 & 1 & 1 & 2 & 1 \\ 0 & 2 & 1 & 3 & 1 & 2 & 1 & 4 \\ \end{array} \right). $$ Let $k$ be the number of squarefree integers in $\{1,2,\ldots,n\}$. Then we claim that for general $n$ we have $\det X = k$ and that $XX^t$ is the block matrix $$ Y = \left( \begin{array}{cc} k & 0 \\ 0 & A \end{array} \right). $$ This would imply that $k \det(A) = \det(Y) = \det (XX^t) = \det(X)^2 = k^2$ or $\det(A)=k$, as desired.

Let us first show that $XX^t = Y$. We check the equality of the element in row $i$ and column $j$. For $i,j > 1$ this follows as in the $\gcd(i,j)$-case. For $i=j=1$ this follows from $k = \sum_{i=1}^n \mu(i)^2$. For the other cases this follows from the formula $$ \sum_{d \mid n} \mu(d) = 0 \qquad \mbox{for } n > 2. $$

It remains to show that $\det X = k$. For each $2 \leq i \leq n$, we add the $i$-th column $\mu(i)$ times to the first row. Then the determinant does not change and the first column will contain a $k$ in the first row and $0$ in other rows by the formula $\sum_{d \mid n} \mu(d) = 0$. In our $n=8$ example we find the following: $$ \left( \begin{array}{cccccccc} 6 & -1 & -1 & 0 & -1 & 1 & -1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ \end{array} \right). $$ It is now clear that (in general) the determinant equals $k$ by noting that the term corresponding to the diagonal is the only nonzero term.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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