For a set of matrices $S$, find $X$ such that the elements of $SX$ commute

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$?", 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.

• I think that (*) is of order $n^2$ by $n^2d(d+1)/2$ or something like that, because there are $n^2$ unknowns in $X$. Am I right? – Lev Borisov Nov 9 '13 at 19:42
• @LevBorisov Yes, you are right. However, due to the specific form of these equations, I expect that the existence of the solution can be drawn directly from $A_k$, $k=0,\dots,d$, at least for some $d$. – Vedran Šego Nov 9 '13 at 21:07
• Do you expect $A_iX$ to be (simultaneously) diagonalizable, or are they expected to have nontrivial Jordan blocks? – Lev Borisov Nov 9 '13 at 21:19
• @LevBorisov I'd like to do this with as little assumptions on $A_k$ (or $A_kX$) as possible. If you can say something about this under the assumption that either $A_k$ or $A_kX$ are diagonalizable, I'd still be glad to hear it. – Vedran Šego Nov 9 '13 at 22:12
• I am interested in how you came up with this question. It is quite interesting. – Atsushi Kanazawa Nov 10 '13 at 17:46

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).
• Thank you, this is an interesting idea. I'm having trouble seeing why the commutativity of $\{B_i\}$ implies commutativity of $\{B_iB_j^{-1}\}$. If all $B_i$ are nonsingular, it is trivial, but how do you show that if some of them are singular? – Vedran Šego Nov 10 '13 at 16:39
• If $B_j$ is invertible, then $B_kB_j=B_jB_k$ implies $B_j^{-1}B_k=B_kB_j^{-1}$. Then you have $B_iB_j^{-1}B_kB_j^{-1} = B_iB_k B_j^{-2}$. So if $B_iB_k=B_kB_i$, you have the same thing for $B_iB_j^{-1}$. Does this make sense? – Lev Borisov Nov 10 '13 at 22:19
• You make plenty of sense, and this answer seems to be quite complete. It doesn't cover the case when all $A_i$ are singular, but given that any set of singular matrices is "thin", I don't see it as a problem. I will give it another day (or few) before accepting it, to see if any more answers pop up, possibly with some additional insights. Thank you for your help! – Vedran Šego Nov 11 '13 at 14:38
• Well, my answer gives no help if all $A_i$ are uppertriangular with zeroes on the diagonal :) – Lev Borisov Nov 12 '13 at 19:06