# Space-Efficient Calculations using Symmetric Kronecker Product: $(A\otimes_sB)^{-1}x$

## Introduction:

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$$

## Problem:

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!