# Vector Multiplication with Multiple Kronecker Products

My question concerns matrix-vector multiplications when your matrix has Kronecker structure, which can be done faster in that case.

I know how to compute this for a matrix $A = A_1 \otimes A_2$, which has two components $A_i$: $$Ax = (A_1 \otimes A_2)x = (A_1 \otimes A_2)vec(X) = vec(A_2XA_1^T)$$ where $vec(X) = x$ is the vectorization of $X$.

However, I have no idea how to proceed for more components $A_i$. I can imagine doing something as follows: $$Ax = (A_1 \otimes A_2 \otimes \cdots \otimes A_n)x = vec((A_2 \otimes \cdots A_n)XA_1^T) = (I_m \otimes A_2 \otimes \cdots \otimes A_n)vec(XA_1^T)$$ which provides me again with an actual matrix-vector multiplication. I was hoping to get a large identity matrix on the left-hand side this way, but no luck.

(EDIT: I realised it is impossible to do it this way, as the matrices $X$ and $A_1^T$ do not have the same dimensions.)

I tried looking it up on-line, but I mainly get the case for two components. Can anyone of you help me out? Thanks!

To summarize very briefly, what you want to do is to treat the vector $$x$$ as having a multi-dimensional index $$x_{i_1, i_2, ..., i_n}$$. Then you can sequentially multiply $$x$$ by the matrices $$A_1$$, $$A_2$$, etc. after an appropriate permutation of the indices. See discussion in Fino & Algazi (1976). Overall, this gives substantial savings in terms of memory and computational complexity. You save a factor of 2 in the exponent.