Characteristic polynomial of a matrix related to pairs of elements generating $\mathbb{Z}/n\mathbb{Z}$ 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.
 A: 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.
