Kronecker product

For the Kronecker product of representations of symmetric groups, see Kronecker coefficient.

In mathematics, the Kronecker product, denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It gives the matrix of the tensor product with respect to a standard choice of basis. The Kronecker product should not be confused with the usual matrix multiplication, which is an entirely different operation. It is named after German mathematician Leopold Kronecker.

Definition

If A is an m-by-n matrix and B is a p-by-q matrix, then the Kronecker product A ⊗ B is the mp-by-nq block matrix $\mathbf{A}\otimes\mathbf{B} = \begin{bmatrix} a_{11} B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1} B & \cdots & a_{mn} B \end{bmatrix}.$

More explicitly, we have

$\mathbf{A}\otimes\mathbf{B} = \begin{bmatrix} a_{11} b_{11} & a_{11} b_{12} & \cdots & a_{11} b_{1q} & \cdots & \cdots & a_{1n} b_{11} & a_{1n} b_{12} & \cdots & a_{1n} b_{1q} \\ a_{11} b_{21} & a_{11} b_{22} & \cdots & a_{11} b_{2q} & \cdots & \cdots & a_{1n} b_{21} & a_{1n} b_{22} & \cdots & a_{1n} b_{2q} \\ \vdots & \vdots & \ddots & \vdots & & & \vdots & \vdots & \ddots & \vdots \\ a_{11} b_{p1} & a_{11} b_{p2} & \cdots & a_{11} b_{pq} & \cdots & \cdots & a_{1n} b_{p1} & a_{1n} b_{p2} & \cdots & a_{1n} b_{pq} \\ \vdots & \vdots & & \vdots & \ddots & & \vdots & \vdots & & \vdots \\ \vdots & \vdots & & \vdots & & \ddots & \vdots & \vdots & & \vdots \\ a_{m1} b_{11} & a_{m1} b_{12} & \cdots & a_{m1} b_{1q} & \cdots & \cdots & a_{mn} b_{11} & a_{mn} b_{12} & \cdots & a_{mn} b_{1q} \\ a_{m1} b_{21} & a_{m1} b_{22} & \cdots & a_{m1} b_{2q} & \cdots & \cdots & a_{mn} b_{21} & a_{mn} b_{22} & \cdots & a_{mn} b_{2q} \\ \vdots & \vdots & \ddots & \vdots & & & \vdots & \vdots & \ddots & \vdots \\ a_{m1} b_{p1} & a_{m1} b_{p2} & \cdots & a_{m1} b_{pq} & \cdots & \cdots & a_{mn} b_{p1} & a_{mn} b_{p2} & \cdots & a_{mn} b_{pq} \end{bmatrix}.$

If A and B represent linear transformations V₁ → W₁ and V₂ → W₂, respectively, then A ⊗ B represents the tensor product of the two maps, V₁ ⊗ V₂ → W₁ ⊗ W₂.

Examples

$\begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} \otimes \begin{bmatrix} 0 & 5 \\ 6 & 7 \\ \end{bmatrix} = \begin{bmatrix} 1\cdot 0 & 1\cdot 5 & 2\cdot 0 & 2\cdot 5 \\ 1\cdot 6 & 1\cdot 7 & 2\cdot 6 & 2\cdot 7 \\ 3\cdot 0 & 3\cdot 5 & 4\cdot 0 & 4\cdot 5 \\ 3\cdot 6 & 3\cdot 7 & 4\cdot 6 & 4\cdot 7 \\ \end{bmatrix} = \begin{bmatrix} 0 & 5 & 0 & 10 \\ 6 & 7 & 12 & 14 \\ 0 & 15 & 0 & 20 \\ 18 & 21 & 24 & 28 \end{bmatrix}$.

Properties

Bilinearity and associativity

The Kronecker product is a special case of the tensor product, so it is bilinear and associative:

$\mathbf{A} \otimes (\mathbf{B}+\mathbf{C}) = \mathbf{A} \otimes \mathbf{B} + \mathbf{A} \otimes \mathbf{C},$

