Produs Kronecker

În matematică produsul Kronecker, uneori notat cu ⊗, este o operație pe două matrici de dimensiuni arbitrare rezultând o matrice de blocuri. Este o particularizare a produsului tensorial^⁠(d) (care este notat cu același simbol) de la vectori la matrici, iar rezultatul este matricea aplicației liniare „produs tensorial” în raport cu o alegere standard a bazei. Produsul Kronecker trebuie să fie distins de produsul matricial obișnuit, care este o operație complet diferită. Produsul Kronecker mai este numit uneori „produs direct de matrici”.^[1]

Definiție[modificare | modificare sursă]

Dacă $A$ este o matrice $m \times n$ iar $B$ o matrice $p \times q$ , atunci produsul Kronecker $A \otimes B$ este matricea de blocuri $pm \times qn$ :

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

adică explicit:

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

Folosind $/\!/$ și $\%$ pentru a nota câtul și restul, și numerotând elementele matricei începând de la 0 se obține $(A\otimes B)_{pr+v,qs+w}=a_{rs}b_{vw}$ și $(A\otimes B)_{i,j}=a_{i/\!/p,j/\!/q}b_{i\%p,j\%q}.$ La numerotarea uzuală, care începe de la 1, se obține $(A\otimes B)_{p(r-1)+v,q(s-1)+w}=a_{rs}b_{vw}$ și $(A\otimes B)_{i,j}=a_{\lceil i/p\rceil ,\lceil j/q\rceil }b_{(i-1)\%p+1,(j-1)\%q+1}.$

Dacă $A$ și $B$ reprezintă transformări liniare $V 1 \to W 1$ , respectiv $V 2 \to W 2$ , atunci produsul tensorial a două aplicații este reprezentat de $A \otimes B$ , care este același cu $V 1 \otimes V 2 \to W 1 \otimes W 2$ .

Exemple[modificare | modificare sursă]

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

Similar:

{\begin{bmatrix}1&-4&7\\-2&3&3\end{bmatrix}}\otimes {\begin{bmatrix}8&-9&-6&5\\1&-3&-4&7\\2&8&-8&-3\\1&2&-5&-1\end{bmatrix}}={\begin{bmatrix}8&-9&-6&5&-32&36&24&-20&56&-63&-42&35\\1&-3&-4&7&-4&12&16&-28&7&-21&-28&49\\2&8&-8&-3&-8&-32&32&12&14&56&-56&-21\\1&2&-5&-1&-4&-8&20&4&7&14&-35&-7\\-16&18&12&-10&24&-27&-18&15&24&-27&-18&15\\-2&6&8&-14&3&-9&-12&21&3&-9&-12&21\\-4&-16&16&6&6&24&-24&-9&6&24&-24&-9\\-2&-4&10&2&3&6&-15&-3&3&6&-15&-3\end{bmatrix}}

Proprietăți[modificare | modificare sursă]

Relațiile cu alte operații matriciale[modificare | modificare sursă]

Biliniaritate și asociativitate:
Produsul Kronecker este un caz particular al produsului tensorial, deci este bilinar și asociativ:

