(Reposted from math.SE)

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 $$

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 in OEIS. 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.