# 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

## 1 Answer

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).

• 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