Let $A$ and $B$ be two $p \times p$ matrices, where $p$ can be large. I am interested in finding $C$, where $$vec(C) = (I_{p^2} - A \otimes A)^{-1}vec(B)\,. $$

Here $\otimes$ denotes the Kronecker Product. Of course, I can do this directly, but when $p$ is large, the Kronecker product is expensive, and in addition, the matrix inversion is expensive. Is there a simplification of the above that can yield in less computation.

On alternative is to note that since $vec(XYZ) = (Z^T \otimes X)vec(Y)$, \begin{align*} &vec(C) = (I_{p^2} - A \otimes A)^{-1}vec(B)\\ \Rightarrow & (I_{p^2} - A \otimes A) vec(C) = vec(B)\\ \Rightarrow & vec(C) - (A\otimes A)vec(C) = vec(B)\\ \Rightarrow & vec(C) - vec(ACA^T) = vec(B)\\ \Rightarrow & C - ACA^T = B. \end{align*}

If we could backsolve for $C$ efficiently, we could get a fast answer, but I don't know how I can do that without using the Kronecker product.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.