World Library  
Flag as Inappropriate
Email this Article

Kronecker product

Article Id: WHEBN0000712430
Reproduction Date:

Title: Kronecker product  
Author: World Heritage Encyclopedia
Language: English
Subject: Matrix multiplication, Leopold Kronecker, Bose–Mesner algebra, Haar wavelet, Sylvester equation
Collection: Matrix Theory
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Kronecker product

In mathematics, the Kronecker product, denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a generalization of the outer product (which is denoted by the same symbol) from vectors to matrices, and 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.

The Kronecker product is named after

  • Hazewinkel, Michiel, ed. (2001), "Tensor product",  
  • Kronecker product at PlanetMath.org.
  • MathWorld Kronecker 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.

External links

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

References

  1. ^ G. Zehfuss (1858), "Ueber eine gewisse Determinante", Zeitschrift für Mathematik und Physik 3: 298–301. 
  2. ^ H. V. Henderson and S. R. Searle (1980). "The vec-permutation matrix, the vec operator and Kronecker products: A review". LINEAR AND MULTILINEAR ALGEBRA 9 (4): 271–288.  
  3. ^ J. W. Brewer (1969). "A Note on Kronecker Matrix Products and Matrix Equation Systems". SIAM Journal on Applied Mathematics 17 (3): 603–606.  
  4. ^ Dummit, David S.; Foote, Richard M. (1999). Abstract Algebra (2 ed.). New York: John Wiley and Sons. pp. 401–402.  
  5. ^ See answer to Exercise 96, D. E. Knuth: "Pre-Fascicle 0a: Introduction to Combinatorial Algorithms", zeroth printing (revision 2), to appear as part of D.E. Knuth: The Art of Computer Programming Vol. 4A
  6. ^ Tracy, D. S.; Singh, R. P. (1972). "A New Matrix Product and Its Applications in Matrix Differentiation". Statistica Neerlandica 26 (4): 143–157.  
  7. ^ Liu, S. (1999). "Matrix Results on the Khatri–Rao and Tracy–Singh Products". Linear Algebra and its Applications 289 (1–3): 267–277.  
  8. ^ Khatri C. G.,  
  9. ^ Zhang X, Yang Z, Cao C. (2002), "Inequalities involving Khatri–Rao products of positive semi-definite matrices", Applied Mathematics E-notes 2: 117–124 

Notes

See also

\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].

so that:

\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] ,

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 m1 = m, p1 = p, n = q and for each j: nj = pj = 1. The resulting product is a mp × 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:

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).

\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].

in which the ij-th block is the mipi × njqj sized Kronecker product of the corresponding blocks of A and B, assuming the number of row and column partitions of both matrices is equal. The size of the product is then i mipi) × (Σj njqj). Proceeding with the same matrices as the previous example we obtain:

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

The Khatri–Rao product is defined as[8][9]

Khatri–Rao product

\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].

we get:

\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] ,

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

which means that the (ij)-th subblock of the mp × nq product AB is the mi p × nj q matrix AijB, of which the (k)-th subblock equals the mi pk × nj q matrix AijBk. Essentially the Tracy–Singh product is the pairwise Kronecker product for each pair of partitions in the two matrices.

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

The Tracy–Singh product is defined as[6][7]

Tracy–Singh product

Two related matrix operations are the Tracy–Singh and Khatri–Rao products which operate on partitioned matrices. Let the m × n matrix A be partitioned into the mi × nj blocks Aij and p × q matrix B into the pk × q blocks Bkl with of course Σi mi = m, Σj nj = n, Σk pk = p and Σ q = q.

Related matrix operations

For an example of the application of this formula, see the article on the Lyapunov equation. This formula also comes in handy in showing that the matrix normal distribution is a special case of the multivariate normal distribution.

Applications

If X is row-ordered into the column vector x then AXB can be also be written as (Jain 1989, 2.8 Block Matrices and Kronecker Products) (ABT)x.

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).

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

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

