similar matrices over $\mathbb{Z}$ Let $A,B$ be $2\times 2$ matrices over $\mathbb{Z}$. Suppose $x^2+x+1$ is the characteristic polynomial for both $A,B$. Determine whether $A,B$ are similar to each other over $\mathbb{Z}$. How to solve?

The answer is that such matrices are always similar over $\def\Z{\Bbb Z}\Z$ (conjugate in $GL_2(\Bbb Z)$). The question is deeper however than it might look at first, and as far as I can see any solution requires some somewhat subtle arithmetic considerations. A few things are easy: $A,B$ always have determinant$~1$ (from the constant coefficients of the characteristic polynomial), minimal polynomial (over$\def\Q{\Bbb Q}~\Q$) equal to the characteristic polynomial (as it is square-free) and order$~3$ (because the minimal polynomial divides $x^3-1$); the matrices also have trace$~{-}1$, but I'm not sure that is very useful information in itself. With minimal and  characteristic polynomials both equal to $x^2+x+1$, the two matrices and are similar over$~\Q$ to the companion matrix of $x^2+x+1$, and therefore to each other. The main difficulty is proving similarity over$~\Z$, which is a more restrictive condition.
Obvious examples of such matrices are the companion matrix of $x^2+x+1$ and its transpose:
$$
  \begin{pmatrix}0&-1\\1&-1\end{pmatrix}
  \qquad\text{and}\qquad
  \begin{pmatrix}0&1\\-1&-1\end{pmatrix}.
$$
These matrices are conjugate by the diagonal matrix with diagonal entries $1,-1$, but they are not conjugate inside $SL_2(\Z)$ (so one had better not try to prove that stronger statement). Since there are no eigenvectors over$~\Q$, any nonzero vector$~v$ together with $A\cdot v$ forms a $\Q$-basis, with respect to which the matrix gives the above companion matrix. The difficulty is to show the existence of a vector $v\in\Z^2$ such that $(v,A\cdot v)$ is a $\Z$-basis for $\Z^2$.
Two approaches using some structure theory are possible. One, which I took from this answer to a rather similar question, uses the known structure of $SL(2,\Z)$ as amalgamated product $SL_2(\Z)\cong\Z/4*_{\Z/2}\Z/6$, and the fact that in such a product the only elements of finite order are those which are conjugate to the elements of amalgamated groups. Thus every element of order $3$ in $SL_2(\Z)$ is conjugate in this group to one of the two elements of order $3$ in the factor $\Z/6$, and therefore to one of matrices above (each of which is easily seen to be conjugate in $SL_2(\Z)$ to the square of the other). This implies that $A$ and $B$ are conjugate in $GL(2,\Z)$, and hence similar over$~\Z$.
Another approach, which I took from this answer, is to use the structure theory for modules over a PID. Each matrix of the required kind makes $\Z^2$ into a $\Z[X]$ module in which $X^2+X+1$ acts as$~0$, and hence into a $\Z[X]/(X^2+X+1)$-module. Now $R=\Z[X]/(X^2+X+1)$ is known to be a Euclidean domain (that of the Eisenstein integers) and hence a PID. Since any nonzero ideal of $R$ intersects $\Z$ nontrivially, our module cannot have any factors $R/I$ with $I\neq(0)$. So we are looking at a module isomorphic to $R^n$, and from the rank$~2$ over$~\Z$ it is obvious that $n=1$. But taking $v$ to be a generator of the module over$~R$, the vectors $v,A\cdot v$ form a basis of the module considered over$~\Z$, as desired.
I prefer the second argument. The same reasoning gives the following more general statement:

If an $n\times n$ matrix$~A$ over$~\Z$ has minimal polynomial $P=X^2+X+1$, then $n$ is even and $A$ is similar over$~\Z$ to the block diagonal matrix with $n/2$ blocks equal to the companion matrix of$~P$.

The same is true for $P=X^2-X+1$ and for $P=X^2+1$. It fails (even when $n=2$) for $P=X^2-1$ (think $(\begin{smallmatrix}1&0\\0&-1\end{smallmatrix})$). Also one cannot of course in any case (with $n>2$ even) weaken the hypothesis to the condition that the characteristic polynomial is $P^{n/2}$, as most matrices with that characteristic polynomial are not diagonalisable (over the splitting field of$~P$).
