Almost Commutative Kronecker Product

Introduction

Tensor product and Kronecker product are very important in quantum mechanics. It also have practical physical meanings for quantum processes. One of the interesting properties of Kronecker product is that it is “almost commutative”.

In this blog post, I would like to informally discuss the “almost commutative” property for Kronecker product.

Outer Product

Given two vectors $u = \{u_0, u_1, \cdots, u_{m-1}\}$ and $v = \{v_0, v_1, \cdots, v_{n-1}\}$, the outer product of $u$ and $v$, denoted as $u \otimes v$, is defined as

$$
\begin{align}
u \otimes v &=
\begin{bmatrix}
u_0 v_0 & u_0 v_1 & \cdots & u_0 v_{n-1}\\
u_1 v_0 & u_1 v_1 & \cdots & u_1 v_{n-1}\\
\vdots & \vdots & \ddots & \vdots \\
u_{m-1} v_0 & u_{m-1} v_1 & \cdots & u_{m-1} v_{n-1}\\
\end{bmatrix} \nonumber\\
\end{align}
$$

Using index notation,

$$
(u \otimes v)_{i,j} = u_i v_j
$$

If $u$ and $v$ are column vectors, i.e., $u = [u_0, u_1, \cdots, u_{m-1}]^{\top}$ and $v = [v_0, v_1, \cdots, v_{n-1}]^{\top}$, the outer product could also be simply expressed using matrix multiplication.

$$
\begin{align}
u \otimes v &= u v^{\dagger}
\end{align}
$$

The mapping of outer product could be described as

$$
\otimes: \mathbb{C}^{m} \times \mathbb{C}^{n} \rightarrow \mathbb{C}^{m \times n}
$$

Tensor Product

Tensor product is essentially an general case of one dimensional array outer product. It is the outer product of two tensors, namely multidimensional tensors, that could have different dimensionality.

If $A$ is a $k$ dimensional tensor, $A \in \mathbb{C}^{ \prod_{i=0}^{k-1} m_i}$ and $B$ is a $k^{\prime}$ dimensional tensor, $B \in \mathbb{C}^{ \prod_{i=0}^{k^{\prime}-1} n_i}$, the tensor product $A \otimes B$ is a $k + k^{\prime}$ dimensional tensor that would have shape $A \otimes B \in \mathbb{C}^{ \prod_{i=0}^{k-1} m_i \prod_{i=0}^{k^{\prime}-1} n_i}$.

Kronecker Product

The outer product and Kronecker product are closely related. In fact the same symbol is commonly used to denote both operations.

If $u$ and $v$ are column vectors, i.e., $u = [u_0, u_1, \cdots, u_{m-1}]^{\top}$ and $v = [v_0, v_1, \cdots, v_{n-1}]^{\top}$, the Kronecker product could also be expressed as follows.

$$
\begin{align}
u \otimes_{\text{Kron}} v &=
\begin{bmatrix}
u_0 v \\
u_1 v \\
\vdots \\
u_{m-1} v\\
\end{bmatrix} \nonumber\\
&=
\begin{bmatrix}
u_0 v_0 \\
u_0 v_1 \\
\vdots \\
u_0 v_{n-1} \\
\vdots \\
u_{m-1} v_0 \\
u_{m-1} v_1 \\
\vdots \\
u_{m-1} v_{n-1} \\
\end{bmatrix} \nonumber\\
\end{align}
$$

Note that there is an implicit dimensional reduction process in the above expression.

The mapping of outer product could be described as

$$
\otimes: \mathbb{C}^{m \times 1} \times \mathbb{C}^{n \times 1} \rightarrow \mathbb{C}^{mn \times 1}
$$

More concretely, let $A \in \mathbb{C}^{m \times m^{\prime}}$ and $B \in \mathbb{C}^{n \times n^{\prime}}$. Then the Kronecker product of $A$ and $B$ is defined as the matrix

