Crossposted at MathOverflow

Recently I came across a very simply defined family of matrices: for $n \in \mathbb{N}$, set $A_n := (a_{ij})_{1 \le i, j \le n}$, where

$$\displaystyle a_{ij} := (-1)^{\big\lfloor \dfrac{2(i-1)(j-1)}{n} \big\rfloor}$$

These are normalized $\pm 1$ symmetric $n \times n$ matrices. The first few are:

$$ A_2 = \begin{bmatrix} 1&1\\ 1&-1 \end{bmatrix}, A_3 = \begin{bmatrix} 1&1&1\\ 1&1&-1\\ 1&-1&1 \end{bmatrix}, A_4 = \begin{bmatrix} 1&1&1&1\\ 1&1&-1&-1\\ 1&-1&1&-1\\ 1&-1&-1&1 \end{bmatrix}, \ldots $$

Computing $\operatorname{rank}(A_n)$ for small $n$ quickly suggests a pattern:

$$\operatorname{rank}(A_n) = \sigma_0(n) + \Big\lfloor \frac{n-1}{2} \Big\rfloor$$

where $\sigma_0(n)$ is the number (= sum of $0^\text{th}$ powers) of divisors of $n$. My question is:

Is this formula for $\operatorname{rank}(A_n)$ true for all $n$?

If so, then since the minimal value of $\sigma_0$ is $2$, which occurs exactly for prime $n$, one would have $\operatorname{rank}(A_n) = \big\lfloor \frac{n+3}{2} \big\rfloor$ is minimal $\iff n$ is prime. (This would, in my opinion, be an interesting encoding of the primes in a purely linear-algebraic fashion.)

I have tested this up to $n = 30$. To save some trouble, this is A361003 in OEIS (coincidentally just added last week!). A combinatorial proof e.g. via A361001 would be fine. If anyone knows more about this family of matrices I would be happy to read more.

  • 1
    $\begingroup$ My computer has checked that it's true up to $n=1024$. (And even so I don't exactly believe it :) .) $\endgroup$
    – JBL
    Mar 11, 2023 at 0:08
  • $\begingroup$ @JBL Your standards for numerical evidence are perhaps higher than mine :) $\endgroup$
    – math54321
    Mar 11, 2023 at 4:46


You must log in to answer this question.