The Kronecker product of two matrices is defined as:

$$\mathbf{A} \otimes \mathbf{B} = \begin{bmatrix} a_{11} \mathbf{B} & \cdots & a_{1n}\mathbf{B} \\ \vdots & \ddots & \vdots \\ a_{m1} \mathbf{B} & \cdots & a_{mn} \mathbf{B} \end{bmatrix}$$

Let $\mathbf{A}, \mathbf{B} \in \mathbb{R}^{n \times n}$ and let $\bar{n} = \frac{n(n+1)}{2}$. Then the symmetric Kronecker product of two matrices is defined as:

$$\mathbf{A} \otimes_s \mathbf{B} = \frac{1}{2}\mathbf{U}(\mathbf{A}\otimes\mathbf{B} + \mathbf{B}\otimes\mathbf{A})\mathbf{U}^T$$

where $\mathbf{UU}^T = \mathbf{I}$ and $\mathbf{U} \in \mathbb{R}^{\bar{n} \times n^2}$ and $\mathbf{I} \in \mathbb{R}^{\bar{n} \times \bar{n}}$.

Additionally, let the symmetric vectorization operator work on an $n \times n$ symmetric matrix $\mathbf{X}$ as follows: $$\mathrm{\mathbf{svec}}(\mathbf{X}) = (x_{11}, \sqrt{2}x_{21},...,\sqrt{2}x_{n1}, x_{22}, \sqrt{2}x_{32},...,\sqrt{2}x_{n2},...,x_{nn})^T$$


In practice, matrices in $\mathbb{R}^{n^2 \times n^2}$ and $\mathbb{R}^{\bar{n} \times \bar{n}}$ are too large to work with. If $n=200$, just storing $\mathbf{A} \otimes \mathbf{B} \in \mathbb{R}^{n^2 \times n^2}$ already requires more than 6 GB of storage. Fortunately, while working within a system of equations, the property

$$(\mathbf{A} \otimes_s \mathbf{B})\mathbf{svec}(\mathbf{X}) = \frac{1}{2}\mathbf{svec}(\mathbf{BXA}^T + \mathbf{AXB}^T)$$ allows us to solve $(\mathbf{A} \otimes_s \mathbf{B})\mathbf{svec}(\mathbf{X})$ without ever storing $\mathbf{A} \otimes_s \mathbf{B}$ or $\mathbf{A} \otimes \mathbf{B}$.

If I would like to instead solve $(\mathbf{A} \otimes_s \mathbf{B})^{-1}\mathbf{svec}(\mathbf{X})$, is there a similar space-efficient equation? I have tried deriving this myself, but cannot proceed past calculating the inverse of the sum of two Kronecker products. Any solutions, ideas, hints, or suggestions are welcome!


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.