Characteristic polynomial of a matrix related to pairs of elements generating $\mathbb{Z}/n\mathbb{Z}$

Question

Fix $n\geq 2$. Let $A$ be the matrix whose rows and columns are indexed by pairs $(a,b)\in \mathbb{Z}/n\mathbb{Z}$ such that $a,b$ generate $\mathbb{Z}/n\mathbb{Z}$ (the number of such pairs is $\phi(n)\psi(n)$, where $\phi(n)$ is the Euler phi-function and $\psi(n)$ is the Dedekind $\psi$-function), with the $((a,b),(c,d))$ entry defined by $$ A_{(a,b),(c,d)}=\left\{ \begin{array}{rl} 1, & \mathrm{if}\ c=a\ \mathrm{and}\ d=b-a\\ 1, & \mathrm{if}\ c=a-b\ \mathrm{and}\ d=b\\ 0, & \mathrm{otherwise}. \end{array} \right. $$ The characteristic polynomial of $A$ factors quite a bit. What is the explanation for this behavior? Is $A$ diagonalizable (over $\mathbb{C}$)? What is the rank of $A$? This matrix arises in the congruence properties mod $n$ of the entries of Stern's triangle.

Here are these polynomials for $n\leq 11$. I write $[k]$ for an irreducible polynomial (over $\mathbb{Q}$) of degree $k$. $$ n=2:\ \ (x+1)(x-1)(x-2) $$ $$ n=3:\ \ x^2(x-1)^3(x-2)(x^2+x+2) $$ $$ n=4:\ \ x^2(x+1)^3(x-1)^4(x-2)(x^2-x+2) $$ $$ n=5:\ \ x^4(x+1)^2(x-1)^7(x-2)(x^2+1)^2(x^2-x+2)(x^4-x^2+4) $$ $$ n=6:\ \ x^6(x+1)^4(x-1)^7(x-2)(x^2+2x+2)(x^2-2x+2)(x^2+x+2) $$ $$ n=7:\ \ x^{10}(x+1)^4(x-1)^{11}(x-2)(x^2+2)(x^4+3)^2[4]^2[4] $$ $$ n=8:\ \ x^8(x+1)^8(x-1)^{13}(x-2)(x^2+1)^2(x^2-x+2)(x^4-x^2+4)[4][4] $$ $$ n=9:\ \ x^{14}(x+1)^6(x-1)^{17}(x-2)(x^2-2x+2)^2(x^2+x+2)^3[6]^2[6]^2 $$ $$ n=10:\ \ x^{12}(x+1)^{10}(x-1)^{15}(x-2)(x^2-x+2)(x^2+1)^2 [4]^2[4][4][4][4] $$ $$ n=11:\ \ x^{20}(x+1)^{10}(x-1)^{21}(x-2)(x^2+2x+2)(x^2-2x+2) (x^2+x+2)[3]^2[4]^2[4]^2[8]^2[12]^2. $$ The factor $x-2$ is clear since the all 1's vector is an eigenvector with eigenvalue 2.

Answer 1

The corank is $\phi(n)\psi(n)/6$ for all $n>3$. In particular, your computations imply that the matrix is not diagonalizable for $n=6,7,9$.

This follows from the fact that all nonzero entries are accumulated in the $6\times 6$ blocks with rows indexed by $$ (a,b),\; (a-b,a),\; (-b,a-b),\; (-a,-b),\; (b-a,a), \; (b,b-a) $$ and columns indexed by $$ (a-b,b),\; (-b,a),\; (-a,a-b),\; (b-a,-b),\; (b,-a),\; (-a,b-a) $$ (and all indices are paritioned into such 6-tuples!). Each such block has the form $$ \begin{pmatrix} 1& 1&\\ & 1& 1\\ & & 1& 1\\ & & & 1& 1\\ & & & & 1& 1\\ 1& & & & & 1\\ \end{pmatrix}, $$ hence it is of corank 1.

This can be seen from the following observation. Move along your matrix, passing alternately from a one to another one in the same row, and to another one in the same column. A pair of moves performs the row change $(a,b)\mapsto (a-b,a)$, and a column change $(c,d)\mapsto (-d,c+d)$. Both these maps have order $6$, and (for $n>3$) they have no orbit of smaller length.

For $n=2$ and $n=3$, there appear smaller cycles.