$(\mathbf{A}+\mathbf{B})\otimes \mathbf{C} = \mathbf{A} \otimes \mathbf{C} + \mathbf{B} \otimes \mathbf{C},$

$(k\mathbf{A}) \otimes \mathbf{B} = \mathbf{A} \otimes (k\mathbf{B}) = k(\mathbf{A} \otimes \mathbf{B}),$

$(\mathbf{A} \otimes \mathbf{B}) \otimes \mathbf{C} = \mathbf{A} \otimes (\mathbf{B} \otimes \mathbf{C}),$

where A, B and C are matrices and k is a scalar.

The Kronecker product is not commutative: in general, A $\,\otimes\,$ B and B $\,\otimes\,$ A are different matrices. However, A $\,\otimes\,$ B and B $\,\otimes\,$ A are permutation equivalent, meaning that there exist permutation matrices P and Q such that

$\mathbf{A} \otimes \mathbf{B} = \mathbf{P} \, (\mathbf{B} \otimes \mathbf{A}) \, \mathbf{Q}.$

If A and B are square matrices, then A $\,\otimes\,$ B and B $\,\otimes\,$ A are even permutation similar, meaning that we can take P = Q^T.

The mixed-product property

If A, B, C and D are matrices of such size that one can form the matrix products AC and BD, then

$(\mathbf{A} \otimes \mathbf{B})(\mathbf{C} \otimes \mathbf{D}) = \mathbf{AC} \otimes \mathbf{BD}.$

This is called the mixed-product property, because it mixes the ordinary matrix product and the Kronecker product. It follows that A $\,\otimes\,$ B is invertible if and only if A and B are invertible, in which case the inverse is given by

$(\mathbf{A} \otimes \mathbf{B})^{-1} = \mathbf{A}^{-1} \otimes \mathbf{B}^{-1}.$

Transpose

The operation of transposition is distributive over the Kronecker product:

$(\mathbf{A}\otimes \mathbf{B})^T = \mathbf{A}^T \otimes \mathbf{B}^T.$

Kronecker sum and exponentiation

If A is n-by-n, B is m-by-m and $\mathbf{I}_k$ denotes the k-by-k identity matrix then we can define what is sometimes called the Kronecker sum, $\oplus$, by

$\mathbf{A} \oplus \mathbf{B} = \mathbf{A} \otimes \mathbf{I}_m + \mathbf{I}_n \otimes \mathbf{B}.$

(Note that this is different from the direct sum of two matrices.) This operation is related to the tensor product on Lie algebras.

We have the following formula for the matrix exponential which is useful in the numerical evaluation of certain continuous-time Markov processes^{[citation needed]},

$e^{\mathbf{A} \oplus \mathbf{B}} = e^\mathbf{A} \otimes e^\mathbf{B}.$

Kronecker sums appear naturally in physics when considering ensembles of non-interacting systems. Let Hⁱ be the Hamiltonian of the i-th such system. Then the total Hamiltonian of the ensemble is $H_{\mathrm{Tot}}=\bigoplus_{i}H^{i}$.

Spectrum

Suppose that A and B are square matrices of size n and m respectively. Let λ₁, ..., λ_n be the eigenvalues of A and μ₁, ..., μ_m be those of B (listed according to multiplicity). Then the eigenvalues of A $\,\otimes\,$ B are

$\lambda_i \mu_j, \qquad i=1,\ldots,n ,\, j=1,\ldots,m.$

It follows that the trace and determinant of a Kronecker product are given by

$\operatorname{tr}(\mathbf{A} \otimes \mathbf{B}) = \operatorname{tr} \mathbf{A} \, \operatorname{tr} \mathbf{B} \quad\mbox{and}\quad \det(\mathbf{A} \otimes \mathbf{B}) = (\det \mathbf{A})^m (\det \mathbf{B})^n.$

Singular values

If A and B are rectangular matrices, then one can consider their singular values. Suppose that A has r_A nonzero singular values, namely

