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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Nov 12, 2013 at 19:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .