Similarity of matrices over $\Bbb{Z}$ Let $A$ be a $2 \times 2$ matrix over $\Bbb{Z}$ with characteristic polynomial $x^2 + 1$. Determine whether $A$ is similar to 
$$\pmatrix{0 & -1 \\ 1 & 0}$$
over $\Bbb{Z}$.
I'm so used to working with matrices over fields $\Bbb{Q}$ and $\Bbb{C}$ that I'm not sure how it differs when we switch to non-fields like $\Bbb{Z}$. Any advice would be much appreciated.
 A: Notice that any such $A$ is an element of order $4$ in $SL_2({\bf Z})$. But $SL_2({\bf Z})\cong {\bf Z}_4*_{{\bf Z}_2}{\bf Z}_6$.
In an amalgamated product, the only elements of finite order are those which are conjugate to the elements of amalgamated groups, so every such $A$ is conjugate to the $1\in {\bf Z}_4$ or $3\in{\bf Z}_4$ in $SL_2({\bf Z})$.
$1$ corresponds to the matrix you provided (with the usual identification of $SL_2({\bf Z})$ with the amalgamated product), while $3$ is its inverse. They are not conjugate in $SL_2({\bf Z})$, but they are in $GL_2({\bf Z})$ by $\begin{pmatrix}0&1\\1&0\end{pmatrix}$. Since any $A$ is conjugate to one of them, all the $A$ are similar.
A: Update: the proof below shows a necessary but not sufficient similarity over $\Bbb{Z}$. I will leave here for pedantic reasons. In the following paragraph, I will summarize; please consult references linked.
Similarity over $\Bbb{Z}$ implies similarity over $\Bbb{Q}$ but the converse is not true in general. The particular case  for $2\times 2$  integral matrices having a characteristic polynomial $f(x) = x^2+1$ is covered by Example $1$ pp. $11$ in these (PDF) notes: Lectures on Integer Matrices Thomas J. Laﬀey. The proof follows from a theorem of Latimer and MacDuffee relating similarity classes to the number of ideal classes of $\Bbb{Z}[\theta]$ where $\theta$ is a complex root of the characteristic polynomial. And in the case of $x^2+1$, $\Bbb{Z}[i]$ is a PID and has class number 1 (see the PDF). Also relevant is  this post in MathOverflow: Ideal classes and integral similarity.

Two matrices $A, B$ are similar over $\Bbb{Z}$ if $x I - A$ and $x I - B$ have the same Smith normal form over $\Bbb{Q}[x]$.
Recall that the $i$th invariant factor is the ratio between the gcd of all $i\times i$ minors, to the gcd of all $i-1 \times i-1$ minors. So, the SNF of $xI - B = \pmatrix{x & 1 \\ -1 & x}$ is $\pmatrix{1 & 0 \\ 0 & x^2+1}.$
It's not hard to show that if $A$ has a characteristic polynomial $\lambda^2+1$ then $xA - I$ has a characteristic polynomial $\lambda^2 + (-2x) \lambda + (x^2 + 1).$ Hence, the determinant of $xA - I$ is $x^2 + 1$, which is also the $2$nd determinantal divisor. But $x^2 + 1$ does not factor over $\Bbb{Q}$, and that pretty much forces the $2$nd invariant factor of $xA - I$ to be $x^2 + 1$, and the first invariant factor to be $1$ (since $1$ is the only element in $\Bbb{Q}[x]$ which divides $x^2 +1 $). So the SNF of $xA-I$ is also $\pmatrix{1 & 0 \\ 0 & x^2+1}.$ Hence $A$ and $B$ are similar over $\Bbb{Z}$.
More in the book Integral Matrices by M. Newman (chapter III section 14).
A: The following argument is inspired by tomasz's answer. Set 
$$
B:=\begin{pmatrix}0 & -1 \\ 1 & 0\end{pmatrix},\quad G:=\text{SL}(2,\mathbb Z),\quad H:=G/\{\pm\ I\},
$$
($I$ being the identity matrix), and let $\pi:G\to H$ be the canonical projection. 
Since $B$ and $-B$ are conjugate in ${GL}(2,\mathbb Z)$, it suffices to verify that $\pi(A)$ and $\pi(B)$ are conjugate in $H$. 
The action of $G$ on the upper half-plane $U$ of $\mathbb C$ by Möbius transformations induces a faithful action of $H$ on $U$. It is not hard to check that an element of finite order of $H$ has a fixed point on $U$. Then, using Theorem VII.1 of Serre's A Course in Arithmetic, one sees that the order two elements of $H$ are conjugate, as required. 
EDIT. The following is implicit above and in tomasz's answer:
Two elements of $\text{SL}(2,\mathbb Z)$ having the same finite order are conjugate in $\text{GL}(2,\mathbb Z)$.
Let me also point out that the proof of Theorem VII.1 in Serre's A Course in Arithmetic is short, self-contained, and (is it necessary to add?) wonderfully written.
