Simultaneous similarity of pair of matrices

Question

Let $k$ be an arbitrary field, and $A,B,A',B'\in M_n(k)$. Do we have any algorithm with polynomial complexity to determine the simultaneous similarity of the pair $(A,B)$ with $(A',B')$?

I found the paper Friedman - Simultaneous similarity of matrices which solved the case when $k=\mathbb{C}$. Do we have similar results when $k$ is another field?

Edited: I am assuming that the operations in the field $k$ are constant time. The polynomial complexity refers to the complexity respect to $n$, the size of the matrix.

Answer 1

First find an invertible matrix $C$ conjugating $A$ to $A'$ (I assume you can do that in polynomial time). Consider $E=CBC^{-1}$. It remains to find an invertible $D$ which commutes with $A'$ and conjugates $E$ to $B'$. This is a system of homogeneous linear equations with a constraint that the determinant is not $0$.

Answer 2

So let me try to give a definite answer. We have a non-zero system of linear homogeneous equations $\Sigma$ in $n^2$ variables $x_{ij}$ having an infinite set of solutions and the matrix $M=((x_{ij}))$. We want to show that for some values of $x_{i,j}$ satisfying the system the determinant $\det(M)$ is not zero. Consider the general solution of the system and plug it in $M$. Thus we need to check if a matrix $M=((x_{i,j}))$ where each entry is a homogeneous linear polynomial, $\det(M)$ is not identically zero. Let, say, $z_1$, be the LEX smallest variable that appears in a polynomial in $M$. We can assume that it appears in $x_{1,1}$ (switching rows and columns can only change the sign of the determinant). Then using row and column transformations, we can make all linear polynomials in the first row and the first column of $M$ not depending on $z_1$. Then consider the cofactor matrix $M_{1,1}$. If its entries do not depend on $z$, we are done. If not, then put the entry containing $z$ in the left top corner of $M_{1,1}$ and continue. As a result we get a matrix $M'$ with linear polynomials containing $z$ on the diagonal and no $z$ appearing anywhere else. The determinant of that matrix is the same as $\det M$ up to sign and is a polynomial of degree $n$ in $z$, so it is not identical zero. That algorithm requires at most $n^8$ operations.

Answer 3

I just read this post and I see -with amusement- that a (knowledgeable?) reader downvoted this post. I believe -on the contrary- that the question is very interesting (although standard).

We give $A,B,A_1,B_1\in M_n(K)$ s.t. $A,A_1$ are similar, $B,B_1$ are similar. We are looking for an invertible $P=[p_{i,j}]\in GL_n(K)$ (if it exists) satisfying the linear system: $(1)$ $PA-A_1P=0$ and $(2)$ $PB-B_1P=0$.

The vector space of solutions of $(1)$ has the same dimension ($\geq n$ and generically, $n$) as $C(A)$ (the commutant of $A$). The vector space of solutions of $(1,2)$ (the intersection of $2$ subspaces) has generically the dimension $1$ when $P$ exists (that is, the solution is unique -up to a factor-). Of course the dimension $r$ may be $>1$: Let

$A=diag(J_3,J_4,J_5,J_8,I_4+J_4,I_6+J_6),A_1=QAQ^{-1}$,

$B=diag(2I_6+J_6,2I_7+J_7,2I_7+J_7,4I_5+J_5,4I_5+J_5),B_1=QBQ^{-1}$ where $Q$ is random and $J_k$ is the nilpotent Jordan block; then $r=9$.

First step; we solve $(1,2)$; an obvious solution is to calculate the kernel of $I\otimes A^T-A_1\otimes I$ (if we transform a matrix into a vector row by row). The complexity is $O(n^6)$ operations -we will come back to this subject below-

The general solution depends on $r$ parameters that can be chosen among the $p_{i,j}$.

Case 1. $K$ is infinite; it suffices to randomly choose the considered parameters; the obtained solution is invertible with probability $1$ (if $P$ exists). If, several tests give non-invertible solutions, then there are no solutions. The complexity is in $O(n^3)$.

Case 2. $K$ is finite. Then we need to do more tests, especially if $ K$ is small. Anyway, we can perform $O(n^3)$ tests without increasing the complexity... During my tests, I always found a valid solution very quickly.

$\bullet$ Finally, the true question is "can we solve $(1,2)$ in less than $O(n^6)$ operations?". Our downvoter certainly knows how to answer this question, but I can't. Indeed

1. There are many solvers for the Sylvester equation that work in $O(n^3)$: Bartels-Stewart, Hammarling, Hessenberg-Schur, Krylov subpaces techniques,... Yet, these methods work only when the spectra of $A,A_1$ are disjoint and, moreover, the unique solution is done as an approximation. Here we need an exact value of $P$ (because of the multiplicities of the eigenvalues ​​of our matrices); on the other hand, we cannot put our matrices in Schur form because we don't know how to calculate the eigenvalues. Of course, we can put $A,B$ in Frobenius form.

2. I am surprised that we do not know a faster method to solve equation $(1)$ because it presents an interesting pattern: $I\otimes A^T-A_1\otimes I$ presents, for $n=40$ and random matrices $A,B,P$, $95$% of zeros located at entries fixed in advance (of course, when $n>40$, the proportion is even greater).

We ask for a specialist in sparse matrices.

EDIT. Answer to LSpice.

$\textbf{Proposition.}$ We assume that $K$ is infinite. Let $A,B$ be random matrices and $P$ be any invertible matrix; then $r=1$ with probability $1$.

$\textbf{Proof.}$ We may assume that $K$ is algebraically closed (the dimension does not depend on the extension of the field). To be completely rigorous, we can reason using Zariski topology.

With probability $1$, $A,B$ have distinct eigenvalues and have each a basis of eigenvectors, say $(e_i),(f_i)$. Let $E=[e_1,\cdots,e_n],F=[f_1,\cdots,f_n]$. The $P(e_i)'s,P(f_i)'s$ are bases of eigenvectors of $A_1,B_1$ (that have also distinct eigenvalues).

Now, let $Q$ be the general matrix that ensures the simultaneous similarity. There are non-zero unknowns $(x_i),(y_i)$ s.t. $Q(e_i)=x_ie_i,Q(f_i)=y_if_i$, that is,

$QE=PEdiag(x_i),QF=PFdiag(y_i)$, or $Q=PEdiag(x_i)E^{-1}=PFdiag(y_i)F^{-1}$.

Finally, the condition is $F^{-1}Ediag(x_i)E^{-1}F=diag(y_i)$.

Since $E,F$ are random, $G=F^{-1}E$ too; from $Gdiag(x_i)G^{-1}=diag(y_i)$, we deduce that there is a permutation $\sigma$ s.t. $diag(x_i)=\sigma diag(y_i)\sigma^{-1}$.

Thus $U diag(y_i)=diag(y_i)U$, where $U=G\sigma$ is random. The sole diagonal matrices that commute with $U$ are the scalar matrices.

Consequently, $diag(x_i)=diag(y_i)=uI_n$ and $Q=uP$.