Matrix equations

  1. Spectrum: Suppose that A and B are square matrices of size n and m respectively. Let λ1, ..., λn be the eigenvalues of A and μ1, ..., μm be those of B (listed according to multiplicity). Then the eigenvalues of AB 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\text{and}\quad \det(\mathbf{A} \otimes \mathbf{B}) = (\det \mathbf{A})^m (\det \mathbf{B})^n.
  2. Singular values: If A and B are rectangular matrices, then one can consider their singular values. Suppose that A has rA 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 AB has rArB 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}.
  3. 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 {v1, ..., vm}, {w1, ..., wn}, {x1, ..., xd}, and {y1, ..., ye}, respectively, and if the matrices A and B represent the linear transformations S : VX and T : WY, respectively in the appropriate bases, then the matrix AB represents the tensor product of the two maps, ST : VWXY with respect to the basis {v1w1, v1w2, ..., v2w1, ..., vmwn} of VW and the similarly defined basis of XY with the property that AB(viwj) = (Avi) ⊗ (Bwj), where i and j are integers in the proper range.[4] When V and W are Lie algebras, and S : VV and T : WW are Lie algebra homomorphisms, the Kronecker sum of A and B represents the induced Lie algebra homomorphisms VWVW.
  4. 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.[5]

Abstract properties

  1. 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.
  2. Non-commutative: In general, AB and BA are different matrices. However, AB and BA are permutation equivalent, meaning that there exist permutation matrices P and Q (so called commutation matrices) such that[2]
    \mathbf{A} \otimes \mathbf{B} = \mathbf{P} \, (\mathbf{B} \otimes \mathbf{A}) \, \mathbf{Q}.
    If A and B are square matrices, then AB and BA are even permutation similar, meaning that we can take P = QT.
  3. The mixed-product property and the inverse of a Kronecker product: 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 AB is invertible if and only if both 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}.
  4. Transpose: Transposition and conjugate transposition are distributive over the Kronecker product:
    (\mathbf{A}\otimes \mathbf{B})^\mathrm{T} = \mathbf{A}^\mathrm{T} \otimes \mathbf{B}^\mathrm{T} and (\mathbf{A}\otimes \mathbf{B})^* = \mathbf{A}^* \otimes \mathbf{B}^*.
  5. Determinant: Let A be an n × n matrix and let B be an m × m matrix. Then
    \left| \mathbf{A} \otimes \mathbf{B} \right| = \left| \mathbf{A} \right| ^m \left| \mathbf{B} \right| ^n .
    The exponent in |A| is the order of B and the exponent in |B| is the order of A.
  6. Kronecker sum and exponentiation If A is n × n, B is m × m and Ik denotes the k × k identity matrix then we can define what is sometimes called the Kronecker sum, ⊕, 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 some numerical evaluations.[3]

    \exp({\mathbf{N} \oplus \mathbf{M}}) = \exp(\mathbf{N}) \otimes \exp(\mathbf{M})

    Kronecker sums appear naturally in physics when considering ensembles of non-interacting systems. Let Hi be the Hamiltonian of the ith such system. Then the total Hamiltonian of the ensemble is

    H_{\mathrm{Tot}}=\bigoplus_{i}H^{i}.

Relations to other matrix operations

Properties

\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}.

Examples

If A and B represent linear transformations V1W1 and V2W2, respectively, then AB represents the tensor product of the two maps, V1V2W1W2.

More compactly, we have (A\otimes B)_{p(r-1)+v, q(s-1)+w} = a_{rs} b_{vw}

{\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}.

more explicitly:

\mathbf{A}\otimes\mathbf{B} = \begin{bmatrix} a_{11} \mathbf{B} & \cdots & a_{1n}\mathbf{B} \\ \vdots & \ddots & \vdots \\ a_{m1} \mathbf{B} & \cdots & a_{mn} \mathbf{B} \end{bmatrix},

If A is an m × n matrix and B is a p × q matrix, then the Kronecker product AB is the mp × nq block matrix:

Definition

Contents

  • Definition 1
    • Examples 1.1
  • Properties 2
    • Relations to other matrix operations 2.1
    • Abstract properties 2.2
  • Matrix equations 3
    • Applications 3.1
  • Related matrix operations 4
    • Tracy–Singh product 4.1
    • Khatri–Rao product 4.2
  • See also 5
  • Notes 6
  • References 7
  • External links 8

[1]

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 



Copyright © World Library Foundation. All rights reserved. eBooks from Hawaii eBook Library are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.