Tiny VoltThe 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.
| Matrix | # rows | # cols |
|---|---|---|
1. Definition of Kronecker product
The Kronecker product of two matrices and is a matrix denoted by where each element is replaced by a block matrix .
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 with a row vector of length . The outer product has the shape . 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
Since is a matrix, you can view it as a vector by stacking its columns vertically. In other words, the norm of is the product of norms of and . 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 and 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 and , their product is where is the sum of diagonal of the product
For instance where is the sum of entries along the diagonal of the matrix :
The product of polynomials and .
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 . The insight lies in viewing a bilinear form as a dot product.
Given column vectors and and a matrix , the bilinear form can be seen as a dot product between and which is a vector formed by stacking columns of .
The bilinear form can be seen as a dot product .
3.1 Extending to products of the form
This idea can be extended to products of the form . We have:
This is useful when writing linear operators as matrix-vector products in Matrix calculus. Eg
where is the identity matrix of the appropriate shape. This gives us:
Similarly the Sylvester equation 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 of shape gives the desired output matrix.
