Kronecker product

Kronecker product

In mathematics, the Kronecker product, denoted by otimes, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a special case of a tensor product. 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 otimes B is the "mp"-by-"nq" block matrix: A otimes B = egin{bmatrix} a_{11} B & cdots & a_{1n}B \ vdots & ddots & vdots \ a_{m1} B & cdots & a_{mn} B end{bmatrix}. More explicitly, we have: A otimes B = egin{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}.

Examples

: egin{bmatrix} 1 & 2 \ 3 & 4 \ end{bmatrix}otimes egin{bmatrix} 0 & 5 \ 6 & 7 \ end{bmatrix}= egin{bmatrix} 1cdot 0 & 1cdot 5 & 2cdot 0 & 2cdot 5 \ 1cdot 6 & 1cdot 7 & 2cdot 6 & 2cdot 7 \ 3cdot 0 & 3cdot 5 & 4cdot 0 & 4cdot 5 \ 3cdot 6 & 3cdot 7 & 4cdot 6 & 4cdot 7 \ end{bmatrix}

= egin{bmatrix} 0 & 5 & 0 & 10 \ 6 & 7 & 12 & 14 \ 0 & 15 & 0 & 20 \ 18 & 21 & 24 & 28 end{bmatrix}.

:egin{bmatrix}a_{11} & a_{12} \a_{21} & a_{22} \a_{31} & a_{32}end{bmatrix}otimesegin{bmatrix}b_{11} & b_{12} & b_{13} \b_{21} & b_{22} & b_{23}end{bmatrix}=egin{bmatrix}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} \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} \a_{31} b_{11} & a_{31} b_{12} & a_{31} b_{13} & a_{32} b_{11} & a_{32} b_{12} & a_{32} b_{13} \a_{31} b_{21} & a_{31} b_{22} & a_{31} b_{23} & a_{32} b_{21} & a_{32} b_{22} & a_{32} b_{23}end{bmatrix}.

Properties

Bilinearity and associativity

