Kronecker product
Encyclopedia
In mathematics, the Kronecker product, denoted by ⊗, is an operation on two matrices
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 of arbitrary size resulting in a block matrix
Block matrix
In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a matrix broken into sections called blocks. Looking at it another way, the matrix is written in terms of smaller matrices. We group the rows and columns into adjacent 'bunches'. A partition is the rectangle...

. It gives the matrix of the tensor product
Tensor product
In mathematics, the tensor product, denoted by ⊗, may be applied in different contexts to vectors, matrices, tensors, vector spaces, algebras, topological vector spaces, and modules, among many other structures or objects. In each case the significance of the symbol is the same: the most general...

 with respect to a standard choice of basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...

. The Kronecker product should not be confused with the usual matrix multiplication
Matrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...

, which is an entirely different operation. It is named after German mathematician Leopold Kronecker
Leopold Kronecker
Leopold Kronecker was a German mathematician who worked on number theory and algebra.He criticized Cantor's work on set theory, and was quoted by as having said, "God made integers; all else is the work of man"...

.

Definition

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


More explicitly, we have



If A and B represent linear transformations V1W1 and V2W2, respectively, then AB represents the tensor product
Tensor product
In mathematics, the tensor product, denoted by ⊗, may be applied in different contexts to vectors, matrices, tensors, vector spaces, algebras, topological vector spaces, and modules, among many other structures or objects. In each case the significance of the symbol is the same: the most general...

 of the two maps, V1V2W1W2.

Examples

.

Bilinearity and associativity

The Kronecker product is a special case of the tensor product
Tensor product
In mathematics, the tensor product, denoted by ⊗, may be applied in different contexts to vectors, matrices, tensors, vector spaces, algebras, topological vector spaces, and modules, among many other structures or objects. In each case the significance of the symbol is the same: the most general...

, so it is bilinear
Bilinear operator
In mathematics, a bilinear operator is a function combining elements of two vector spaces to yield an element of a third vector space that is linear in each of its arguments. Matrix multiplication is an example.-Definition:...

 and associative
Associativity
In mathematics, associativity is a property of some binary operations. It means that, within an expression containing two or more occurrences in a row of the same associative operator, the order in which the operations are performed does not matter as long as the sequence of the operands is not...

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

The Kronecker product is not commutative: in general, A B and B A are different matrices. However, A B and B A are permutation equivalent, meaning that there exist permutation matrices
Permutation matrix
In mathematics, in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere...

 P and Q such that
If A and B are square matrices, then A B and B A are even permutation similar, meaning that we can take P = QT.

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
This is called the mixed-product property, because it mixes the ordinary matrix product and the Kronecker product. It follows that A B is invertible if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

 A and B are invertible, in which case the inverse is given by

Transpose

The operation of transposition is distributive over the Kronecker product:

Kronecker sum and exponentiation

If A is n-by-n, B is m-by-m and denotes the k-by-k identity matrix then we can define what is sometimes called the Kronecker sum, , by
(Note that this is different from the direct sum of two matrices.) This operation is related to the tensor product on Lie algebra
Lie algebra
In mathematics, a Lie algebra is an algebraic structure whose main use is in studying geometric objects such as Lie groups and differentiable manifolds. Lie algebras were introduced to study the concept of infinitesimal transformations. The term "Lie algebra" was introduced by Hermann Weyl in the...

s.

We have the following formula for the matrix exponential
Matrix exponential
In mathematics, the matrix exponential is a matrix function on square matrices analogous to the ordinary exponential function. Abstractly, the matrix exponential gives the connection between a matrix Lie algebra and the corresponding Lie group....

 which is useful in the numerical evaluation of certain continuous-time Markov processes ,

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

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 A B are
It follows that the trace and determinant
Determinant
In linear algebra, the determinant is a value associated with a square matrix. It can be computed from the entries of the matrix by a specific arithmetic expression, while other ways to determine its value exist as well...

 of a Kronecker product are given by

Singular values

If A and B are rectangular matrices, then one can consider their singular values
Singular value decomposition
In linear algebra, the singular value decomposition is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics....

. Suppose that A has rA nonzero singular values, namely
Similarly, denote the nonzero singular values of B by
Then the Kronecker product A B has rArB nonzero singular values, namely
Since the rank of a matrix equals the number of nonzero singular values, we find that

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 {v1 ⊗ w1, v1 ⊗ w2, ... , v2 ⊗ w1, ... , vm ⊗ wn} of VW and the similarly defined basis of XY with the property that AB(vi ⊗ wj) = (Avi)⊗(Bwj), where i and j are integers in the proper range.

When V and W are Lie algebra
Lie algebra
In mathematics, a Lie algebra is an algebraic structure whose main use is in studying geometric objects such as Lie groups and differentiable manifolds. Lie algebras were introduced to study the concept of infinitesimal transformations. The term "Lie algebra" was introduced by Hermann Weyl in the...

s, and S : VV and T : WW are Lie algebra homomorphisms, the Kronecker sum of A and B represents the induced Lie algebra homomorphisms VWVW.

Relation to products of graphs

The Kronecker product of the adjacency matrices
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...

 of two graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 is the adjacency matrix of the tensor product graph
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 × V; and...

. The Kronecker sum of the adjacency matrices of two graphs
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 is the adjacency matrix of the Cartesian product graph
Cartesian product of graphs
In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...

. 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

Here, vec(X) denotes the vectorization
Vectorization (mathematics)
In mathematics, especially in linear algebra and matrix theory, the vectorization of a matrix is a linear transformation which converts the matrix into a column vector...

 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 .

If X is row-ordered into the column vector x then can be also be written as

History

The Kronecker product is named after Leopold Kronecker
Leopold Kronecker
Leopold Kronecker was a German mathematician who worked on number theory and algebra.He criticized Cantor's work on set theory, and was quoted by as having said, "God made integers; all else is the work of man"...

, 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
Block matrix
In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a matrix broken into sections called blocks. Looking at it another way, the matrix is written in terms of smaller matrices. We group the rows and columns into adjacent 'bunches'. A partition is the rectangle...

. Let the m-by-n matrix A be partitioned into the -by- blocks and -by- matrix into the -by- blocks Bkl with of course , , and

The Tracy-Singh product
is defined as


which means that the th subblock of the mp-by-nq product is the -by- matrix , of which the th subblock equals the -by- matrix . 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.:
we get:

The Khatri-Rao product
is defined as
in which the th block is the -by- sized Kronecker product of the corresponding blocks of and , assuming the number of row and column partitions of both matrices is equal. The size of the product is then -by-. Proceeding with the same matrices as the previous example we obtain:

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 , , and . The resulting product is a -by- matrix of which each column is the Kronecker product of the corresponding columns of and . Using the matrices from the previous examples with the columns partitioned:
so that:

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK