What is the Kronecker Product?

The Kronecker product of two matrices $A\in\mathbb{C}^{m\times n}$ and $B\in\mathbb{C}^{p\times q}$ (also called the tensor product) is the $mp\times nq$ matrix¹

$A \otimes B = \begin{bmatrix} a_{11}B & a_{12}B & \dots & a_{1n}B \\ a_{21}B & a_{22}B & \dots & a_{2n}B \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & \dots & a_{mn}B \end{bmatrix}.$

In other words, $A\otimes B$ is the block $m\times n$ matrix with $(i,j)$ block $a_{ij}B$ . For example,

$\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix} \otimes \begin{bmatrix} b_{11} & b_{12} & b_{13} \\ b_{21} & b_{22} & b_{23} \end{bmatrix} = \left[\begin{array}{ccc|ccc} a_{11}b_{11} & a_{11}b_{12} & a_{11}b_{13} & a_{12}b_{11} & a_{12}b_{12} & a_{12}b_{13} \\ a_{11}b_{21} & a_{11}b_{22} & a_{11}b_{23} & a_{12}b_{21} & a_{12}b_{22} & a_{12}b_{23} \\\hline a_{21}b_{11} & a_{21}b_{12} & a_{21}b_{13} & a_{22}b_{11} & a_{22}b_{12} & a_{22}b_{13} \\ a_{21}b_{21} & a_{21}b_{22} & a_{21}b_{23} & a_{22}b_{21} & a_{22}b_{22} & a_{22}b_{23} \end{array}\right].$

Notice that the entries of $A\otimes B$ comprise every possible product $a_{ij}b_{rs}$ , which is not the case for the usual matrix product $AB$ when it is defined. Indeed if $A$ and $B$ are $n\times n$ then

$AB$ is $n\times n$ and contains sums of $n^3$ of the products $a_{ij}b_{rs}$ ,
$A\otimes B$ is $n^2\times n^2$ and contains all $n^4$ products $a_{ij}b_{rs}$ .

Two key properties of the Kronecker product are

$\begin{aligned} (A\otimes B)^* &= A^* \otimes B^*, \label{KP1} \\ (A\otimes B)(C\otimes D)&= AC \otimes BD. \label{KP2} \end{aligned}$

The second equality implies that when $x_i$ is an eigenvector of $A\in\mathbb{C}^{m\times m}$ with eigenvalue $\lambda_i$ and $y_j$ is an eigenvector of $B\in\mathbb{C}^{n\times n}$ with eigenvalue $\mu_j$ then

$(A\otimes B)(x_i\otimes y_j) = (Ax_i \otimes By_j) = (\lambda_i x_i \otimes \mu_j y_j) = \lambda_i\mu_j ( x_i \otimes y_j),$

so that $\lambda_i\mu_j$ is an eigenvalue of $A\otimes B$ with eigenvector $x_i \otimes y_j$ . In fact, the $mn$ eigenvalues of $A\otimes B$ are precisely $\lambda_i\mu_j$ for $i = 1\colon m$ and $j = 1\colon n$ .

Kronecker product structure arises in image deblurring models in which the blur is separable, that is, the blur in the horizontal direction can be separated from the blur in the vertical direction. Kronecker products also arise in the construction of Hadamard matrices. Recall that a Hadamard matrix is a matrix of $\pm1$ s whose rows and columns are mutually orthogonal. If $H_n$ is an $n\times n$ Hadamard matrix then

$\begin{bmatrix} \phantom{-} 1 & 1 \\ -1 & 1 \end{bmatrix} \otimes H_n = \begin{bmatrix} \phantom{-} H_n & H_n \\ -H_n & H_n \end{bmatrix}$

is a $2n\times 2n$ Hadamard matrix.

The practical significance of Kronecker product structure is that it allows computations on a large matrix to be reduced to computations on smaller matrices. For example, suppose $A$ and $B$ are Hermitian positive definite matrices and $C = A \otimes B$ , which can be shown to be Hermitian positive definite from the properties mentioned above. If $A = R^*R$ and $B = S^*S$ are Cholesky factorizations then

$A \otimes B = (R^*R) \otimes (S^*S) = (R^*\otimes S^*) (R \otimes S) = (R \otimes S)^* (R \otimes S),$

so $R\otimes S$ , which is easily seen to be triangular with positive diagonal elements, is the Cholesky factor of $A\otimes B$ . If $A$ and $B$ are $n\times n$ then forming $A\otimes B$ and computing its Cholesky factorization costs $O(n^6)$ flops, whereas $R$ and $S$ can be computed in $O(n^3)$ flops. If we want to solve a linear system $(A \otimes B)x = b$ this can be done using $R$ and $S$ without explicitly form $R\otimes S$ .

Vec Operator

The vec operator stacks the columns of a matrix into one long vector: if $A = [a_1,a_2,\dots,a_m]$ then $\mathrm{vec}(A) = [a_1^T a_2^T \dots a_m^T]^T$ . The vec operator and the Kronecker product interact nicely: for any $A$ , $X$ , and $B$ for which the product $AXB$ is defined,

$\mathrm{vec}(AXB) = (B^T \otimes A) \mathrm{vec}(X).$

This relation allows us to express a linear system $AXB = C$ in the usual form “ $Ax=b$ ”.

Kronecker Sum

The Kronecker sum of $A\in\mathbb{C}^{m\times m}$ and $B\in\mathbb{C}^{n\times n}$ is defined by $A\oplus B = A \otimes I_n + I_m \otimes B$ . The eigenvalues of $A\oplus B$ are $\lambda_{ij} = \lambda_i(A) + \lambda_j(B)$ , $i=1\colon m$ , $j=1\colon n$ , where the $\lambda_i(A)$ are the eigenvalues of $A$ and the $\lambda_j(B)$ are those of $B$ .

