# How to find an integer matrix $P$ such that $PAP^{-1}=B$ for given two similar, integer matrices $A$ and $B$?

An integer matrix is a matrix whose coefficients are integers.

Suppose that two given invertible, integer $3\times 3$ matrices $A$ and $B$ are similar to each other, that is, there exists an invertible, integer matrix $P$ such that $PAP^{-1}=B$.

Assuming that we know such a matrix $P$ exists, how can we concretely find $P$?

I would like to know how to find $P$ for the case that $A=\begin{bmatrix}0&25&37\\ 0&2&3\\1&0&38\end{bmatrix}$ and $B=\begin{bmatrix}0&23&297\\ 0&12&155\\1&0&28\end{bmatrix}$.

(One can check that $A$ and $B$ are similar by using a theorem of Latimer and MacDufee.)

• Isn't that usually called that they are similar to each other? Conjugate matrix usually means element wise complex conjugation: mathworld.wolfram.com/ConjugateMatrix.html Commented Aug 12, 2017 at 16:40
• Also integral matrix can be confusing as it can also mean matrix that performs/represents integration. Commented Aug 12, 2017 at 16:42
• An algorithm for solving simiilarity of $3\times 3$ integer matrices is proposed by Applegate and Onishi in this 1982 paper. Commented Aug 12, 2017 at 16:48

Note that $\chi_A(x)=\chi_B(x)=p(x)=x^3-40x^2+39x-1$ is irreducible and has $3$ distinct roots $(\lambda_i)$. Here $PA=BP$ with $\det(P)=1$; then $P$ sends any eigenvector of $B$ associated to $\lambda_i$ to an eigenvector of $A$ associated to the same $\lambda_i$; moreover, the eigenvectors are defined up to a multiplicative constant. The set $\{R;RA=BR\}$ is a vector-space of dimension $3$. Then an equality of the form $Ru=v$, where $u,v$ are given vectors, define in general a unique $R$.

An eigenvector of $A$ (resp. of $B$) associated to $\lambda_i$ is $U_i=[1+37\lambda_i,3\lambda_i,-2\lambda_i+\lambda_i^2]^T$ (resp. $W_i=[1+297\lambda_i,155\lambda_i,-12\lambda_i+\lambda_i^2]^T$) and $P(U_i)=a_iW_i$ where $a_i\in\mathbb{C}$. It is easy to see that $U=\sum_iU_i=[1483,120,1442]^T$ and $P(U)=\sum_ia_iW_i$ is an integer vector.

Thus (*) $\sum_ia_i,\sum_ia_i\lambda_i,\sum_ia_i\lambda_i^2$ are rational numbers and the $(a_i)$ are in $F$, the decomposition-field of $p$. On the other hand, $\dfrac{\det(U_1,U_2,U_3)}{\det(W_1,W_2,W_3)}=3/155$ implies that $a_1a_2a_3=3/155$.

Consequently, the $(a_i)$ are the roots of a polynomial $q(y)$ that is the image of $p$ by a transformation $y=u+vx+wx^2$ where $u,v,w$ are rational numbers. Note that $q$ must be in the form $q(y)=y^3+\cdots-3/155$. We seek solutions $(u,v,w)$ in the form $n/155$ where $n\in\mathbb{Z}$ and we obtain $3$ candidates: $(-13/155,28/155,-1/155),(-1/155,26/155,-12/155),(12/155,-2/155,-11/155)$ (maybe there are other solutions). It remains to see that the associated solutions $P$ are (or are not) integer-matrices.

Case 1. We obtain $P(U)=[-33012,-17227,-3004]^T$ and $P$ is the matrix obtained by Axel Kemper (with the little radius). $P$ is an integer matrix and is convenient.

Case 2. We obtain $P(U)=[-1288409,-672344,-117124]^T$, $P=\begin{pmatrix}-23&2&-870\\-12&1&-454\\-2&-2&-79\end{pmatrix}$ and $P$ is convenient.

Case 3. We obtain $P(U)=[-1255397,-655117,-11412]^T$; yet, $P$ is not an integer matrix and is not convenient

Since $galois(p)=S_3$, there are no algebraic relations with coefficients in $\mathbb{Q}$ linking the $(a_i)$ and there is a cycle $\sigma\in Galois(p)$ s.t. $\sigma(\lambda_i)=\lambda_{i+1}$. According to (*) above, $a_i\in F$, the decomposition-field of $p$ and (reverse the Vandermonde matrix) $a_1=u+v\lambda_1+w\lambda_i^2,a_2=\sigma(a_1),a_3=\sigma(a_2)$, where $u,v,w$ are rational numbers. Finally, the $(a_i)$ are the roots of a polynomial that is the image of $p$ by the transform $x\rightarrow u+vx+wx^2$.

Along the lines of this related post:

Transform equation

$$PAP^{-1}=B$$

