General question. Let $A$ and $B$ be two $n\times n$-matrices over $\mathbb{Z}$. How do I algorithmically check whether $A$ and $B$ are similar (i.e., conjugate in the ring $\mathbb{Z}^{n\times n}$)?
I am particularly interested in two special matrices, more on which below. However, let me first mark some trails (quite possibly leading nowhere):
If we replace $\mathbb{Z}$ by any field, then the problem becomes easy using the Frobenius canonical form. Unfortunately, similarity over fields is not enough: e.g., a square matrix $A$ is similar to its transpose $A^{T}$ over any field, but (in general) not over $\mathbb{Z}$. See Is a matrix over a PID similar to its transpose? for some examples of this. This also shows that various standard invariants (invariant factors, Jordan forms over $\mathbb{C}$, etc.) are insufficient to guarantee similarity.
Two matrices $A$ and $B$ in $\mathbb{Z}^{n\times n}$ are similar if and only if the polynomial matrices $tI_{n}-A$ and $tI_{n}-B$ in $\left( \mathbb{Z}\left[ t\right] \right) ^{n\times n}$ are congruent (i.e., equivalent under left and right multiplication by invertible matrices, not necessarily by the same matrix). Indeed, a proof of this fact has been sketched in on similar matrices and polynomial matrices for any commutative ring instead of $\mathbb{Z}$. Thus, checking similarity over $\mathbb{Z}$ reduces to checking congruence over $\mathbb{Z}\left[ t\right] $. Unfortunately, it's not clear if the latter is any easier.
I wouldn't be surprised if the problem can be reduced from $\mathbb{Z}$ to $\mathbb{Z}/n$ for some very high (but not prime) $n$. However, I'm ideally interested in a practicable algorithm, which can be used for two $24\times 24$-matrices for example.
How did I get interested in this? The specific problem I started with is probably less interesting to the wider world, but it provides a useful benchmark if nothing else. It comes from the study of random-to-top and top-to-random shuffling on the symmetric group.
Consider a positive integer $n$, and let $S_{n}$ be the symmetric group on the set $\left\{ 1,2,\dotsc,n\right\} $. We shall define an $n!\times n!$-matrix $A\in\mathbb{Z}^{n!\times n!}$ whose rows and columns are indexed by permutations in $S_{n}$. Specifically, for any two permutations $\sigma ,\tau\in S_{n}$, we let the $\left( \sigma,\tau\right) $-th entry of this matrix $A$ be the integer $1$ if the permutation $\tau^{-1}\circ\sigma$ is the cycle $\left( 1,2,\dotsc,i\right) $ for some $i\in\left\{ 1,2,\dotsc ,n\right\} $, and be the integer $0$ otherwise. (Note that the cycle $\left( 1\right) $ is understood to be the identity permutation; thus, all diagonal entries of $A$ are $1$.) For instance, if $n=3$, then $A$ looks as follows: \begin{align*} A=\left( \begin{array} [c]{cccccc} 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 1 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1 \end{array} \right) , \end{align*} where the elements of $S_{3}$ are ordered in lexicographic order (i.e., using one-line notation for permutations, we have $\left[ 1,2,3\right] <\left[ 1,3,2\right] <\left[ 2,1,3\right] <\left[ 2,3,1\right] <\left[ 3,1,2\right] <\left[ 3,2,1\right] $). Let $B$ be the transpose $A^{T}$ of this matrix.
What I'm wondering is whether $A$ and $B$ are similar over $\mathbb{Z}$. This is easily seen to hold for $n\leq3$. In fact, $A$ is conjugate to $B$ by a permutation matrix if $n\leq3$. However, a permutation matrix does not suffice for $n=4$. Could another invertible matrix do the trick? This is the first case I would like to hear the answer. In this case, explicitly, \begin{align*} A & =\left( \begin{array} [c]{rrrrrrrrrrrrrrrrrrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right) \ \ \ \ \ \ \ \ \ \ \text{and}\\ B & =A^{T}. \end{align*} (This has been generated using some simple Sage code.)
In more conceptual terms, the matrices $A$ and $B$ describe two Markov chains on the symmetric group $S_{n}$: the matrix $A$ describes the "top-to-random shuffle", whereas the matrix $B$ describes the "random-to-top shuffle", or vice versa, depending on how we identify permutations with card decks.
Algebraically, $A$ and $B$ represent two $\mathbb{Z}$-module endomorphisms of the group ring $\mathbb{Z}\left[ S_{n}\right] $: namely, if we set \begin{align*} \mathbf{A}:=\underbrace{\left( 1\right) }_{\text{a }1\text{-cycle} }+\underbrace{\left( 1,2\right) }_{\text{a }2\text{-cycle}} +\underbrace{\left( 1,2,3\right) }_{\text{a }3\text{-cycle}}+\cdots +\underbrace{\left( 1,2,\dotsc,n\right) }_{\text{an }n\text{-cycle}} \in\mathbb{Z}\left[ S_{n}\right] , \end{align*} then $A$ represents right multiplication by $\mathbf{A}$, whereas $B$ represents left multiplication by $\mathbf{A}$. It is well-known (see, e.g., Theorem 3 in Is this sum of cycles invertible in $\mathbb QS_n$? ) that $\prod _{i\in\left\{ 0,1,\dotsc,n-2,n\right\} }\left( \mathbf{A}-n\right) =0$ in $\mathbb{Z}\left[ S_{n}\right] $, which shows that both $A$ and $B$ are diagonalizable over $\mathbb{Q}$ with diagonal entries $0,1,\dotsc,n-2,n$ (whose multiplicities can also be computed). Section 4 from my Waterloo 2022 talk The one-sided cycle shuffles in the symmetric group algebra gives some more context. If $A$ and $B$ are similar, then essentially any property of $A$ yields an analogous property of $B$ and vice versa, which would be very convenient for the study of $A$ and $B$. Arguably, much is already known about $A$ and $B$, but there are other, less standard, situations in which one similarly wants to jump around between left and right actions.
