2
$\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$
4
$\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$
  • 1
    $\begingroup$ Nice proof! It might be even clearer to invoke the summation convention and drop all the $\Sigma$'s. $\endgroup$ – greg Apr 21 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$ – Omnomnomnom Apr 21 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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.