The Kronecker Product Visualized

The Kronecker product takes two matrices and produces a larger block matrix. This article visualizes the operation and explores some of its lesser-known properties.

1. Definition of Kronecker product

The Kronecker product of two matrices $A \in R^{r_A \times c_A}$ and $B \in R^{\textcolor{#b45309}{r_B} \times \textcolor{#b45309}{c_B}}$ is a matrix denoted by $A \otimes B \in R^{r_A\textcolor{#b45309}{r_B} \times c_A\textcolor{#b45309}{c_B}}$ where each element $a_{ij}$ is replaced by a block matrix $a_{ij} * B$.

Kronecker product can be seen as replacing each element c of the left matrix with the right matrix scaled by the value c.

An example is shown below:

2. Kronecker product of two vectors

Perhaps the most common Kronecker product of two vectors is the outer product - this is the product of a column vector of length $m$ with a row vector of length $n$. The outer product has the shape $(m,n)$. Kronecker product of two column vectors is a column vector whose length is the product of individual column vectors. Similarly the Kronecker product of two row vectors is a row vector.

2.1 Some lesser known properties of Kronecker product of two vectors

2.1.1 Kronecker product of two unit vectors is a unit vector

$$||u \otimes v||^2 = ||u||^2||v||^2$$

Since $u \otimes v$ is a matrix, you can view it as a vector by stacking its columns vertically. In other words, the norm of $u \otimes v$ is the product of norms of $u$ and $v$. Note that this is true even for products of matrices - you just need to view the matrix as a vector.

2.1.2 Kronecker product of two probability distributions is a probability distribution

If $u$ and $v$ are two (independent) probability distributions, their Kronecker product (viewed as a vector) is a (joint) probability distribution. More generally, Kronecker product of two stochastic matrices is itself a stochastic matrix. If these input matrices have steady states, the steady state of the output matrix is the Kronecker product of the steady states of the input matrices.

2.1.3 Connection with products of two polynomials

Given two polynomials $p(x) = p_0 + p_1x + ... + p_mx^m$ and $q(x) = q_0 + q_1x + ... + q_nx^n$, their product is $p(x)q(x) = s_0 + s_1x + ... + s_{m+n}x^{m+n}$ where $s_i$ is the sum of $i\text{-th}$ diagonal of the product

For instance $(a + bx + cx^2)(p + qx + rx^2 + sx^3) = s_0 + s_1x + s_2x^2 + s_3x^3 + s_4x^4 + s_5x^5$ where $s_i$ is the sum of entries along the $i\text{-th}$ diagonal of the matrix $\begin{bmatrix} a \\ b \\ c \end{bmatrix} \otimes \begin{bmatrix} p & q & r & s \end{bmatrix}$:

The product of polynomials $a + bx + cx^2$ and $p + qx + rx^2 + sx^3$.

3. Bilinear form and Kronecker product: the most important takeaway

Note that we need to view a matrix as a vector (conventionally formed by stacking columns vertically) in order to interpret some properties of this product. This change in view is actually very helpful in solving equations of the form $AX + XB = C$. The insight lies in viewing a bilinear form as a dot product.

Given column vectors $b$ and $c$ and a matrix $M$, the bilinear form $c^TMb$ can be seen as a dot product between $b \otimes c$ and $vec(M)$ which is a vector formed by stacking columns of $M$.

The bilinear form $c^TMb$ can be seen as a dot product $(b^T \otimes c^T) \cdot vec(M) = (b \otimes c)^T \cdot vec(M)$.

3.1 Extending to products of the form $CXB^T$

This idea can be extended to products of the form $CMB^T$. We have:

This is useful when writing linear operators as matrix-vector products in Matrix calculus. Eg

where $I$ is the identity matrix of the appropriate shape. This gives us:

Similarly the Sylvester equation $AX + XB = C$ can be solved like so:

4. Kronecker product preserves many properties of the matrices

It was mentioned earlier that if the input matrices are stochastic, their Kronecker product is also stochastic. Similarly, if the input matrices have a norm of 1, so does their Kronecker product. Similarly, if the input matrices are permutation matrices, their Kronecker product is also a permutation matrix. If the input matrices are unitary, so is their Kronecker product. For a complete list, check out the Wikipedia article.

5. An unconventional application of Kronecker product

A while ago I came across a small but amusing problem - how to visualize the attention value of each image patch. To provide some context, a Vision Transformer (ViT) divides an image into non-overlapping patches. For example, an image of dimensions 224x224 is divided into 7x7 patches, each patch of dimension 32x32. Each patch is then converted into a vector and fed to transformer layers. We can extract the attention values from the last transformer layer. These attention values (each value is between 0 and 1) form a 7x7 grid, with each value corresponding to a 32x32 patch in the image. We can overlay these values on top of an image by multiplying each patch with the corresponding value. An example is shown below.

An image is divided into 7x7 patches. Each patch is assigned a probability by the attention layer.

The Kronecker product of the 7x7 attention matrix with a matrix of 1s of shape 32x32 gives the desired matrix which, when multiplied elementwise to the input image, gives the final overlaid image.

The Kronecker product of the attention values with a ones matrix $[1]$ of shape $(32,32)$ gives the desired output matrix.

Related articles:

• Three interpretations of matrix products visualized