to

$$PA = BP$$

by multiplying both sides of the equation with matrix $P$.

Then, you find the solution via a calculation of Eigenvectors.

Alternative:

int: n = 3;

array[1..n, 1..n] of int: A = [| 0, 25,  37
| 0,  2,   3
| 1,  0,  38 |];
array[1..n, 1..n] of int: B = [| 0, 23, 297
| 0, 12, 155
| 1,  0,  28|];
array[1..n, 1..n] of var -20000 .. 20000: P;

constraint forall(i in 1..n, j in 1..n)(
sum(k in 1..n)(P[i,k]*A[k,j]) == sum(k in 1..n)(B[i,k]*P[k,j])
);

solve satisfy;

output [if j == 1 then "\n" else "" endif ++ show(P[i, j]) ++ " " | i in 1..n, j in 1..n];


Result is

$$P=\begin{bmatrix}19995&-17948&-19979\\ 8093&19876&-10454\\ -694&23&563\end{bmatrix}$$

By decreasing the search radius, I arrived at

$$P=\begin{bmatrix}-2&26&-23\\ -1&13&-12\\ 0&-1&-2\end{bmatrix}$$

• Could you please see whether $A$ and $$C=\begin{bmatrix}0&1&0\\ 0&1&1\\ 1&0&39\end{bmatrix}$$ are similar over the integers (with determinant $1$)? It turns out there are several similarity classes with this characteristic polynomial. Commented Aug 13, 2017 at 3:32
• The way you solved the problem there could be a matrix $P$ for my $C$ but with determinant not equal to $\pm 1,$ as with your first matrix with the large entries. Commented Aug 13, 2017 at 3:58
• @WillJagy: for your $C$ I found $$P=\begin{bmatrix}1&0&-1\\ -1&25&-1 \\ 0&0&1\end{bmatrix}$$ However, determinant of $P$ is $25$. Commented Aug 13, 2017 at 13:13
• Axel, thank you. In comments below my answer and the third answer, the OP confirmed that he intended determinant $1.$ He also stated that he already knew that my $C$ would not be similar over $\mathbb Z$ to the original $A,B.$ Most likely that he is calculating in an algebraic number field, while the matrices followed on that. Commented Aug 13, 2017 at 16:36

You could just write $P=\begin{bmatrix}a_{1}&a_{2}&a_{3}\\a_{4}&a_{5}&a_{6}\\a_{7}&a_{8}&a_{9} \end{bmatrix}$ and then you have $PA=BP$, so you can solve the system of equations $$\begin{bmatrix}a_{3}&25a_{1}+2a_{2}&37a_{1}+3a_{2}+38a_{3}\\a_{6}&25a_{4}+2a_{5}&37a_{4}+3a_{5}+38a_{6}\\a_{9}&25a_{7}+2a_{8}&37a_{7}+3a_{8}+38a_{9} \end{bmatrix}=\begin{bmatrix}23a_{4}+297a_{7}&23a_{5}+297a_{8}&23a_{6}+297a_{9}\\12a_{4}+155a_{7}&12a_{5}+155a_{8}&12a_{6}+155a_{9}\\a_{1}+28a_{7}&a_{2}+28a_{8}&a_{3}+28a_{9} \end{bmatrix}$$ which lead us to the system \begin{align*} a_{3}-23a_{4}-297a_{7}&=0\\ a_{6}-12a_{4}-155a_{7}&=0\\ a_{9}-a_{1}-28a_{7}&=0\\ 25a_{1}+2a_{2}-23a_{5}-297a_{8}&=0\\ 25a_{4}-10a_{5}-155a_{8}&=0\\ 25a_{7}-a_{2}-26a_{8}&=0\\ 37a_{1}+3a_{2}+38a_{3}-23a_{6}-297a_{9}&=0\\ 37a_{4}+3a_{5}+26a_{6}-155a_{9}&=0\\ 37a_{7}+3a_{8}+10a_{9}-a_{3}&=0 \end{align*} which is the same as $$\begin{bmatrix} 0&0&1&-23&0&0&-297&0&0\\ 0&0&0&-12&0&1&-155&0&0\\ -1&0&0&0&0&0&-28&0&1\\ 25&2&0&0&-23&0&0&-297&0\\ 0&0&0&25&-10&0&0&-155&0\\ 0&-1&0&0&0&0&25&-26&0\\ 37&3&38&0&0&-23&0&0&-297\\ 0&0&0&37&3&26&0&0&-155\\ 0&0&-1&0&0&0&37&3&10 \end{bmatrix} \begin{bmatrix}a_{1}\\a_{2}\\a_{3}\\a_{4}\\a_{5}\\a_{6}\\a_{7}\\a_{8}\\a_{9}\end{bmatrix}=\begin{bmatrix}0\\0\\0\\0\\0\\0\\0\\0\\0\end{bmatrix}$$ which is ugly but can be resolved by pivoting