$$
\begin{align}
A \otimes_{\text{Kron}} B &=
\begin{bmatrix}
A_{0,0}B & A_{0,1}B & \cdots & A_{0,m^{\prime}-1}B \\
A_{1,0}B & A_{1,1}B & \cdots & A_{1,m^{\prime}-1}B \\
\vdots & \vdots & \ddots & \vdots \\
A_{m-1,0}B & A_{m-1,1}B & \cdots & A_{m-1,m^{\prime}-1}B \\
\end{bmatrix} \nonumber\\
\end{align}
$$

Almost Commutative

Kronecker product is not commutative, i.e., usually $A \otimes B \neq B \otimes A$. However, Kronecker product is almost commutative with some row and column exchanges in some dimensions. We define this as $A \otimes B \cong B \otimes A$.

Suppose we have $A \in \mathbb{C}^{m \times m^{\prime}}$ and $B \in \mathbb{C}^{n \times n^{\prime}}$, we have

$$
\begin{align}
& A \otimes B \\
&=
\begin{bmatrix}
A_{0,0}B & A_{0,1}B & \cdots & A_{0,m^{\prime}-1}B \\
A_{1,0}B & A_{1,1}B & \cdots & A_{1,m^{\prime}-1}B \\
\vdots & \vdots & \ddots & \vdots \\
A_{m-1,0}B & A_{m-1,1}B & \cdots & A_{m-1,m^{\prime}-1}B \\
\end{bmatrix} \nonumber\\
&=
\begin{bmatrix}
A_{0,0}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} & A_{0,1}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} & \cdots & A_{0,m^{\prime}-1}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} \\
A_{1,0}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} & A_{1,1}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} & \cdots & A_{1,m^{\prime}-1}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} \\
\vdots & \vdots & \ddots & \vdots \\
A_{m-1,0}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} & A_{m-1,1}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} & \cdots & A_{m-1,m^{\prime}-1}\begin{bmatrix} B_{:,0} & B_{:,1} & \cdots & B_{:,n^{\prime}-1} \end{bmatrix} \\
\end{bmatrix} \nonumber\\
&=
\begin{bmatrix}
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,0} &
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,n^{\prime}-1}
&
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,0} &
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,n^{\prime}-1}
&
\cdots
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,0} &
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,n^{\prime}-1}
\end{bmatrix} \nonumber\\
\end{align}
$$

We rearrange the columns of $A \otimes B$, we have