$\sigma_{\mathbf{A},i}, \qquad i = 1, \ldots, r_\mathbf{A}.$

Similarly, denote the nonzero singular values of B by

$\sigma_{\mathbf{B},i}, \qquad i = 1, \ldots, r_\mathbf{B}.$

Then the Kronecker product A $\,\otimes\,$ B has r_Ar_B nonzero singular values, namely

$\sigma_{\mathbf{A},i} \sigma_{\mathbf{B},j}, \qquad i=1,\ldots,r_\mathbf{A} ,\, j=1,\ldots,r_\mathbf{B}.$

Since the rank of a matrix equals the number of nonzero singular values, we find that

$\operatorname{rank}(\mathbf{A} \otimes \mathbf{B}) = \operatorname{rank} \mathbf{A} \, \operatorname{rank} \mathbf{B}.$

Relation to the abstract tensor product

The Kronecker product of matrices corresponds to the abstract tensor product of linear maps. Specifically, if the vector spaces V, W, X, and Y have bases {v₁, ... , v_m}, {w₁, ... , w_n}, {x₁, ... , x_d}, and {y₁, ... , y_e}, respectively, and if the matrices A and B represent the linear transformations S : V → X and T : W → Y, respectively in the appropriate bases, then the matrix A ⊗ B represents the tensor product of the two maps, S ⊗ T : V ⊗ W → X ⊗ Y with respect to the basis {v₁ ⊗ w₁, v₁ ⊗ w₂, ... , v₂ ⊗ w₁, ... , v_m ⊗ w_n} of V ⊗ W and the similarly defined basis of X ⊗ Y with the property that A ⊗ B(v_i ⊗ w_j) = (Av_i)⊗(Bw_j), where i and j are integers in the proper range.

When V and W are Lie algebras, and S : V → V and T : W → W are Lie algebra homomorphisms, the Kronecker sum of A and B represents the induced Lie algebra homomorphisms V ⊗ W → V ⊗ W.

Relation to products of graphs

The Kronecker product of the adjacency matrices of two graphs is the adjacency matrix of the tensor product graph. The Kronecker sum of the adjacency matrices of two graphs is the adjacency matrix of the Cartesian product graph. See, answer to Exercise 96.

Matrix equations

The Kronecker product can be used to get a convenient representation for some matrix equations. Consider for instance the equation AXB = C, where A, B and C are given matrices and the matrix X is the unknown. We can rewrite this equation as

$(\mathbf{B}^\top \otimes \mathbf{A}) \, \operatorname{vec}(\mathbf{X}) = \operatorname{vec}(\mathbf{AXB}) = \operatorname{vec}(\mathbf{C}).$

Here, vec(X) denotes the vectorization of the matrix X formed by stacking the columns of X into a single column vector. It now follows from the properties of the Kronecker product that the equation AXB = C has a unique solution if and only if A and B are nonsingular (Horn & Johnson 1991, Lemma 4.3.1).

If X is row-ordered into the column vector x then $\mathbf{AXB}$ can be also be written as $(\mathbf{A} \otimes \mathbf{B}^\top)\mathbf{x}$ (Jain 1989, 2.8 Block Matrices and Kronecker Products)

History

The Kronecker product is named after Leopold Kronecker, even though there is little evidence that he was the first to define and use it. Indeed, in the past the Kronecker product was sometimes called the Zehfuss matrix, after Johann Georg Zehfuss.

Related matrix operations

Two related matrix operations are the Tracy-Singh and Khatri-Rao products which operate on partitioned matrices. Let the m-by-n matrix A be partitioned into the m_i-by-n_j blocks $\mathbf{A}_{ij}$ and p-by-q matrix $\mathbf{B}$ into the p_k-by-q_l blocks B_kl with of course Σ_im_i = m, Σ_jn_j = n, Σ_kp_k = p and Σ_lq_l = q.

The Tracy-Singh product is defined as

