7
$\begingroup$

I want to show the Kronecker Product identity listed on Wikipedia: $$\begin{align} \mathrm{vec}(AXB) =(B^T \otimes A) \mathrm{vec}(X) \\ \tag{1} \end{align}$$ Wikipedia does not cite references for the proof for (1), and I want to verify. Before the calculation, agree with some convention. Let us denote $a\; \mathrm{mod}\; b$ for the remainder of $a$ modulo $b$ (so that $9\; \mathrm{mod}\; 4 =1$). This is unlike the usual practice, but otherwise the expression gets too verbose. Moreover let us denote the $(i,j)$-th entry of $A$ to be $A_{i,j}$, and $i$-th entry of $v$ to be $v_{i}$. Also say that $A \in \mathbb{R}^{M \cdot N}$ if it is a $M$ by $N$ matrix, by slightly abusing the meaning of $\mathbb{R}$. If we stick to only addition and multiplication, once the proof works, it works for any field.

Firstly, restate the formal definition of Kronecker product and vectorization, for later use. For $X' \in \mathbb{R}^{N_2 \cdot N_3}$ $$\begin{align} (\mathrm{vec}(X'))_{m_1} =X'_{m_1\; \mathrm{mod}\; N_1, \lceil m_1/N_1 \rceil} \\ \tag{2} \end{align}$$

For $A' \in \mathbb{R}^{N_1 \cdot N_2}, B' \in \mathbb{R}^{N_3 \cdot N_4}$, $$\begin{align} (A' \otimes B')_{m_1, m_2} =A'_{\lceil m_1/N_3 \rceil, \lceil m_2/N_4 \rceil} B'_{m_1\; \mathrm{mod}\; N_3, m_2\; \mathrm{mod}\; N_4} \\ \tag{3} \end{align}$$

Now, let $A \in \mathbb{R}^{N_1 \cdot N_2},\; X \in \mathbb{R}^{N_2 \cdot N_3},\; B \in \mathbb{R}^{N_3 \cdot N_4},$, We try to evaluate lhs and rhs of (1).

$$\begin{align} &(\mathrm{vec}(AXB))_{m_1} \\ =&(AXB)_{m_1\; \mathrm{mod}\; N_1, \lceil m_1/N_1 \rceil} \\ =&\sum_{n_2=1}^{N_2} \sum_{n_3=1}^{N_3} A_{m_1\; \mathrm{mod}\; N_1, n_2} X_{n_2, n_3} B_{n_3, \lceil m_1/N_1 \rceil} \\ \tag{4} \end{align}$$

$$\begin{align} &((B^T \otimes A) \mathrm{vec}(X) )_{m_1} \\ =&\sum_{m_2=1}^{N_2 N_3} (B^T \otimes A)_{m_1, m_2} \mathrm{vec}(X)_{m_2} \\ =&\sum_{m_2=1}^{N_2 N_3} (B^T)_{\lceil m_1/N_1 \rceil, \lceil m_2/N_2 \rceil} A_{m_1\; \mathrm{mod}\; N_1, m_2\; \mathrm{mod}\; N_2} \mathrm{vec}(X)_{m_2} \\ =&\sum_{m_2=1}^{N_2 N_3} B_{\lceil m_2/N_2 \rceil, \lceil m_1/N_1 \rceil} A_{m_1\; \mathrm{mod}\; N_1, m_2\; \mathrm{mod}\; N_2} X_{m_2\; \mathrm{mod}\; N_2, \lceil m_2/N_2 \rceil} \\ \tag{5} \end{align}$$

It would seem that we are close, but it is not obvious that (4) and (5) are equal. Although $A$'s row index $m_1\; \mathrm{mod}\; N_1$ and $B$'s column index $\lceil m_1/N_1 \rceil$ agree, the other do not. It is suggestive that maybe if we "sum away" $n_2, n_3$, we might find them to agree, but $A,X,B$ are all free, and we have nothing to exploit to carry out that summation.

$\endgroup$

2 Answers 2

9
$\begingroup$

Your effort is valiant, but I can tell you from experience that it is helpful to avoid getting into the quagmire of modular arithmetic (or of directly indexing of a Kronecker product at all) when possible. Here's how I would prove the statement:

First, it helps to note that for any column-vectors $u,v,$ we have $$ \operatorname{vec}(uv^T) = v \otimes u $$ I think you will find proving this statement to be a useful exercise. In fact, I prefer to take the above equation to be the definition of the vectorization operator (wikipedia defines the operator as "stacking the columns").

Let $e_1,\dots,e_n$ denote the canonical basis (i.e. the columns of the $n \times n$ identity matrix). Let $X = (x_{ij})_{i,j = 1}^{m,n}$. We have $$ \begin{align} \operatorname{vec}(AXB) &= \operatorname{vec}\left(A\left(\sum_{i=1}^m \sum_{j=1}^n x_{ij} e_ie_j^T\right)B\right) \\ & = \sum_{i=1}^m\sum_{j=1}^n x_{ij} \operatorname{vec}(Ae_ie_j^TB) \\ & = \sum_{i=1}^m\sum_{j=1}^nx_{ij} \operatorname{vec}([Ae_i][B^Te_j]^T) \\ &= \sum_{i=1}^m\sum_{j=1}^nx_{ij} [B^Te_j]\otimes [Ae_i] \\ &= (B^T \otimes A)\left(\sum_{i=1}^m\sum_{j=1}^nx_{ij} e_j \otimes e_i\right) \\ &= (B^T \otimes A)\left(\sum_{i=1}^m\sum_{j=1}^nx_{ij} \operatorname{vec}(e_i e_j^T)\right) \\ &= (B^T \otimes A)\operatorname{vec}\left(\sum_{i=1}^m\sum_{j=1}^nx_{ij} e_i e_j^T\right) = (B^T \otimes A)\operatorname{vec}(X) \end{align} $$

$\endgroup$
2
  • 1
    $\begingroup$ Nice proof! It might be even clearer to invoke the summation convention and drop all the $\Sigma$'s. $\endgroup$
    – greg
    Commented Apr 21, 2019 at 19:31
  • 1
    $\begingroup$ @greg Thanks. And thanks for the suggestion: while I'm sure dropping $\Sigma$s would make the proof less cluttered, I'm sure it would make the proof confusing to those unaccustomed to Einstein notation, and anyway I've never been much of a fan of that convention. Another approach I considered is proving that the statement holds for $X = e_ie_j^T$, then stating that the full result holds "by linearity". $\endgroup$ Commented Apr 21, 2019 at 19:59
0
$\begingroup$

I see! In (5), as $m_2 =1, \dots, N_2 N_3$, we see that $m_2\; \mathrm{mod}\; N_2 =1, \dots N_2$, and $\lceil m_2/N_2 \rceil =1, \dots N_3$, same as the numbering of $n_2, n_3$ respectively in (4).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .