Exercise 4.3.5

We have $x=\mathit{vec}(X)=\mathit{vec}(G^{-1}B{(F^{-1})}^T)=(F^{-1}\otimes G^{-1})\mathit{vec}(B)=(F^{-1}\otimes G^{-1})b$, notice that $F^{-1}\otimes G^{-1}$ is the inverse of $F\otimes G$, multiply both sides by $F\otimes G$, we have

$(F\otimes G)x=b$, which recovers the original equation.

Solving $\mathit{Ax}=b$ is on the order of $O(n^3)$, where $n$ is the dimension of matrix $A$. We have $(\mathit{FG})x=b$, where $(F\otimes G)$ has a dimension of $n^2\times n^2$, so the total cost to solve $b$ using the original equation is $O\left({(n^2)}^3\right)=O(n^6)$.

With the equivalent system, we have to find $Z$ with $\mathit{GZ}=B$, and then find $X$ from $X{F}^T=Z$, both costs are $O(n^3)$ because all the matrices are size $n$.