# Are these two explicitly given $10 \times 10$ matrices similar over the integers? Or equivalently, are they shift equivalent over $\mathbb{Z}$?

Are the following two $$10 \times 10$$ matrices $$A = \left[ \begin {array}{cccccccccc} 0&1&0&0&1&0&0&0&0&0 \\ 0&0&1&0&0&1&0&0&0&0\\ 1&0&0&1&0 &0&1&0&0&0\\ 1&0&0&0&0&0&0&1&0&0 \\ 0&0&0&0&0&1&0&0&0&0\\ 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&1&0\\ 0&0&0&0&0 &0&0&1&1&1\\ 0&0&0&0&0&0&0&0&1&1\end {array} \right]$$

and

$$B = \left[ \begin {array}{cccccccccc} 1&1&0&0&0&0&0&0&0&0 \\ 1&1&1&0&0&0&0&0&0&0\\ 0&1&0&0&0 &1&5&1&5&5\\ 0&0&0&0&1&0&6&10&5&1 \\ 0&0&1&0&0&1&6&6&10&5\\ 0&0&0&1&0 &0&10&5&1&5\\ 0&0&0&0&0&0&0&1&0&0 \\ 0&0&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\end {array} \right]$$ similar over $$\mathbb{Z}$$?

I believe the answer to be no, but if the answer is yes, then these matrices form a counterexample to something (to be described below) I've been trying to prove recently in my PhD project. Let me give some context to my question by first indicating what I've tried and found out so far, and then giving some motivation and background after that.

What I've tried: Both matrices have characteristic polynomial $${t}^{10}-2\,{t}^{9}-{t}^{8}-{t}^{7}+2\,{t}^{6}+6\,{t}^{5}-{t}^{3}-4\,{ t}^{2}-2\,t+1,$$ and they both have the same Frobenius/Rational canonical form, this being just the companion matrix of said polynomial:
$$F = \left[ \begin {array}{cccccccccc} 0&0&0&0&0&0&0&0&0&-1 \\ 1&0&0&0&0&0&0&0&0&2\\ 0&1&0&0&0 &0&0&0&0&4\\ 0&0&1&0&0&0&0&0&0&1 \\ 0&0&0&1&0&0&0&0&0&0\\ 0&0&0&0&1 &0&0&0&0&-6\\ 0&0&0&0&0&1&0&0&0&-2 \\ 0&0&0&0&0&0&1&0&0&1\\ 0&0&0&0&0 &0&0&1&0&1\\ 0&0&0&0&0&0&0&0&1&2\end {array} \right]$$ So we know that $$A$$ and $$B$$ are similar over $$\mathbb{Q}$$ (as they are both similar to $$F$$). I have actually been able to show that $$A$$ is similar to $$F$$ also over $$\mathbb{Z}$$. This was done using a "lucky" computer search: I ran through all size $$10$$ vectors $$\vec v$$ with entries in $$\{-1,0,1\}$$ and checked whether the matrix with columns $$\vec v$$, $$A \vec v$$, $$\ldots$$, $$A^9 \vec v$$ had determinant $$\pm 1$$. This was the case for a handful of $$\vec v$$'s, so these matrices witness the integral similarity of $$A$$ and $$F$$. The same search for $$B$$ did not yield any positive results though. I would like to try a search on a larger set of vectors, but this would require more computing power than I posess currently (being home for the summer holidays). If the matrices are not similar, this method will of course never give the answer though...

From the above we nevertheless have the following equivalent question: Are the matrices $$B$$ and $$F$$ above similar over $$\mathbb{Z}$$?

Another idea: Another idea I've had is to consider the matrices $$A$$ and $$B$$ (or $$F$$ and $$B$$) as matrices over the finite field $$\mathbb{F}_p$$ for various choices of the prime $$p$$. As this can be decided using the Frobenius form or Smith normal form. If there is a $$p$$ for which the matrices are not similar over $$\mathbb{F}_p$$, then they are not similar over $$\mathbb{Z}$$ either. So that would settle it. However, if for some large $$p$$, $$A$$ and $$B$$ are similar over $$\mathbb{F}_p$$, I hope that a the transformation matrix witnessing this similarity also could work over $$\mathbb{Z}$$, because the $$p$$ is so large. This is just speculation though. My problem is that I'm not sure which software I could use to perform these finite field calculations effeciently. Any feedback on this is greatly appreciated!

