(Reposted from [math.SE](https://math.stackexchange.com/questions/4655805/))

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](https://en.wikipedia.org/wiki/Hadamard%27s_maximal_determinant_problem#Equivalence_and_normalization_of_{1,_%E2%88%921}_matrices) $\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
$$

My original interest was showing that the first standard basis vector $e_1$ is always in the column space of $A_n$ (which I think I can show). However, computing $\operatorname{rank}(A_n)$ for small $n$ quickly suggests an intriguing 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$ (and apparently holds up to $n = 1024$ even, which is more than enough evidence to convince me personally of its validity). To save some trouble, the proposed formula is [A361003](https://oeis.org/A361003) in OEIS. A combinatorial proof e.g. via [A361001](https://oeis.org/A361001) would be fine. If anyone knows more about this family of matrices I would be happy to read more.