Let $S := \{A\_0, A\_1, \dots, A\_d\}$, where $A\_k \in \mathbb{C}^{n \times n}$, be a set of (generally noncommuting) matrices. I am interested in finding a nonsingular $X \in \mathbb{C}^{n \times n}$ such that the elements of


$$SX = \{A\_kX \colon k=0,1,\dots,d\}$$


commute. In other words, I want a nonsingular $X$ such that


$$A\_iXA\_j = A\_jXA\_i, \quad \forall i,j \in \{0,1,\dots,d\}.\tag{\*}$$



> 
> More precisely, depending on $d$, I am interested in:
> 
> 
> 1. the conditions that $S$ has to fulfill so that such $X$ exists,
> 2. an algorithm to find such matrix $X$,
> 3. any structural properties that either $X$ or the elements of $SX$ might have.
> 
> 
> Preferably, I'd like to keep within the matrices of order $n$, i.e., I want to avoid my problems to grow to order $nd$ or $n^2$.
> 
> 
> 


Note that it is perfectly O.K. to request nonsingular $X,Y$ such that the elements of $XSY$ commute, but this is equivalent to


$$XA\_iYXA\_jY = XA\_jYXA\_iY, \quad \forall i,j \in \{0,1,\dots,d\},$$


which is the same as


$$A\_i(YX)A\_j = A\_j(YX)A\_i, \quad \forall i,j \in \{0,1,\dots,d\},$$


so observing $XSY$ is equivalent to observing just $SX$.


Of course, $(\*)$ is a system of linear equations, but its order is $nd$, and I'd like to avoid dealing with that. Also, I would like to be able if such $X$ exists before actually trying to find it (my point 1 above).


Searching for a way to solve this, I have found the (answered) question "[Is there a name for the matrix equation $A X B + B X A + C X C = D$?](https://mathoverflow.net/q/6166/36450)", which looks a lot like my $d = 1$ case \*I don't impose structural restrictions that are present there). However, I want to avoid using Kronecker product suggested in the most voted answer there, for two reasons:


1. It is hard to determine if $X$ is nonsingular from $\operatorname{vec}(X)$, and the theoretical aspect (my point 1 above) is my primary interest.
2. The matrices I obesrve may be quite large, so blowing them up from order $n$ to order $n^2$ is not acceptable.


Testing the case $d = 1$ on random generated matrices suggests that such $X$ (almost?) always exists, but I have no idea how to prove that. For $d > 1$, as one would expect, such $X$ sometimes exists, and sometimes does not, but I've managed to find no pattern on when it does.



For a set of matrices $S$, find $X$ such that the elements of $SX$ commute
This is not a complete solution by any means, but here are some ideas.


If one of $A\_j$ (or their linear combinations) is invertible, then one can get
a necessary and sufficient condition. Namely, if $B\_i=A\_iX$ commute then so do $B\_iB\_j^{-1}=A\_iA\_j^{-1}$. So one can take $A\_iA\_j^{-1}$ and see if it commutes with $A\_kA\_j^{-1}$. In the other direction, if $A\_iA\_j^{-1}$ commute for all $i$ and fixed $j$ then you get what you want by picking $X=A\_j^{-1}$.


This doesn't sound like a particularly practical criterion, because inverse calculation may be a mess. Also, even if $A\_i$ are nice, say sparse, the matrices $A\_iA\_j^{-1}$ may not be sparse at all. Still, it's something.


It might be easier if one of $A\_iA\_j^{-1}$ has distinct eigenvalues. One can try to calculate eigenvectors of $A\_iA\_j^{-1}$ by finding the 
roots of $det(A\_i-\lambda A\_j)$ and then solving the system (don't know how practical this is).


