6
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Lev Borisov
    Nov 9, 2013 at 19:42
  • $\begingroup$ @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$. $\endgroup$
    – Vedran Šego
    Nov 9, 2013 at 21:07
  • $\begingroup$ Do you expect $A_iX$ to be (simultaneously) diagonalizable, or are they expected to have nontrivial Jordan blocks? $\endgroup$
    – Lev Borisov
    Nov 9, 2013 at 21:19
  • $\begingroup$ @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. $\endgroup$
    – Vedran Šego
    Nov 9, 2013 at 22:12
  • 1
    $\begingroup$ I am interested in how you came up with this question. It is quite interesting. $\endgroup$
    – Atsushi Kanazawa
    Nov 10, 2013 at 17:46

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Vedran Šego
    Nov 10, 2013 at 16:39
  • 1
    $\begingroup$ 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? $\endgroup$
    – Lev Borisov
    Nov 10, 2013 at 22:19
  • $\begingroup$ 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! $\endgroup$
    – Vedran Šego
    Nov 11, 2013 at 14:38
  • $\begingroup$ Well, my answer gives no help if all $A_i$ are uppertriangular with zeroes on the diagonal :) $\endgroup$
    – Lev Borisov
    Nov 12, 2013 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.