The Kronecker product is a special case of the tensor product, so it is bilinear and associative:: A otimes (B+C) = A otimes B + A otimes C, : (A+B)otimes C = A otimes C + B otimes C, : (kA) otimes B = A otimes (kB) = k(A otimes B), : (A otimes B) otimes C = A otimes (B otimes 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: A otimes B = P , (B otimes A) , 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: (A otimes B)(C otimes D) = AC otimes 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: (A otimes B)^{-1} = A^{-1} otimes B^{-1}.

Kronecker sum and exponentiation

If "A" is "n"-by-"n", "B" is "m"-by-"m" and I_k denotes the "k"-by-"k" identity matrix then we can define the Kronecker sum, oplus, by: A oplus B = A otimes I_m + I_n otimes B. We have the following formula for the matrix exponential which is useful in the numerical evaluation of certain continuous-time Markov processes Fact|date=January 2008, : e^{A oplus B} = e^A otimes e^B.

Spectrum

Suppose that "A" and "B" are square matrices of size "n" and "q" respectively. Let λ1, ..., λ"n" be the eigenvalues of "A" and μ1, ..., μ"q" 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,q. It follows that the trace and determinant of a Kronecker product are given by: operatorname{tr}(A otimes B) = operatorname{tr} A , operatorname{tr} B quadmbox{and}quad det(A otimes B) = (det A)^q (det 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_{A,i}, qquad i = 1, ldots, r_A. Similarly, denote the nonzero singular values of "B" by: sigma_{B,i}, qquad i = 1, ldots, r_B. Then the Kronecker product "A" otimes "B" has "r""A""r""B" nonzero singular values, namely: sigma_{A,i} sigma_{B,j}, qquad i=1,ldots,r_A ,, j=1,ldots,r_B. Since the rank of a matrix equals the number of nonzero singular values, we find that: operatorname{rank}(A otimes B) = operatorname{rank} A , operatorname{rank} 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 {v1, ... , vm}, {w1, ... , wn}, {x1, ... , xd}, and {y1, ... , ye}, 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 {v1 ⊗ w1, v1 ⊗ w2, ... , v2 ⊗ w1, ... , vm ⊗ wn} of "V" ⊗ "W" and the similarly defined basis of "X" ⊗ "Y". [Pages 401-402 of Citation
last=Dummit
first=David S.
last2=Foote
first2=Richard M.
title=Abstract Algebra
edition=2
year=1999
publisher=John Wiley and Sons, Inc.
place=New York
isbn=0-471-36857-1
]

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 D. E. Knuth: " [http://www-cs-faculty.stanford.edu/~knuth/fasc0a.ps.gz "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"] , answer to Exercise 96.

Transpose

The operation of transposition is distributive over the Kronecker product::(Aotimes B)^T = A^T otimes B^T.

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: (B^ op otimes A) , operatorname{vec}(X) = operatorname{vec}(AXB) = operatorname{vec}(C). 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 harv|Horn|Johnson|1991|loc=Lemma 4.3.1.

Here, vec("X") denotes the vectorization of the matrix "X" formed by stacking the columns of "X" into a single column vector.

If "X" is row-ordered into the column vector "x" then AXB can be also be written as (A otimes B^ op)x harv|Jain|1989|loc=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 Anchor|Tracy-Singh and Khatri-Rao products

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 A_{ij} and p-by-q matrix B into the p_k-by-q_l blocks "B""kl" with of course Sigma_i m_i = m, Sigma_j n_j = n, Sigma_k p_k = p and Sigma_l q_l = q .

The Tracy-Singh product [Tracy, DS, Singh RP. 1972. A new matrix product and its applications in matrix differentiation. Statistica Neerlandica 26: 143-157.] [Liu S. 1999. Matrix results on the Khatri-Rao and Tracy-Singh products. Linear Algebra and its Applications 289: 267-277. ( [http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B6V0R-3YVMNR9-R-1&_cdi=5653&_user=877992&_orig=na&_coverDate=03%2F01%2F1999&_sk=997109998&view=c&wchp=dGLbVlb-zSkWb&md5=21c8c66f17da8d1bab45304a29cc96ac&ie=/sdarticle.pdf pdf] )] is defined as : A circ B = (A_{ij}circ B)_{ij} = ((A_{ij} otimes B_{kl})_{kl})_{ij} which means that the (ij)th subblock of the mp-by-nq product Acirc B is the m_i p-by-n_j q matrix A_{ij} circ B, of which the (kl)th subblock equals the m_i p_k-by-n_j q_l matrix A_{ij} otimes 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.:: A = left [egin{array} {c | c}A_{11} & A_{12} \hlineA_{21} & A_{22}end{array} ight] = left [egin{array} {c c | c}1 & 2 & 3 \4 & 5 & 6 \hline7 & 8 & 9 end{array} ight] ,quadB = left [egin{array} {c | c}B_{11} & B_{12} \hlineB_{21} & B_{22}end{array} ight] = left [egin{array} {c | c c}1 & 4 & 7 \hline2 & 5 & 8 \3 & 6 & 9 end{array} ight] ,we get::A circ B = left [egin{array} {c | c}A_{11} circ B & A_{12} circ B \hlineA_{21} circ B & A_{22} circ B end{array} ight] =left [egin{array} {c | c | c | c }A_{11} otimes B_{11} & A_{11} otimes B_{12} & A_{12} otimes B_{11} & A_{12} otimes B_{12} \hlineA_{11} otimes B_{21} & A_{11} otimes B_{22} & A_{12} otimes B_{21} & A_{12} otimes B_{22} \hlineA_{21} otimes B_{11} & A_{21} otimes B_{12} & A_{22} otimes B_{11} & A_{22} otimes B_{12} \hlineA_{21} otimes B_{21} & A_{21} otimes B_{22} & A_{22} otimes B_{21} & A_{22} otimes B_{22}end{array} ight] :=left [egin{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 \hline2 & 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 \hline7 & 8 & 28 & 49 & 32 & 56 & 9 & 36 & 63 \hline14 & 16 & 35 & 56 & 40 & 64 & 18 & 45 & 72 \21 & 24 & 42 & 63 & 48 & 72 & 27 & 54 & 81end{array} ight] .

The Khatri-Rao product [Cite journal
author = Khatri C. G., C. R. Rao
year = 1968
title = Solutions to some functional equations and their applications to characterization of probability distributions
journal = Sankhya
volume = 30
pages = 167-180
url = http://sankhya.isical.ac.in/search/30a2/30a2019.html
] [Cite journal
author = Zhang X, Yang Z, Cao C.
year = 2002
title = Inequalities involving Khatri-Rao products of positive semi-definite matrices
journal = Applied Mathematics E-notes
volume ) 2
pages = 117-124
] is defined as: A ast B = (A_{ij}otimes 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 A and B, assuming the number of row and column partitions of both matrices is equal. The size of the product is then Sigma_i m_ip_i-by-Sigma_j n_jq_j. Proceeding with the same matrices as the previous example we obtain::A ast B = left [egin{array} {c | c}A_{11} otimes B_{11} & A_{12} otimes B_{12} \hlineA_{21} otimes B_{21} & A_{22} otimes B_{22} end{array} ight] =left [egin{array} {c c | c c}1 & 2 & 12 & 21 \4 & 5 & 24 & 42 \hline14 & 16 & 45 & 72 \21 & 24 & 54 & 81end{array} ight] .

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_1=m, p_1=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::C = left [egin{array} { c | c | c}C_1 & C_2 & C_3end{array} ight] = left [egin{array} {c | c | c}1 & 2 & 3 \4 & 5 & 6 \7 & 8 & 9 end{array} ight] ,quadD = left [egin{array} { c | c | c }D_1 & D_2 & D_3end{array} ight] = left [egin{array} { c | c | c }1 & 4 & 7 \2 & 5 & 8 \3 & 6 & 9 end{array} ight] ,so that::C ast D = left [egin{array} { c | c | c }C_1 otimes D_1 & C_2 otimes D_2 & C_3 otimes D_3end{array} ight] =left [egin{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 & 81end{array} ight] .

References

*.

*citation | first1=Anil K. | last1=Jain | year = 1989 | title=Fundamentals of Digital Image Processing | publisher= Prentice Hall | isbn=0-13-336165-9.

External links

*
* [http://mathworld.wolfram.com/MatrixDirectProduct.html MathWorld Matrix Direct Product]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Kronecker product — noun The ⊗ operation (the tensor product) when applied to two matrices …   Wiktionary

  • Kronecker-Produkt — Das Kronecker Produkt (nach Leopold Kronecker) ist ein Begriff aus der Matrizenrechnung. Inhaltsverzeichnis 1 Definition 2 1. Beispiel 3 2. Beispiel 4 Eigenschaften …   Deutsch Wikipedia

  • Product (mathematics) — In mathematics, a product is the result of multiplying, or an expression that identifies factors to be multiplied. The order in which real or complex numbers are multiplied has no bearing on the product; this is known as the commutative law of… …   Wikipedia

  • Kronecker delta — In mathematics, the Kronecker delta or Kronecker s delta, named after Leopold Kronecker (1823 1891), is a function of two variables, usually integers, which is 1 if they are equal, and 0 otherwise. So, for example, delta {12} = 0, but delta {33} …   Wikipedia

  • Kronecker's sigma function — Let D be the domain of the Cartesian product X times X, for a set X, then the Kronecker s sigma function with respect to X is a function from D to the set {0,1} such that it is equal to the characteristic function on D.ee also*Sigma function …   Wikipedia

  • Tensor product — In mathematics, the tensor product, denoted by otimes, may be applied in different contexts to vectors, matrices, tensors, vector spaces, algebras, topological vector spaces, and modules. In each case the significance of the symbol is the same:… …   Wikipedia

  • Leopold Kronecker — Infobox Scientist name = Leopold Kronecker caption = Leopold Kronecker birth date = birth date|1823|12|7|mf=y birth place = Liegnitz, Prussian province of Silesia residence = Prussian nationality = Prussian death date = death date and… …   Wikipedia

  • Tensor product of graphs — In graph theory, the tensor product G × H of graphs G and H is a graph such that * the vertex set of G × H is the Cartesian product V(G) × V(H) ; and * any two vertices (u,u ) and (v,v ) are adjacent in G × H if and only if u is adjacent with v… …   Wikipedia

  • Dyadic product — In mathematics, in particular multilinear algebra, the dyadic product of two vectors, and , each having the same dimension, is the tensor product of the vectors and results in a tensor of order two and rank one. It is also called outer product.… …   Wikipedia

  • Outer product — For outer product in geometric algebra, see exterior product. In linear algebra, the outer product typically refers to the tensor product of two vectors. The result of applying the outer product to a pair of vectors is a matrix. The name… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”