${\begin{aligned}\mathbf {A} \otimes (\mathbf {B} +\mathbf {C} )&=\mathbf {A} \otimes \mathbf {B} +\mathbf {A} \otimes \mathbf {C} ,\\(\mathbf {B} +\mathbf {C} )\otimes \mathbf {A} &=\mathbf {B} \otimes \mathbf {A} +\mathbf {C} \otimes \mathbf {A} ,\\(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} ),\\\mathbf {A} \otimes \mathbf {0} &=\mathbf {0} \otimes \mathbf {A} =\mathbf {0} ,\end{aligned}}$
unde $A, B$ și $C$ sunt matrici, $0$ este matricea zero, iar $k$ este un scalar.
Necommutative: În general, $A \otimes B$ și $B \otimes A$ sunt matrici diferite. Totuși, $A \otimes B$ și $B \otimes A$ sunt permutări echivalente, adică există matricile de permutare $P$ și $Q$ astfel încât^[2]
$\mathbf {B} \otimes \mathbf {A} =\mathbf {P} \,(\mathbf {A} \otimes \mathbf {B} )\,\mathbf {Q} .$
Dacă $A$ și $B$ sunt matrici pătrate, atunci $A \otimes B$ și $B \otimes A$ sunt permutări pare similare, adică se poate lua $P = Q T$ . Matricile $P$ și $Q$ sunt matrici amestecate perfect.^[3] Matricea amestecată perfect $S p, q$ poate fi construită luând felii din matricea unitate $I r$ , unde $r=pq$ .
$\mathbf {S} _{p,q}={\begin{bmatrix}\mathbf {I} _{r}(1:q:r,:)\\\mathbf {I} _{r}(2:q:r,:)\\\vdots \\\mathbf {I} _{r}(q:q:r,:)\end{bmatrix}}$
Pentru indicarea submatricilor este folosită notația cu două puncte din MATLAB, iar $I r$ este matricea unitate $r \times r$ . Dacă $\mathbf {A} \in \mathbb {R} ^{m_{1}\times n_{1}}$ și $\mathbf {B} \in \mathbb {R} ^{m_{2}\times n_{2}}$ , atunci
$\mathbf {B} \otimes \mathbf {A} =\mathbf {S} _{m_{1},m_{2}}(\mathbf {A} \otimes \mathbf {B} )\mathbf {S} _{n_{1},n_{2}}^{\textsf {T}}$
Proprietatea produsului mixt: Dacă $A, B, C$ și $D$ sunt matrici cu dimensiuni astfel încât se pot forma produsele matriciale $AC$ și $BD$ , atunci
$(\mathbf {A} \otimes \mathbf {B} )(\mathbf {C} \otimes \mathbf {D} )=(\mathbf {AC} )\otimes (\mathbf {BD} ).$
Aceasta se numește proprietatea produsului mixt, deoarece combină produsul matricial obișnuit cu produsul Kronecker. Ca o consecință imediată,
$\mathbf {A} \otimes \mathbf {B} =(\mathbf {I_{m_{2}}} \otimes \mathbf {B} )(\mathbf {A} \otimes \mathbf {I_{n_{1}}} )=(\mathbf {A} \otimes \mathbf {I_{n_{1}}} )(\mathbf {I_{n_{2}}} \otimes \mathbf {B} ).$
În particular, folosind transpunerea de mai jos, înseamnă că dacă
$\mathbf {A} =\mathbf {Q} \otimes \mathbf {U}$
și $Q$ și $U$ sunt matrici ortogonale^⁠(d) (sau matrici unitate), atunci $A$ este și ea ortogonală (respectiv unitate). Produsul Kronecker mixt matrice-vector poate fi scris astfel:
$\left(\mathbf {A} \otimes \mathbf {B} \right)\mathbf {v} =\operatorname {vec} (\mathbf {B} \mathbf {V} \mathbf {A} ^{T})$
unde $\mathbf {V} =\operatorname {vec} ^{-1}(\mathbf {v} )$ este inversul operatorului de vectorizare (format prin remodelarea vectorului $\mathbf {v}$ ).
Produsul Hadamard: Proprietatea produsului mixt funcționează și pentru produsul pe elemente. Dacă $A$ și $C$ sunt matrici de aceeași dimensiune, iar $B$ și $D$ sunt și ele matrici de aceeași dimensiune, atunci
$(\mathbf {A} \otimes \mathbf {B} )\circ (\mathbf {C} \otimes \mathbf {D} )=(\mathbf {A} \circ \mathbf {C} )\otimes (\mathbf {B} \circ \mathbf {D} ).$
Inversul produsului Kronecker: Rezultă că $A \otimes B$ este inversabil dacă și numai dacă atât A, cât și B sunt inversabile, caz în care inversul este dat de
$(\mathbf {A} \otimes \mathbf {B} )^{-1}=\mathbf {A} ^{-1}\otimes \mathbf {B} ^{-1}.$
Proprietatea produsului inversabil este valabilă și pentru pseudoinversa Moore–Penrose^⁠(d),^[4] adică
$(\mathbf {A} \otimes \mathbf {B} )^{+}=\mathbf {A} ^{+}\otimes \mathbf {B} ^{+}.$
Transpusa: Transpusa și adjuncta sunt distributive față de produsul Kronecker:
$(\mathbf {A} \otimes \mathbf {B} )^{\textsf {T}}=\mathbf {A} ^{\textsf {T}}\otimes \mathbf {B} ^{\textsf {T}}$ and $(\mathbf {A} \otimes \mathbf {B} )^{*}=\mathbf {A} ^{*}\otimes \mathbf {B} ^{*}.$
Determinantul: Fie $A$ o matrice $n \times n$ și $B$ o matrice $m \times m$ . Atunci
$\left|\mathbf {A} \otimes \mathbf {B} \right|=\left|\mathbf {A} \right|^{m}\left|\mathbf {B} \right|^{n}.$
Exponentul lui | A | este ordinul lui $B$ , iar exponentul lui | B | este ordinul lui $A$ .
Suma și ridicarea la putere Kronecker: Dacă $A$ este $n \times n$ , $B$ este $m \times m$ , iar $I k$ este matricea unitate $k \times k$ , atunci se poate defini ceea ce uneori este numită suma Kronecker, ⊕, astfel:
$\mathbf {A} \oplus \mathbf {B} =\mathbf {A} \otimes \mathbf {I} _{m}+\mathbf {I} _{n}\otimes \mathbf {B} .$
Aceasta este diferită de adunarea obișnuită a două matrici. Această operație este legată de produsul tensorial din algebrele Lie^⁠(d). Formula pentru ridicarea la putere a matricilor, utilă în unele calcule numerice, este:^[5]
$\exp({\mathbf {N} \oplus \mathbf {M} })=\exp(\mathbf {N} )\otimes \exp(\mathbf {M} )$
Sumele Kronecker apar în mod natural în fizică când se iau în considerare ansambluri de sisteme care nu interacționează. Fie $H k$ al $k$ -lea hamiltonian al unui astfel de sistem. Atunci hamiltonianul total al ansamblului este
$H_{\mathrm {Tot} }=\bigoplus _{k}H^{k}.$

