# Encoding primes via ranks of sign matrices

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.

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