Motivation: This part will be a bit brief/cryptic, in order to keep it short, so please just let me know if I should give more details on something.

This question has come out of my recent attempts to prove that shift equivalence implies flow equivalence for (certain) non-negative integral matrices and their associated shifts of finite type. The dynamical systems called shifts of finite type, which are associated to a non-negative integer matrix, are described in the introductory textbook "An Introduction to Symbolic Dynamics and Coding" by Douglas Lind and Brian Marcus. Shift equivalence of matrices and flow equivalence of shifts of finite type are also explained in the book (starting on pages 233 and 453).

For non-negative integer matrices which are irreducible (meaning that for each $$i,j$$ $$A^n(i,j) > 0$$ for some $$n$$), it is known that shift equivalence implies flow equivalence. This is because in the irreducible case there is a complete algebraic invariant in terms of the defining matrix which determines flow equivalence. And it is not hard to see that shift equivalence over $$\mathbb{Z}$$ (which is weaker than mere shift equivalence) preserves the invariant.

For reducible matrices, however, the invariant is a lot more complicated. So in this case it is an open problem whether shift equivalence (over $$\mathbb{Z}$$) implies flow equivalence. It is not clear at all whether shift equivalence preserves the invariant. There is a recent paper in another field which hints at this potentially being true, so that is why I've spent some time trying to prove it. After failing to prove it I started searching for counterexamples instead. There are counterexamples if one allows the matrices to have "cyclic components", meaning that one irreducible component is essentially a permutaton matrix, but this makes the shifts of finite type a bit "degenerate" in some sense, so I want to avoid that.

The way shift equivalence over $$\mathbb{Z}$$ connects with similarity over $$\mathbb{Z}$$ is that this is actually equivalent, for matrices with determinant $$\pm 1$$ (i.e. those which are invertible over $$\mathbb{Z}$$). This is the case for $$A$$ and $$B$$. The matrices $$A$$ and $$B$$ are constructed to not be flow equivalent. They both have a similar block structure which is a by-product of the construction (edit: see the comments for the block structure), but I have chosen to not get into that.

Edit: Just to be clear, what I "hope for" is that the matrices are similar. For that would settle my underlying research question. If they turn out to not be similar (or if we cannot tell), then what I would like is to either try to construct some other matrices that might be similar (while still not being flow equivalent) based on the feedback here, or to try find some "underlying reason" why they can never be similar. For that might help me prove that shift equivalence implies flow equivalence.

• So, I'll ask again. How does the characteristic polynomial factor over $\Bbb Q$. Jul 31, 2019 at 16:01
• Just for information, I have no idea what it is worth. Seeing many entries divisible by $5$ I reduced $B$ modulo $5$ and then computed its characteristic polynomial (over $\Bbb Q$!); not only did I get the same value modulo $5$ as I expected, but I got the very same polynomial. So it might be that $B$ is similar to its own reduction modulo $5$ (with remainders in $\{0,1,2,3,4\}$), or if not maybe you've got a simpler example of the phenomenon of interest in the pair of $B$ and its reduction modulo $5$. Jul 31, 2019 at 16:29
• evidently the real difficulty here is that the characteristic polynomial reduces over the rationals. I've just been looking things up, see the simple example using algebraic numbers on page 12 of pdfs.semanticscholar.org/3dfe/… Also, reading from Newman's book on integral matrices, it is possible that the original Latimer MacDuffee result included reducible characteristic polynomials: Newman seems to saying that Taussky's 1949 proof did not. Jul 31, 2019 at 18:28
• A simplification that may or may not be useful: it suffices to investigate any similarity between $A$ and $C$ over $\mathbb Z$, where $C=B(J,J)$ with $J=(7,8,9,10,6,4,5,3,2,1)$. Note that $$A=\pmatrix{X&I_4&0\\ 0&X&F\\ 0&F^T&E},\ C=\pmatrix{X&0&0\\ Y&X&F\\ 0&F^T&E}$$ where $$X=\pmatrix{0&1&0&0\\ 0&0&1&0\\ 1&0&0&1\\ 1&0&0&0},\ F=\pmatrix{0&0\\ 0&0\\ 0&0\\ 1&0},\ E=\pmatrix{1&1\\ 1&1}$$ and $Y=5X^3+X^2+5X+5I$. We have $\det(A)=\det(Y)=-\det(X)=1$. Jul 31, 2019 at 20:13
• @Pjolter here are some notes by Keith Conrad kconrad.math.uconn.edu/blurbs/gradnumthy/matrixconj.pdf As with the other notes, I don't see any worked examples in large degree. I found that in mathoverflow.net/questions/51942/… My impression is that irreducible characteristic polynomial makes it more likely that there is a proof of non-similarity for your matrices, but there is still nothing easy about it. Meanwhile: I was just looking things up out of curiosity, this is hardly my area. Aug 1, 2019 at 0:38