The Kronecker sum arises when we apply the vec operator to the matrix $AX + XB$ :

$\mathrm{vec}(AX + XB) = (I_m \otimes A + B^T \otimes I_n) \mathrm{vec}(X) = (B^T \oplus A) \mathrm{vec}(X).$

Kronecker sum structure also arises in finite difference discretizations of partial differential equations, such as when Poisson’s equation is discretized on a square by the usual five-point operator.

Vec-Permutation Matrix

Since for $A\in\mathbb{C}^{m\times n}$ the vectors $\mathrm{vec}(A)$ and $\mathrm{vec}(A^T)$ contain the same $mn$ elements in different orders, we must have

$\mathrm{vec}(A^T) = \Pi_{m,n} \mathrm{vec}(A),$

for some $mn\times mn$ permutation matrix $\Pi_{m,n}$ . This matrix is called the the vec-permutation matrix, and is also known as the commutation matrix.

Kronecker multiplication is not commutative, that is, $A \otimes B \ne B \otimes A$ in general, but $A \otimes B$ and $B \otimes A$ do contain the same elements in different orders. In fact, the two matrices are related by row and column permutations: if $A\in\mathbb{C}^{m\times n}$ and $B\in\mathbb{C}^{p\times q}$ then

$(A\otimes B)\Pi_{n,q} = \Pi_{m,p} (B\otimes A).$

This relation can be obtained as follows: for $X\in\mathbb{C}^{n\times q}$ ,

$\begin{aligned} (B \otimes A)\mathrm{vec}(X) &= \mathrm{vec}(AXB^T)\\ &= \Pi_{p,m} \mathrm{vec}(BX^TA^T)\\ &= \Pi_{p,m} (A\otimes B)\mathrm{vec}(X^T)\\ &= \Pi_{p,m} (A\otimes B) \Pi_{n,q}\mathrm{vec}(X). \end{aligned}$

Since these equalities hold for all $X$ , we have $B\otimes A = \Pi_{p,m} (A\otimes B) \Pi_{n,q}$ , from which the relation follows on using $\Pi_{m,n}\Pi_{n,m} = I$ , which can be obtained by replacing $A$ by $A^T$ in the definition of vec.

An explicit expression for the the vec-permutation matrix is

$\Pi_{m,n} = \displaystyle\sum_{i=1}^m \sum_{j=1}^n (e_i^{} e_j^T) \otimes (e_j^{} e_i^T),$

where $e_i$ is the $i$ th unit vector.

The following plot shows the sparsity patterns of all the vec permutation matrices $\Pi_{m,n}$ with $mn = 120$ , where the title of each subplot is $(m,n)$ .

MATLAB

In MATLAB the Kronecker product $A\otimes B$ can be computed as kron(A,B) and $\mathrm{vec}(A)$ is obtained by indexing with a colon: A(:). Be careful using kron as it can generate very large matrices!

Historical Note

The Kronecker product is named after Leopold Kronecker (1823–1891). Henderson et al. (1983) suggest that it should be called the Zehfuss product, after Johann Georg Zehfuss (1832–1891), who obtained the result $\det(A\otimes B) = \det(A)^n \det(B)^m$ for $A\in\mathbb{C}^{m\times m}$ and $B\in\mathbb{C}^{n\times n}$ in 1858.

References

This is a minimal set of references, which contain further useful references within.

Per Christian Hansen, James G. Nagy, and Dianne P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2006.
Harold V. Henderson, Friedrich Pukelsheim, and Shayle R. Searle, On the History of the Kronecker Product, Linear and Multilinear Algebra 14(2), 113–120, 1983.
Harold V. Henderson and Shayle R. Searle, The Vec-Permutation Matrix, the Vec Operator and Kronecker Products: A Review, Linear and Multilinear Algebra 9, 271–288, 1981. Note: the definition of $\Pi_{m,n}$ gives the transpose of $\Pi_{m,n}$ as we have defined it.
Jan R. Magnus and Heinz Neudecker, The Commutation Matrix: Some Properties and Applications, Ann. Statist. 7, 381–394, 1979
Roger Horn and Charles Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991. Chapter 4.
Charles F. Van Loan, The Ubiquitous Kronecker Product, J. Comput. Appl. Math. 123(1–2), 85–100, 2000.

Footnotes:

The $\otimes$ symbol is typed in $\LaTeX$ as \otimes.

One thought on “What is the Kronecker Product?”

José-Javier Martínez says:

August 27, 2020 at 4:26 pm

Dear Professor Higham,
I would like to add a classical source of the Kronecker product of two matrices, briefly commented in the paper by Van Loan: bivariate polynomial interpolation. In fact, in a natural way a “generalized Kronecker product” arises.
See, for instance, a recent recall of these facts in our paper “Accurate polynomial interpolation by using the Bernstein basis” (Numerical Algorithms, 2017):

https://link.springer.com/article/10.1007/s11075-016-0215-7

Thank you very much for your work.

What is the Kronecker Product?

Vec Operator

Kronecker Sum

Vec-Permutation Matrix

MATLAB

Historical Note

References

Related Blog Posts

Footnotes:

One thought on “What is the Kronecker Product?”

Leave a Reply Cancel reply

Vec Operator

Kronecker Sum

Vec-Permutation Matrix

MATLAB

Historical Note

References

Related Blog Posts

Footnotes:

Share this:

Related

One thought on “What is the Kronecker Product?”

Leave a Reply Cancel reply