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:

the conditions that $S$ has to fulfill so that such $X$ exists,

an algorithm to find such matrix $X$,

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:

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.

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.

1more comment