$$
\begin{align}
& A \otimes B \\
&=
\begin{bmatrix}
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,0} &
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,n^{\prime}-1}
&
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,0} &
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,n^{\prime}-1}
&
\cdots
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,0}
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,n^{\prime}-1}
\end{bmatrix} \nonumber\\
&\rightarrow
\begin{bmatrix}
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,0} &
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,0}
&
\cdots
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,0}
&
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,1} &
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,0} \\ A_{1,0} \\ \vdots \\ A_{m-1,0} \end{bmatrix} B_{:,n^{\prime}-1} &
\begin{bmatrix} A_{0,1} \\ A_{1,1} \\ \vdots \\ A_{m-1,1} \end{bmatrix} B_{:,n^{\prime}-1}
&
\cdots
&
\begin{bmatrix} A_{0,m^{\prime}-1} \\ A_{1,m^{\prime}-1} \\ \vdots \\ A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,n^{\prime}-1}
\end{bmatrix} \nonumber\\
&=
\begin{bmatrix}
\begin{bmatrix} A_{0,0} & A_{0,1} & \cdots & A_{0,m^{\prime}-1} \end{bmatrix} B_{:,0}
&
\begin{bmatrix} A_{0,0} & A_{0,1} & \cdots & A_{0,m^{\prime}-1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{0,0} & A_{0,1} & \cdots & A_{0,m^{\prime}-1} \end{bmatrix} B_{:,n^{\prime}-1} \\
\begin{bmatrix} A_{1,0} & A_{1,1} & \cdots & A_{1,m^{\prime}-1} \end{bmatrix} B_{:,0}
&
\begin{bmatrix} A_{1,0} & A_{1,1} & \cdots & A_{1,m^{\prime}-1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{1,0} & A_{1,1} & \cdots & A_{1,m^{\prime}-1} \end{bmatrix} B_{:,n^{\prime}-1} \\
\vdots & \vdots & \cdots & \vdots \\
\begin{bmatrix} A_{m-1,0} & A_{m-1,1} & \cdots & A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,0}
&
\begin{bmatrix} A_{m-1,0} & A_{m-1,1} & \cdots & A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,1}
&
\cdots
&
\begin{bmatrix} A_{m-1,0} & A_{m-1,1} & \cdots & A_{m-1,m^{\prime}-1} \end{bmatrix} B_{:,n^{\prime}-1} \\
\end{bmatrix} \nonumber\\
&=
\begin{bmatrix}
\begin{bmatrix} B_{0,0} \\ B_{1,0} \\ \vdots \\ B_{n-1,0} \end{bmatrix} A_{0,:}
&
\begin{bmatrix} B_{0,1} \\ B_{1,1} \\ \vdots \\ B_{n-1,1} \end{bmatrix} A_{0,:}
&
\cdots
&
\begin{bmatrix} B_{0,n^{\prime}} \\ B_{1,n^{\prime}} \\ \vdots \\ B_{n-1,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{0,0} \\ B_{1,0} \\ \vdots \\ B_{n-1,0} \end{bmatrix} A_{1,:}
&
\begin{bmatrix} B_{0,1} \\ B_{1,1} \\ \vdots \\ B_{n-1,1} \end{bmatrix} A_{1,:}
&
\cdots
&
\begin{bmatrix} B_{0,n^{\prime}} \\ B_{1,n^{\prime}} \\ \vdots \\ B_{n-1,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots & \vdots & \cdots & \vdots \\
\begin{bmatrix} B_{0,0} \\ B_{1,0} \\ \vdots \\ B_{n-1,0} \end{bmatrix} A_{m-1,:}
&
\begin{bmatrix} B_{0,1} \\ B_{1,1} \\ \vdots \\ B_{n-1,1} \end{bmatrix} A_{m-1,:}
&
\cdots
&
\begin{bmatrix} B_{0,n^{\prime}} \\ B_{1,n^{\prime}} \\ \vdots \\ B_{n-1,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\end{bmatrix} \nonumber\\
&=
\begin{bmatrix}
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots \\
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\end{bmatrix} \nonumber\\
\end{align}
$$

We further rearrange the rows of $A \otimes B$, we have

$$
\begin{align}
A \otimes B
&\rightarrow
\begin{bmatrix}
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots \\
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\end{bmatrix} \nonumber\\
&\rightarrow
\begin{bmatrix}
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots \\
\begin{bmatrix} B_{0,0} & B_{0,1} & \cdots & B_{0,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots \\
\begin{bmatrix} B_{1,0} & B_{1,1} & \cdots & B_{1,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{0,:} \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{1,:} \\
\vdots \\
\begin{bmatrix} B_{n-1,0} & B_{n-1,1} & \cdots & B_{n-1,n^{\prime}-1} \end{bmatrix} A_{m-1,:} \\
\end{bmatrix} \nonumber\\
&=
\begin{bmatrix}
B_{0,0} A & B_{0,1} A & \cdots & B_{0,n^{\prime}-1} A \\
B_{1,0} A & B_{1,1} A & \cdots & B_{1,n^{\prime}-1} A \\
\vdots & \vdots & \ddots & \vdots \\
B_{n-1,0} A & B_{n-1,1} A & \cdots & B_{n-1,n^{\prime}-1} A \\
\end{bmatrix} \nonumber\\
&= B \otimes A
\end{align}
$$

Therefore,

$$
A \otimes B \cong B \otimes A
$$

This means, there exist permutation matrices $P$ and $Q$ such that

$$
A \otimes B = P (B \otimes A) Q
$$

Miscellaneous

In Numpy, the tensor product could be computed using numpy.ufunc.outer, and the Kronecker product could be computed using numpy.kron.