Kronecker product: Difference between revisions
Reverted good faith edits by Bmasiero (talk): Rv COI selfcite. (TW) |
m Complete a sentence with newly published results. |
||
Line 398: | Line 398: | ||
</math> |
</math> |
||
This column-wise version of the Khatri-Rao product is useful in linear algebra approaches to data analytical processing |
This column-wise version of the Khatri-Rao product is useful in linear algebra approaches to data analytical processing<ref>See e.g. H.D. Macedo and J.N. Oliveira. [http://dx.doi.org/10.1007/s00165-014-0316-9 A linear algebra approach to OLAP]. Formal Aspects of Computing, 27(2):283–307, 2015.</ref> |
||
==Some proposed changes== |
|||
{{request edit}} |
|||
Please allow the previous sentence to be compleated with the text below: |
|||
and in optimizing the solution of inverse problems dealing with a diagonal matrix<ref>{{Cite journal|last=Lev-ari|first=Hanoch|date=2005-01-01|title=Efficient solution of linear matrix equations with application to multistatic antenna array processing|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.125.2878|journal=Communications in Information and Systems|volume=5|pages=123–130}}</ref><ref>{{Cite journal|last=Masiero|first=B.|last2=Nascimento|first2=V. H.|date=2017-05-01|title=Revisiting the Kronecker Array Transform|url=http://ieeexplore.ieee.org/document/7864371/|journal=IEEE Signal Processing Letters|volume=24|issue=5|pages=525–529|doi=10.1109/LSP.2017.2674969|issn=1070-9908}}</ref>. |
|||
Please note that one of the articles sited is of my authorship. Nevertheless, it gives new applications to the Khatri-Rao problem, and, more importantly, presentes a new relationship between the Khatri-Rao and the Kronecker product, what is in accordance with the contents of this Wikipage. |
|||
If you wish to verify the contents of the paper I listed, you can find a copy of it in my webpage http://www.decom.fee.unicamp.br/~masiero or directly at http://www.decom.fee.unicamp.br/~masiero/articles/Journal/LSP2674969.pdf. |
|||
[[User:Bmasiero|Bmasiero]] ([[User talk:Bmasiero|talk]]) 13:02, 27 March 2017 (UTC) Dr. Bruno Masiero |
|||
== See also == |
== See also == |
||
* [[Generalized linear array model]] |
* [[Generalized linear array model]] |
Revision as of 13:03, 27 March 2017
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 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 who in 1858 described the matrix operation we now know as the Kronecker product.[1]
Definition
If A is an m × n matrix and B is a p × q matrix, then the Kronecker product A ⊗ B is the mp × nq block matrix:
more explicitly:
More compactly, we have
If A and B represent linear transformations V1 → W1 and V2 → W2, respectively, then A ⊗ B represents the tensor product of the two maps, V1 ⊗ V2 → W1 ⊗ W2.
Example
Properties
Relations to other matrix operations
- Bilinearity and associativity:
The Kronecker product is a special case of the tensor product, so it is bilinear and associative:
- Non-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 P and Q (so called commutation matrices) such that[2]
- 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
- Transpose:
Transposition and conjugate transposition are distributive over the Kronecker product:
- and
- Determinant:
Let A be an n × n matrix and let B be an m × m matrix. Then
- 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
- .
Abstract properties
- 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 of a Kronecker product are given by
- 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
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 : 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 with the property that A ⊗ B(vi ⊗ wj) = (Avi) ⊗ (Bwj), where i and j are integers in the proper range.[5]
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.[6]
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 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 AXB can be also be written as (Jain 1989, 2.8 Block Matrices and Kronecker Products) (A ⊗ BT)x.
Applications
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.
Related matrix operations
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.
Tracy–Singh product
The Tracy–Singh product is defined as[7][8]
which means that the (ij)-th subblock of the mp × nq product A ∘ B is the mi p × nj q matrix Aij ∘ B, of which the (kℓ)-th subblock equals the mi pk × nj qℓ matrix Aij ⊗ Bkℓ. 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 × 2 partitioned matrices e.g.:
we get:
Khatri–Rao product
The Khatri–Rao product is defined as[9][10]
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:
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 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:
so that:
This column-wise version of the Khatri-Rao product is useful in linear algebra approaches to data analytical processing[11]
Some proposed changes
Error: Protected edit requests can only be made on the talk page. Please allow the previous sentence to be compleated with the text below:
and in optimizing the solution of inverse problems dealing with a diagonal matrix[12][13].
Please note that one of the articles sited is of my authorship. Nevertheless, it gives new applications to the Khatri-Rao problem, and, more importantly, presentes a new relationship between the Khatri-Rao and the Kronecker product, what is in accordance with the contents of this Wikipage. If you wish to verify the contents of the paper I listed, you can find a copy of it in my webpage http://www.decom.fee.unicamp.br/~masiero or directly at http://www.decom.fee.unicamp.br/~masiero/articles/Journal/LSP2674969.pdf. Bmasiero (talk) 13:02, 27 March 2017 (UTC) Dr. Bruno Masiero
See also
Notes
- ^ G. Zehfuss (1858), "Ueber eine gewisse Determinante", Zeitschrift für Mathematik und Physik, 3: 298–301.
- ^ H. V. Henderson; S. R. Searle (1980). "The vec-permutation matrix, the vec operator and Kronecker products: A review". LINEAR AND MULTILINEAR ALGEBRA. 9 (4): 271–288. doi:10.1080/03081088108817379.
- ^ Langville, Amy N.; Stewart, William J. (June 1, 2004). "The Kronecker product and stochastic automata networks". Journal of Computational and Applied Mathematics. 167 (2): 429–447. doi:10.1016/j.cam.2003.10.010.
- ^ J. W. Brewer (1969). "A Note on Kronecker Matrix Products and Matrix Equation Systems". SIAM Journal on Applied Mathematics. 17 (3): 603–606. doi:10.1137/0117057.
- ^ Dummit, David S.; Foote, Richard M. (1999). Abstract Algebra (2 ed.). New York: John Wiley and Sons. pp. 401–402. ISBN 0-471-36857-1.
- ^ 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
- ^ Tracy, D. S.; Singh, R. P. (1972). "A New Matrix Product and Its Applications in Matrix Differentiation". Statistica Neerlandica. 26 (4): 143–157. doi:10.1111/j.1467-9574.1972.tb00199.x.
- ^ Liu, S. (1999). "Matrix Results on the Khatri–Rao and Tracy–Singh Products". Linear Algebra and its Applications. 289 (1–3): 267–277. doi:10.1016/S0024-3795(98)10209-4.
- ^ Khatri C. G., C. R. Rao (1968). "Solutions to some functional equations and their applications to characterization of probability distributions". Sankhya. 30: 167–180.
{{cite journal}}
: CS1 maint: postscript (link) - ^ Zhang X; Yang Z; Cao C. (2002), "Inequalities involving Khatri–Rao products of positive semi-definite matrices", Applied Mathematics E-notes, 2: 117–124
- ^ See e.g. H.D. Macedo and J.N. Oliveira. A linear algebra approach to OLAP. Formal Aspects of Computing, 27(2):283–307, 2015.
- ^ Lev-ari, Hanoch (2005-01-01). "Efficient solution of linear matrix equations with application to multistatic antenna array processing". Communications in Information and Systems. 5: 123–130.
- ^ Masiero, B.; Nascimento, V. H. (2017-05-01). "Revisiting the Kronecker Array Transform". IEEE Signal Processing Letters. 24 (5): 525–529. doi:10.1109/LSP.2017.2674969. ISSN 1070-9908.
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 981-02-3241-1
- Steeb, Willi-Hans (2006), Problems and Solutions in Introductory and Advanced Matrix Calculus, World Scientific Publishing, ISBN 981-256-916-2
External links
- "Tensor product", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- "Kronecker product". PlanetMath.
- 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.