I'm afraid they are similar over $$\mathbb Z$$, see solution below. Note that there is nothing magical about this solution : one simply computes "block-diagonal" similar matrices to $$A$$ and $$B$$ using the kernel decomposition theorem and the irreducible factors of the characteristic polynomial. Then, it suffices to compare the blocks of $$A$$ and $$B$$ one by one (admittedly, we are lucky here as it is much harder to show that two given matrices are not similar over $$\mathbb Z$$ in general, as explained in the MO link given in Will Jagy's comment).
Solution: One can check that $$\mathsf{det}(P)=1$$ and $$P^{-1}BP=A$$ for $$P = \left[ \begin {array}{cccccccccc} -169 & -150 & -127 & -92 & -6494 & -5581 & -4649 & -3194 & 743 & 3410\\ -50 & -19 & -23 & -35 & -1518 & -1063 & -1059 & -804 & 216 & 743\\ 161 & 119 & 131 & 104 & 6099 & 5107 & 4622 & 3120 & -804 & -3194\\ 288 & 275 & 178 & 132 & 10768 & 9245 & 7149 & 5107 & -1063 & -5581\\ 304 & 278 & 270 & 177 & 12266 & 10768 & 9244 & 6099 & -1518 & -6494\\ 280 & 179 & 137 & 161 & 9244 & 7149 & 6136 & 4622 & -1059 & -4649\\ 1 & 0 & 0 & 0 & 17 & 6 & 4 & 7 & 0 & -7\\ 0 & 1 & 0 & 0 & 12 & 17 & 6 & 4 & 0 & -7\\ 0 & 0 & 1 & 0 & 10 & 13 & 17 & 6 & -3 & -7\\ 0 & 0 & 0 & 1 & 6 & 4 & 10 & 7 & -4 & -3\\ \end {array} \right]$$
• Well done Ewan. I understand the general idea but some details seem obscure to me. What's interesting is that you do not use the $\mathbb{Z}[\alpha]$-ideal classes in $\mathbb{Q}[\alpha]$; using Magma, I made calculations by this method but for small values of $n$. Could you give some more details to enlighten me ?
• @loupblanc This is hardly my area, but consider this : the initial problem reduces to little more but the question of solving a 100x100 linear system $AP=PB$. The translation of this problem into ideal classes is overkill and unnecessary unless your have tables with ideal classes precomputed for you or if your software has special tools that treat ideal classes better than linear systems. Anyway, I did it with PARI-GP, using the factorization of the characteristic polynomial to reduce the initial 10x10 system to two systems (a 4x4 and a 6x6), which PARI-GP treats in a matter of seconds. Aug 1, 2019 at 19:31
• Thank you so much for your answer @EwanDelanoy!! I will make sure to thank you if this goes into my thesis. I did for a moment consider trying to solve $AP = BP$ over $\mathbb{Z}$, but that seemed too daunting. So I feel a bit silly now haha, but thanks for restoring my faith in computational software! Aug 1, 2019 at 21:21