$\mathbf{A} \circ \mathbf{B} = (\mathbf{A}_{ij}\circ \mathbf{B})_{ij} = ((\mathbf{A}_{ij} \otimes \mathbf{B}_{kl})_{kl})_{ij}$

which means that the (ij)th subblock of the mp-by-nq product $\mathbf{A}\circ \mathbf{B}$ is the m_ip-by-n_jq matrix $\mathbf{A}_{ij} \circ \mathbf{B}$, of which the (kl)th subblock equals the m_ip_k-by-n_jq_l matrix $\mathbf{A}_{ij} \otimes \mathbf{B}_{kl}$. Essentially the Tracy-Singh product is the pairwise Kronecker product for each pair of partitions in the two matrices.

For example, if A and B both are 2-by-2 partitioned matrices e.g.:

$\mathbf{A} = \left[ \begin{array} {c | c} \mathbf{A}_{11} & \mathbf{A}_{12} \\ \hline \mathbf{A}_{21} & \mathbf{A}_{22} \end{array} \right] = \left[ \begin{array} {c c | c} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \hline 7 & 8 & 9 \end{array} \right] ,\quad \mathbf{B} = \left[ \begin{array} {c | c} \mathbf{B}_{11} & \mathbf{B}_{12} \\ \hline \mathbf{B}_{21} & \mathbf{B}_{22} \end{array} \right] = \left[ \begin{array} {c | c c} 1 & 4 & 7 \\ \hline 2 & 5 & 8 \\ 3 & 6 & 9 \end{array} \right] ,$

we get:

$\mathbf{A} \circ \mathbf{B} = \left[ \begin{array} {c | c} \mathbf{A}_{11} \circ \mathbf{B} & \mathbf{A}_{12} \circ \mathbf{B} \\ \hline \mathbf{A}_{21} \circ \mathbf{B} & \mathbf{A}_{22} \circ \mathbf{B} \end{array} \right] = \left[ \begin{array} {c | c | c | c } \mathbf{A}_{11} \otimes \mathbf{B}_{11} & \mathbf{A}_{11} \otimes \mathbf{B}_{12} & \mathbf{A}_{12} \otimes \mathbf{B}_{11} & \mathbf{A}_{12} \otimes \mathbf{B}_{12} \\ \hline \mathbf{A}_{11} \otimes \mathbf{B}_{21} & \mathbf{A}_{11} \otimes \mathbf{B}_{22} & \mathbf{A}_{12} \otimes \mathbf{B}_{21} & \mathbf{A}_{12} \otimes \mathbf{B}_{22} \\ \hline \mathbf{A}_{21} \otimes \mathbf{B}_{11} & \mathbf{A}_{21} \otimes \mathbf{B}_{12} & \mathbf{A}_{22} \otimes \mathbf{B}_{11} & \mathbf{A}_{22} \otimes \mathbf{B}_{12} \\ \hline \mathbf{A}_{21} \otimes \mathbf{B}_{21} & \mathbf{A}_{21} \otimes \mathbf{B}_{22} & \mathbf{A}_{22} \otimes \mathbf{B}_{21} & \mathbf{A}_{22} \otimes \mathbf{B}_{22} \end{array} \right]$

$= \left[ \begin{array} {c c | c c c c | c | c c} 1 & 2 & 4 & 7 & 8 & 14 & 3 & 12 & 21 \\ 4 & 5 & 16 & 28 & 20 & 35 & 6 & 24 & 42 \\ \hline 2 & 4 & 5 & 8 & 10 & 16 & 6 & 15 & 24 \\ 3 & 6 & 6 & 9 & 12 & 18 & 9 & 18 & 27 \\ 8 & 10 & 20 & 32 & 25 & 40 & 12 & 30 & 48 \\ 12 & 15 & 24 & 36 & 30 & 45 & 18 & 36 & 54 \\ \hline 7 & 8 & 28 & 49 & 32 & 56 & 9 & 36 & 63 \\ \hline 14 & 16 & 35 & 56 & 40 & 64 & 18 & 45 & 72 \\ 21 & 24 & 42 & 63 & 48 & 72 & 27 & 54 & 81 \end{array} \right].$

