Encoding primes via ranks of sign matrices

(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.

• Curious! My intuition would have suggested that $A_n$ should have the smaller (not greater) rank the more divisors $n$ has, and yet it is apparently the other way round. Mar 22, 2023 at 19:55
• @darijgrinberg Maybe you were secretly thinking about $\dim \ker$ instead of rank :) Somewhat related, I don't know if there's a good way of viewing $A_n, A_m$ as blocks inside $A_{nm}$ Mar 22, 2023 at 20:25
• No -- I was thinking that divisors of $n$ would lead to equal rows in $A$. Mar 22, 2023 at 21:06
• Small remark : since it has been checked up to 1024, it is in particular true for the first Carmichael number (aka pseudo prime) 561, which adds some weight to the conjecture. Mar 29, 2023 at 10:11
• Side question : if primality is encoded by the number of non-zero eigenvalues, one can wonder what other properties are encoded in the rest of the spectrum. Apr 1, 2023 at 4:15

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 $$$$v_ka_j= \begin{cases} 0 & \text{if }n\nmid 2kj\\ 2\cdot(-1)^{2kj/n} & \text{if }n\mid 2kj. \end{cases}$$$$ Set $$d=\operatorname{gcd}(n, k)$$ and assume that $$k$$ does not divide $$n$$, hence $$d. 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 if $$k\nmid n$$, and these vectors are linearly independent.

• In fact I did use 0-based indexing in my own calculations (now edited). This is a nice construction of the correct number of linearly independent vectors in $\ker(A_n)$, so it remains to show that they span the kernel - any ideas? Mar 23, 2023 at 18:11
• @math54321 Not really. I guess one again has to write out a sufficiently large set of linearly independent vectors of the row space. The vectors $e_k-e_{n-k}$, $1\le k<n/2$, seem to be in this space. Probably the additional vectors coming from the divisors of $n$ have a similarly simple shape. But at a first glance I did not see a pattern even in how to linearly combine $e_k-e_{n-k}$ them from the rows of $A$. Even if $n$ is prime it might be difficult. Mar 23, 2023 at 19:47
• I tried playing with prime $n$, and it seems like your suggestion of $e_k - e_{n-k}$, $1 \le k < n/2$ being in the row (= column) space checks out - although the coefficients I found for the linear combinations (wrt rows of $A_n$) are not easy to predict, they do seem to be only supported in the latter half of rows (with a single exception for $k = 1$). Also I believe the additional 2 vectors needed in this case can be chosen to be $e_0$ and $\sum_{k=1}^{\lfloor n/2 \rfloor} e_k$ (both of which only involve 2 rows of $A_n$) Mar 23, 2023 at 21:32

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

• Thanks for the data! Any guesses as to the product of the nonzero invariant factors? Mar 27, 2023 at 18:00
• Powers of 2 seems to give particularly nice Smith normal forms, perhaps start with a conjecture there. Mar 28, 2023 at 5:24