Proprietăți abstracte[modificare | modificare sursă]

Spectrul^⁠(d):
Fie matricile pătrate $A$ de dimensiune $n$ și $B$ de dimensiune $m$ . Fie $λ$ ₁, ... , $λ n$ valorile proprii ale lui $A$ și $μ$ ₁, ... , $μ m$ cele ale lui $B$ (corespunzător multiplicității). Atunci valorile proprii ale lui $A \otimes B$ sunt

$\lambda _{i}\mu _{j},\qquad i=1,\ldots ,n,\,j=1,\ldots ,m.$

Rezultă că urma și determinantul unui produs Kronecker sunt date de

$\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}.$
Valori singulare:
Dacă $A$ și $B$ sunt matrici dreptunghiulare, atunci se pot lua în considerare valorile singulare^⁠(d). Se presupune că $A$ are $r A$ valori singulare diferite de zero, și anume

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

Similar, se notează valorile singulare diferite de zero ale $B$ cu

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

Atunci produsul Kronecker $A \otimes B$ are $r A r B$ valori singulare diferite de zero, și anume

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

Deoarece rangul unei matrice este egal cu numărul de valori singulare diferite de zero, rezultă că

$\operatorname {rang} (\mathbf {A} \otimes \mathbf {B} )=\operatorname {rang} \mathbf {A} \,\operatorname {rang} \mathbf {B} .$
Relația cu produsul tensorial abstract:
Produsul Kronecker al matricilor corespunde produsului tensorial abstract al aplicațiilor liniare. Mai exact, dacă spațiile vectoriale $V, W, X$ și $Y$ au bazele ${v 1, ... , v m},$ ${w 1, ... , w n},$ ${x 1, ... , x d},$ și respectiv ${y 1, ... , y e},$ și dacă matricile $A$ și $B$ reprezintă transformările liniare $S : V \to X$ și respectiv $T : W \to Y$ , în bazele corespunzătoare, atunci matricea $A \otimes B$ reprezintă produsul tensorial al celor două aplicații, $S \otimes T : V \otimes W \to X \otimes Y$ cu privire la baza ${v 1 \otimes w 1, v 1 \otimes w 2, ... , v 2 \otimes w 1, ... , v m \otimes w n}$ din $V \otimes W$ și baza definită în mod similar pentru $X \otimes Y$ cu proprietatea că $A \otimes B (v i \otimes w j) = (Av i) \otimes (Bw j)$ , unde $i$ și $j$ sunt numere întregi în intervalul corespunzător.^[6]
Când V și W sunt algebre Lie, iar $S : V \to V$ și $T : W \to W$ sunt homomorfisme de algebre Lie, suma Kronecker a lui $A$ și $B$ reprezintă homomorfismele de algebră Lie induse $V \otimes W \to V \otimes W$ .
Relația cu produsul matricial de grafuri: Produsul Kronecker al matricilor de adiacență a două grafuri este matricea de adiacență a grafului produsului tensorial. Suma Kronecker a matricilor de adiacență a două grafuri este matricea de adiacență a grafului produsului cartezian.^[7]

Note[modificare | modificare sursă]