• Your matrix whose entries are $a_i$ may not have determinant 1. Commented Aug 13, 2017 at 3:58

Probably worth pointing out that Latimer-Macduffee says that there are 16 similarity classes of matrices with characteristic polynomial $x^3 - 40 x^2 + 39 x - 1,$ as

? K = bnfinit(x^3 - 40*x^2 + 39*x - 1);
? K.disc
%2 = 1968377
? factor(K.disc)
%3 =
[431 1]

[4567 1]

? K.clgp
%4 = [16, [16], [[35, 11, 20; 0, 1, 0; 0, 0, 1]]]
?


which means that the two given matrices were not really guaranteed to be similar over the integers, at least, not by the information shown in the original question above. See pages 49-55 in Newman's book, especially Theorem III.14 on page 53. From Keith Conrad

In particular, your matrices $A,B$ appear to not be similar over the integers to

$$C = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 39 \end{array} \right)$$

? c = [ 0,1,0; 0,1,1; 1,0,39]
%1 =
[0 1 0]

[0 1 1]

[1 0 39]

? charpoly(c)
%2 = x^3 - 40*x^2 + 39*x - 1
?


After Axel posted his item I decided to try to program the thing; slower, by far...

===================================================================

 Determinant       0  :      0    0    0    0    0    0    0    0    0
Determinant      -1  :      2  -26   23    1  -13   12    0    1    2
Determinant       1  :     -2   26  -23   -1   13  -12    0   -1   -2
Determinant      -8  :      4  -52   46    2  -26   24    0    2    4
Determinant       8  :     -4   52  -46   -2   26  -24    0   -2   -4
Determinant  -10825  :     21   27 -113    8   51  -59   -1   -2   -7
Determinant   10825  :    -21  -27  113   -8  -51   59    1    2    7
Determinant   -7969  :     23    1  -90    9   38  -47   -1   -1   -5
Determinant    7969  :    -23   -1   90   -9  -38   47    1    1    5
Determinant   -5175  :     25  -25  -67   10   25  -35   -1    0   -3
Determinant    5175  :    -25   25   67  -10  -25   35    1    0    3
Determinant   -2449  :     27  -51  -44   11   12  -23   -1    1   -1
Determinant    2449  :    -27   51   44  -11  -12   23    1   -1    1


===================================================================

int main()
{

system("date");
int bound = 35;

for(int d = 0; d <= bound; ++d){
for(int g = -bound; g <= bound; ++g) {

int c = 23 * d + 297 * g;
int f = 12 * d + 155 * g;
for(int a = -bound; a <= bound; ++a){
int i = a + 28 * g;
for(int b = -bound; b <= bound; ++b){
for(int e = -bound; e <= bound; ++e){
for(int h = -bound; h <= bound; ++h) {
if( 25 * a + 2 * b == 23 * e + 297 * h  &&  25 * d + 2 * e == 12 * e + 155 * h && 25 * g + 2 * h == b + 28 * h ){
for(int f = -bound; f <= bound; ++f){
if( 37 * a + 3 * b + 38 * c == 23 * f + 297 * i &&  37 * d + 3 * e + 38 * f == 12 * f + 155 * i &&  37 * g + 3 * h + 38 * i == c + 28 * i ) {
int n =  (i*e - h*f)*a + ((-i*d + g*f)*b + (h*d - g*e)*c);
cout << " Determinant  " << setw(6) << n << "  :  "   << setw(5) << a   << setw(5) << b   << setw(5) << c   << setw(5) << d   << setw(5) << e   << setw(5) << f   << setw(5) << g   << setw(5) << h << setw(5) << i   << endl;
cout << " Determinant  " << setw(6) << -n << "  :  "   << setw(5) << -a   << setw(5) << -b   << setw(5) << -c   << setw(5) << -d   << setw(5) << -e   << setw(5) << -f   << setw(5) << -g   << setw(5) << -h << setw(5) << -i   << endl;
} // if 13 23 33
} // for f

} // if 12  22 32
}}}  // b e h
} // for a

}} // d g

system("date");

return 0;
}

• I know that $A$ and $B$ are not similar to $C$. By the way, how do you find the matrix $C$ which has the same characteristic polynomial? Commented Aug 13, 2017 at 3:58
• @user7540 you really should add to your question that the determinant of $P$ should be $1.$ Commented Aug 13, 2017 at 4:01
• I wrote $P$ is an invertible, integer matrix. Commented Aug 13, 2017 at 4:22
• Let $I_A$ and $I_B$ the ideal classes correspond to $A$ and $B$ via the Latimer-MacDurfee bijection. I know that $I_A$ and $I_B$ are same, and hence $A$ and $B$ are similar. Commented Aug 18, 2017 at 13:01
• Your c++ needs indenting Commented Nov 22, 2019 at 1:43