21
$\begingroup$

Let $A_n$ be the $n \times n$-matrix with entries $\gcd(i,j)$ and $f_n$ the characteristic polynomial of $A_n$.

Question: Is $f_n$ irreducible over $\mathbb{Q}$ for all $n$ except $n=8$?

This is true for $n \leq 60$.

$\endgroup$
8
  • $\begingroup$ Any references for this problem? $\endgroup$
    – lhf
    Jun 30, 2020 at 0:07
  • 2
    $\begingroup$ True for $n \le 180$. $\endgroup$ Jun 30, 2020 at 1:29
  • $\begingroup$ @lhf I do not know whether this problem is stated somewhere else. I came up with it by experimenting with GAP. $\endgroup$
    – Mare
    Jun 30, 2020 at 5:38
  • $\begingroup$ Any significance that can be attached to the $n=8$ case? If I'm not wrong $f_8(x)=(x^2-8x+8)(x^6-28x^5+248x^4-900x^3+1324x^2-704x+96)$ $\endgroup$ Jan 21, 2021 at 11:21
  • 1
    $\begingroup$ This question assumes that numbering of rows and columns ($i$ and $j$) goes from $1$ to $n$. If it ranges from $0$ to $n-1$ as seems more logical to me (with gcd of $0$ and $j$ being $j$ for all $j$ of course), then the characteristic polynomial appears to be always irreducible. $\endgroup$
    – Gro-Tsen
    Jan 11, 2023 at 10:27

1 Answer 1

12
+25
$\begingroup$

Edit. See the calculation modulo $2$ below.

This is not an answer, but it is too long for a comment. The matrix $A_n$ can be decomposed as $A_n=D_n^T\Phi_nD_n$ where the entries of $D_n$ (D for divisors, not for diagonal) are either $1$ if $i|j$, or $0$ otherwise, and $\Phi_n={\rm diag}(\phi(1),\ldots,\phi(n))$, $\phi$ being the Euler's totient function.

Notice that the matrix $D_n$ is the $n\times n$ upper-left block of an infinite upper triangular matrix $D$. Its diagonal is made of $1$s, so that $\det D_n=1$. Thus $$f_n(X)=\det(XD_n^{-T}D_n^{-1}-\Phi_n).$$ The matrix $D_n^{-T}D_n^{-1}$ is the $n\times n$ upper-left block of $D^{-T}D^{-1}$. The entries of $D^{-1}$ are known to be either $\mu(j/i)$ if $i|j$, or $0$ otherwise. Therefore $$(D_n^{-T}D_n^{-1})_{ij}=\sum_{k|i,j}\mu\left(\frac ik\right)\mu\left(\frac jk\right).$$ For instance this is zero when $p^2|j$ but $p$ does not divide $i$. Also the diagonal entry corresponding to $j=i$ equals $2^r$, where $r$ is the number of distinct prime factors of $i$. A closed formula is that the $(i,j)$-entry equals $$\mu\left(\frac{{\rm lcm}(i,j)}{{\rm gcd}(i,j)}\right)2^{P(i,j)},$$ where $P(i,j)$ is the number of distinct prime factors of ${\rm gcd}(i,j)$ for which the valuations agree: $$v_p(i)=v_p(j)\ge1.$$

Calculation modulo 2. Since $\phi(j)$ is even for every $j\ge3$, the matrix $\Phi_n$ reduces to ${\rm diag}(1,1,0,\ldots,0)$. Thus $f_n(X)=X^n-aX^{n-1}+bX^{n-2}$ where $$a=(D_n^{-T}D_n^{-1})\binom{\hat1}{\hat1}+(D_n^{-T}D_n^{-1})\binom{\hat2}{\hat2}$$ is the sum of minors obtained by deleting either the first row and column, or the second, and $$b=(D_n^{-T}D_n^{-1})\binom{\widehat{12}}{\widehat{12}}$$ is the minor when deleting the two first columns and rows. Because $\det(D_n^{-T}D_n^{-1})=1$, this gives $$a=(D_nD_n^T)_{11}+(D_nD_n^T)_{22},\qquad b=(D_nD_n^T)\binom{12}{12},$$ the latter being a $2\times2$ minor. These quantities involve only the two first rows $(1,\ldots,1)$ and $(0101\ldots)$ of $D_n$. We obtain $$a=n^2+\lfloor\frac n2\rfloor^2=n+\lfloor\frac n2\rfloor,\qquad b=n\lfloor\frac n2\rfloor-\lfloor\frac n2\rfloor^2=(n+1)\lfloor\frac n2\rfloor.$$ Hence (mod $2$) $$f_n(X)=\left\{\begin{array}{lcr} X^n, & & n=0,3, \\ X^{n-1}(X+1), & & n=1 \\ X^{n-2}(X^2+X+1), & & n=2. \end{array}\right.$$

$\endgroup$
2
  • $\begingroup$ Quite neat decomposition of $A$. Is it used for well known number theoretic results? If so and you easily happen have a reference for that, please post it. $\endgroup$ Jan 21, 2021 at 18:39
  • 3
    $\begingroup$ @YaakovBaruch. The decomposition $A_n=D_n^T\Phi_nD_n$ is well known ans easy to verify. I made an exercise (#188) from it in my blog perso.ens-lyon.fr/serre/DPF/exobis.pdf (companion to my book on Matrices). $\endgroup$ Jan 21, 2021 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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