The Khatri-Rao product is defined as

$\mathbf{A} \ast \mathbf{B} = (\mathbf{A}_{ij}\otimes \mathbf{B}_{ij})_{ij}$

in which the (ij)th block is the m_ip_i-by-n_jq_j sized Kronecker product of the corresponding blocks of $\mathbf{A}$ and $\mathbf{B}$, assuming the number of row and column partitions of both matrices is equal. The size of the product is then Σ_im_ip_i-by-Σ_jn_jq_j. Proceeding with the same matrices as the previous example we obtain:

$\mathbf{A} \ast \mathbf{B} = \left[ \begin{array} {c | c} \mathbf{A}_{11} \otimes \mathbf{B}_{11} & \mathbf{A}_{12} \otimes \mathbf{B}_{12} \\ \hline \mathbf{A}_{21} \otimes \mathbf{B}_{21} & \mathbf{A}_{22} \otimes \mathbf{B}_{22} \end{array} \right] = \left[ \begin{array} {c c | c c} 1 & 2 & 12 & 21 \\ 4 & 5 & 24 & 42 \\ \hline 14 & 16 & 45 & 72 \\ 21 & 24 & 54 & 81 \end{array} \right].$

This is a submatrix of the Tracy-Singh product of the two matrices (each partition in this example is a partition in a corner of the Tracy-Singh product).

A column-wise Kronecker product of two matrices may also be called the Khatri-Rao product. This product assumes the partitions of the matrices are their columns. In this case m₁ = m, p₁ = p, n = q and $\forall j: n_j=p_j=1$. The resulting product is a mp-by-n matrix of which each column is the Kronecker product of the corresponding columns of A and B. Using the matrices from the previous examples with the columns partitioned:

$\mathbf{C} = \left[ \begin{array} { c | c | c} \mathbf{C}_1 & \mathbf{C}_2 & \mathbf{C}_3 \end{array} \right] = \left[ \begin{array} {c | c | c} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} \right] ,\quad \mathbf{D} = \left[ \begin{array} { c | c | c } \mathbf{D}_1 & \mathbf{D}_2 & \mathbf{D}_3 \end{array} \right] = \left[ \begin{array} { c | c | c } 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{array} \right] ,$

so that:

$\mathbf{C} \ast \mathbf{D} = \left[ \begin{array} { c | c | c } \mathbf{C}_1 \otimes \mathbf{D}_1 & \mathbf{C}_2 \otimes \mathbf{D}_2 & \mathbf{C}_3 \otimes \mathbf{D}_3 \end{array} \right] = \left[ \begin{array} { c | c | c } 1 & 8 & 21 \\ 2 & 10 & 24 \\ 3 & 12 & 27 \\ 4 & 20 & 42 \\ 8 & 25 & 48 \\ 12 & 30 & 54 \\ 7 & 32 & 63 \\ 14 & 40 & 72 \\ 21 & 48 & 81 \end{array} \right].$

See also

• Matrix product

References

• Horn, Roger A.; Johnson, Charles R. (1991), Topics in Matrix Analysis, Cambridge University Press, ISBN 0-521-46713-6 .
• Jain, Anil K. (1989), Fundamentals of Digital Image Processing, Prentice Hall, ISBN 0-13-336165-9 .
• Steeb, Willi-Hans (1997), Matrix Calculus and Kronecker Product with Applications and C++ Programs, World Scientific Publishing, ISBN 9810232411 
• Steeb, Willi-Hans (2006), Problems and Solutions in Introductory and Advanced Matrix Calculus, World Scientific Publishing, ISBN 9812569162 

External links

• Kronecker product on PlanetMath
• MathWorld Matrix Direct Product
• New Kronecker product problems
• Earliest Uses: The entry on The Kronecker, Zehfuss or Direct Product of matrices has historical information.
• Generic C++ and Fortran 90 codes for calculating Kronecker products of two matrices.