# Permutation of kronecker products

I would like to be able to compute a re-ordered kronecker product from the result of another kronecker product. For example, consider $$F=A\otimes B\otimes C\otimes D\otimes E$$ from the result F and the sizes of the different matrices (The matrices $A, B, C, D$ and $E$ themselves are not known!), I would like to get the result of say, $$H=A\otimes C\otimes D\otimes B\otimes E$$ which is just a re-ordering of $F$.

Is there any good algorithm for doing this and doing it efficiently for possibly very large matrices?

• This just amounts to a permutation similarity – Omnomnomnom Jul 6 '15 at 15:53
• Do we have the sizes of $A,B,C,D,E$? – Omnomnomnom Jul 6 '15 at 16:36
• Yes we know the sizes of each matrix and the order in which they occur in the kronecker product. – Patrick Mboma Jul 6 '15 at 19:21

I don't know how to generalize for different sizes of the matrices, but here goes my answer:

Try to show the following lemma:

Let $T_1,\ldots,T_m \in L(V,V)$ and $A_1,\ldots,A_m$ be square matrices $n \times n$.

Show that

i) $(T_1 \otimes \cdots \otimes T_m)P(\sigma)=P(\sigma)(T_{\sigma(1)} \otimes \cdots \otimes T_{\sigma(m)})$

ii) There exists a permutation matrix $Q$ such that $A_{\sigma(1)} \otimes \cdots \otimes A_{\sigma(m)}=Q(A_1 \otimes \cdots \otimes A_m)Q^{T}$. Hint: Use i).

• The matrices are not necessarily square. – Patrick Mboma Jul 6 '15 at 19:23
• You can use that there exist permutation matrices $P$ and $Q$ such that $A \otimes B = P(B \otimes A)Q$. If $A$ and $B$ are square matrices, then we can take $Q=P^{T}$. – Leafar Jul 6 '15 at 19:28
• Dear Leafar, I am looking for a way to find those matrices. I do already know they exist. Thanks for your input. – Patrick Mboma Jul 6 '15 at 19:39