Encoding primes via ranks of sign matrices

Question

(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})_{0 \le i, j \le n-1}$, where

$$\displaystyle a_{ij} := (-1)^{\big\lfloor 2ij/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}, \qquad A_3 = \begin{bmatrix} 1&1&1\\ 1&1&-1\\ 1&-1&1 \end{bmatrix}, \qquad 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_0$ 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.

Answer 1

A modest start, but before doing so, one suggestion: I would index the columns and rows from $0$ to $n-1$, so $a_{ij} = (-1)^{\lfloor 2ij/n\rfloor}$.

We prove that the conjectured value of $\operatorname{rank}(A_n)$ is an upper bound. For $1\le k\le n-1$ let $v_k$ be the row vector with $1$ in positions $k$ and $n-k$ and $0$ elsewhere, and for $0\le j\le n-1$ let $a_j$ be the $j$'th column of $A_n$.

As $\lfloor 2kj/n\rfloor$ and $\lfloor 2(n-k)j/n\rfloor$ have different parity if and only if $n$ does not divide $2kj$, we obtain \begin{equation} v_ka_j= \begin{cases} 0 & \text{if }n\nmid 2kj\\ 2\cdot(-1)^{2kj/n} & \text{if }n\mid 2kj. \end{cases} \end{equation} Set $d=\operatorname{gcd}(n, k)$ and assume that $k$ does not divide $n$, hence $d<k$. We claim that $w_k=v_k-v_d$ is a left eigenvector of $A_n$. We consider two cases:

• If $n$ does not divide $2kj$, then $n$ does not divide $2dj$ either. So $w_ka_j=v_ka_j-v_da_j=0-0=0$.
• Now suppose that $n$ divides $2kj$. Then $n/d$ divides $2jk/d$, and since $n/d$ and $k/d$ are relatively prime, we get that $n/d$ divides $2j$, so $n\mid 2dj$. So $w_ka_j=0$ once we know that $2kj/n$ and $2dj/n$ have the same parity. As $d\mid k$, this could only fail if $k/d$ were even while $2dj/n$ were odd. This would imply $2d\mid k$ and $2d\mid n$, respectively, contrary to the choice of $d$.

Thus $w_k$ is an eigenvector of $A_n$ for $1\le k<n/2$ if $k\nmid n$, and these vectors are linearly independent.

Answer 2

Just a long comment: I tried to look at the diagonal of the Smith Normal form of the matrices. I counted the number of occurrences of each number. For example, the row $\{8,3\} \to 1^1\, 2^4\, 4^1\, 8^1 $ encodes $n$, $\lfloor \frac{n-1}{2} \rfloor$ and then the non-zero entries on the diagonal. In this case, 1 entry is 1, 4 entries are equal to 2, and then there is a single 4, and a single 8.

\begin{array}{l} \{1,0\}\to 1^1 \\ \{2,0\}\to 1^1\, 2^1 \\ \{3,1\}\to 1^1\, 2^2 \\ \{4,1\}\to 1^1\, 2^2\, 4^1 \\ \{5,2\}\to 1^1\, 2^3 \\ \{6,2\}\to 1^1\, 2^3\, 4^2 \\ \{7,3\}\to 1^1\, 2^4 \\ \{8,3\}\to 1^1\, 2^4\, 4^1\, 8^1 \\ \{9,4\}\to 1^1\, 2^5\, 6^1 \\ \{10,4\}\to 1^1\, 2^4\, 4^3 \\ \{11,5\}\to 1^1\, 2^5\, 6^1 \\ \{12,5\}\to 1^1\, 2^6\, 4^1\, 8^3 \\ \{13,6\}\to 1^1\, 2^6\, 10^1 \\ \{14,6\}\to 1^1\, 2^5\, 4^4 \\ \{15,7\}\to 1^1\, 2^9\, 60^1 \\ \{16,7\}\to 1^1\, 2^7\, 4^1\, 8^2\, 16^1 \\ \{17,8\}\to 1^1\, 2^8\, 34^1 \\ \{18,8\}\to 1^1\, 2^7\, 4^4\, 12^2 \\ \{19,9\}\to 1^1\, 2^9\, 54^1 \\ \{20,9\}\to 1^1\, 2^8\, 4^1\, 8^5 \\ \{21,10\}\to 1^1\, 2^{12}\, 504^1 \\ \{22,10\}\to 1^1\, 2^7\, 4^4\, 12^2 \\ \{23,11\}\to 1^1\, 2^{11}\, 534^1 \\ \{24,11\}\to 1^1\, 2^{10}\, 4^3\, 8^1\, 16^4 \\ \{25,12\}\to 1^1\, 2^{12}\, 10^1\, 410^1 \\ \{26,12\}\to 1^1\, 2^8\, 4^5\, 20^2 \\ \{27,13\}\to 1^1\, 2^{13}\, 6^1\, 18^1\, 342^1 \\ \{28,13\}\to 1^1\, 2^{10}\, 4^1\, 8^6\, 16^1 \\ \{29,14\}\to 1^1\, 2^{12}\, 4^2\, 2260^1 \\ \{30,14\}\to 1^1\, 2^{10}\, 4^9\, 60^1\, 120^1 \\ \{31,15\}\to 1^1\, 2^{14}\, 62^1\, 558^1 \\ \{32,15\}\to 1^1\, 2^{11}\, 4^3\, 8^2\, 16^3\, 32^1 \\ \{33,16\}\to 1^1\, 2^{16}\, 6^1\, 66^1\, 2904^1 \\ \{34,16\}\to 1^1\, 2^{10}\, 4^7\, 68^2 \\ \{35,17\}\to 1^1\, 2^{18}\, 18^1\, 81900^1 \\ \{36,17\}\to 1^1\, 2^{14}\, 4^1\, 8^6\, 24^4 \\ \{37,18\}\to 1^1\, 2^{18}\, 524290^1 \\ \{38,18\}\to 1^1\, 2^{11}\, 4^8\, 108^2 \\ \{39,19\}\to 1^1\, 2^{20}\, 520^1\, 32760^1 \\ \{40,19\}\to 1^1\, 2^{13}\, 4^5\, 8^1\, 16^6\, 48^1 \\ \end{array}

The Mathematica code:

aa[n_] := 
 aa[n] = Table[(-1)^Floor[2 i j/n], {i, 0, n - 1}, {j, 0, 
    n - 1}]; {#, Floor[(# - 1)/2]} -> 
    Row[(Superscript[#1, #2] & @@@ 
       Tally[DeleteCases[Diagonal[SmithDecomposition[aa[#]][[2]]], 
         0]]), " "] & /@ Range[40] // Column