^ en Weisstein, Eric W. „Kronecker product”. mathworld.wolfram.com. Accesat în 6 septembrie 2020.
^ en Henderson, H.V.; Searle, S.R. (1980). „The vec-permutation matrix, the vec operator and Kronecker products: A review” (PDF). Linear and Multilinear Algebra. 9 (4): 271–288. doi:10.1080/03081088108817379. hdl:1813/32747 .
^ en Van Loan, Charles F. (2000). „The ubiquitous Kronecker product”. Journal of Computational and Applied Mathematics. 123 (1–2): 85–100. Bibcode:2000JCoAM.123...85L. doi:10.1016/s0377-0427(00)00393-9 .
^ en Langville, Amy N.; Stewart, William J. (1 iunie 2004). „The Kronecker product and stochastic automata networks”. Journal of Computational and Applied Mathematics. 167 (2): 429–447. Bibcode:2004JCoAM.167..429L. doi:10.1016/j.cam.2003.10.010 .
^ en Brewer, J.W. (1969). „A note on Kronecker matrix products and matrix equation systems”. SIAM Journal on Applied Mathematics. 17 (3): 603–606. doi:10.1137/0117057.
^ en Dummit, David S.; Foote, Richard M. (1999). Abstract Algebra (ed. 2). New York: John Wiley and Sons. pp. 401–402. ISBN 978-0-471-36857-1.
^ en See Knuth, D.E. „Pre-Fascicle 0a: Introduction to Combinatorial Algorithms” (ed. zeroth printing, revision 2). answer to Exercise 96. Arhivat din original la 13 mai 2019. Accesat în 22 aprilie 2023, to appear as part of Knuth, D.E. The Art of Computer Programming. 4A.

Bibliografie[modificare | modificare sursă]

en Horn, Roger A.; Johnson, Charles R. (1991). Topics in Matrix Analysis. Cambridge University Press. ISBN 978-0-521-46713-1.
en Jain, Anil K. (1989). Fundamentals of Digital Image Processing. Prentice Hall. Bibcode:1989fdip.book.....J. ISBN 978-0-13-336165-0.
en Steeb, Willi-Hans (1997). Matrix Calculus and Kronecker Product with Applications and C++ Programs. World Scientific Publishing. ISBN 978-981-02-3241-2.
en Steeb, Willi-Hans (2006). Problems and Solutions in Introductory and Advanced Matrix Calculus. World Scientific Publishing. ISBN 978-981-256-916-5.
en Liu, Shuangzhe; Trenkler, Götz (2008), „Hadamard, Khatri-Rao, Kronecker and other matrix products”, International Journal of Information and Systems Sciences, 4: 160–177

Legături externe[modificare | modificare sursă]

en „Kronecker product”. PlanetMath.
en Eric W. Weisstein, Kronecker product la MathWorld.
en „New Kronecker product problems” (PDF).
en „Earliest uses”. The entry on the Kronecker, Zehfuss, or Direct Product of matrices has historical information.
en calculate Kronecker product of two matrices. SourceForge (generic C++ and Fortran 90 source code). 27 iunie 2015.
en „Kronecker product”. RosettaCode.org. 31 decembrie 2020. Accesat în 13 ianuarie 2021. Software source in more than 40 languages.

Portal Matematică

[1] Weisstein, Eric W. „Kronecker product”. mathworld.wolfram.com. Accesat în 6 septembrie 2020.

[2] Henderson, H.V.; Searle, S.R. (1980). „The vec-permutation matrix, the vec operator and Kronecker products: A review” (PDF). Linear and Multilinear Algebra. 9 (4): 271–288. doi:10.1080/03081088108817379. hdl:1813/32747 .

[3] Van Loan, Charles F. (2000). „The ubiquitous Kronecker product”. Journal of Computational and Applied Mathematics. 123 (1–2): 85–100. Bibcode:2000JCoAM.123...85L. doi:10.1016/s0377-0427(00)00393-9 .

[4] Langville, Amy N.; Stewart, William J. (1 iunie 2004). „The Kronecker product and stochastic automata networks”. Journal of Computational and Applied Mathematics. 167 (2): 429–447. Bibcode:2004JCoAM.167..429L. doi:10.1016/j.cam.2003.10.010 .

[5] Brewer, J.W. (1969). „A note on Kronecker matrix products and matrix equation systems”. SIAM Journal on Applied Mathematics. 17 (3): 603–606. doi:10.1137/0117057.

[6] Dummit, David S.; Foote, Richard M. (1999). Abstract Algebra (ed. 2). New York: John Wiley and Sons. pp. 401–402. ISBN 978-0-471-36857-1.

[TAOCP0a-7] See Knuth, D.E. „Pre-Fascicle 0a: Introduction to Combinatorial Algorithms” (ed. zeroth printing, revision 2). answer to Exercise 96. Arhivat din original la 13 mai 2019. Accesat în 22 aprilie 2023, to appear as part of Knuth, D.E. The Art of Computer Programming. 4A.

[1]

[2]

[3]

[4]

[5]

[6]

[7]