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

Dacă A este o matrice m × n iar B o matrice p × q, atunci produsul Kronecker AB este matricea de blocuri pm × qn:

A B = [ a 11 B a 1 n B a m 1 B a m n B ] , {\displaystyle \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:

A B = [ a 11 b 11 a 11 b 12 a 11 b 1 q a 1 n b 11 a 1 n b 12 a 1 n b 1 q a 11 b 21 a 11 b 22 a 11 b 2 q a 1 n b 21 a 1 n b 22 a 1 n b 2 q a 11 b p 1 a 11 b p 2 a 11 b p q a 1 n b p 1 a 1 n b p 2 a 1 n b p q a m 1 b 11 a m 1 b 12 a m 1 b 1 q a m n b 11 a m n b 12 a m n b 1 q a m 1 b 21 a m 1 b 22 a m 1 b 2 q a m n b 21 a m n b 22 a m n b 2 q a m 1 b p 1 a m 1 b p 2 a m 1 b p q a m n b p 1 a m n b p 2 a m n b p q ] . {\displaystyle {\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 / / {\displaystyle /\!/} și % {\displaystyle \%} pentru a nota câtul și restul, și numerotând elementele matricei începând de la 0 se obține ( A B ) p r + v , q s + w = a r s b v w {\displaystyle (A\otimes B)_{pr+v,qs+w}=a_{rs}b_{vw}} și ( A B ) i , j = a i / / p , j / / q b i % p , j % q . {\displaystyle (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 B ) p ( r 1 ) + v , q ( s 1 ) + w = a r s b v w {\displaystyle (A\otimes B)_{p(r-1)+v,q(s-1)+w}=a_{rs}b_{vw}} și ( A B ) i , j = a i / p , j / q b ( i 1 ) % p + 1 , ( j 1 ) % q + 1 . {\displaystyle (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 V1W1, respectiv V2W2, atunci produsul tensorial a două aplicații este reprezentat de AB, care este același cu V1V2W1W2.

Exemple

[ 1 2 3 4 ] [ 0 5 6 7 ] = [ 1 [ 0 5 6 7 ] 2 [ 0 5 6 7 ] 3 [ 0 5 6 7 ] 4 [ 0 5 6 7 ] ] = [ 1 × 0 1 × 5 2 × 0 2 × 5 1 × 6 1 × 7 2 × 6 2 × 7 3 × 0 3 × 5 4 × 0 4 × 5 3 × 6 3 × 7 4 × 6 4 × 7 ] = [ 0 5 0 10 6 7 12 14 0 15 0 20 18 21 24 28 ] . {\displaystyle {\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:

[ 1 4 7 2 3 3 ] [ 8 9 6 5 1 3 4 7 2 8 8 3 1 2 5 1 ] = [ 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 ] {\displaystyle {\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

Relațiile cu alte operații matriciale

  1. Biliniaritate și asociativitate:

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

    A ( B + C ) = A B + A C , ( B + C ) A = B A + C A , ( k A ) B = A ( k B ) = k ( A B ) , ( A B ) C = A ( B C ) , A 0 = 0 A = 0 , {\displaystyle {\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.
  2. Necommutative: În general, AB și BA sunt matrici diferite. Totuși, AB și BA sunt permutări echivalente, adică există matricile de permutare P și Q astfel încât[2]
    B A = P ( A B ) Q . {\displaystyle \mathbf {B} \otimes \mathbf {A} =\mathbf {P} \,(\mathbf {A} \otimes \mathbf {B} )\,\mathbf {Q} .}
    Dacă A și B sunt matrici pătrate, atunci AB și BA sunt permutări pare similare, adică se poate lua P = QT. Matricile P și Q sunt matrici amestecate perfect.[3] Matricea amestecată perfect Sp,q poate fi construită luând felii din matricea unitate Ir, unde r = p q {\displaystyle r=pq} .
    S p , q = [ I r ( 1 : q : r , : ) I r ( 2 : q : r , : ) I r ( q : q : r , : ) ] {\displaystyle \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 Ir este matricea unitate r × r. Dacă A R m 1 × n 1 {\displaystyle \mathbf {A} \in \mathbb {R} ^{m_{1}\times n_{1}}} și B R m 2 × n 2 {\displaystyle \mathbf {B} \in \mathbb {R} ^{m_{2}\times n_{2}}} , atunci
    B A = S m 1 , m 2 ( A B ) S n 1 , n 2 T {\displaystyle \mathbf {B} \otimes \mathbf {A} =\mathbf {S} _{m_{1},m_{2}}(\mathbf {A} \otimes \mathbf {B} )\mathbf {S} _{n_{1},n_{2}}^{\textsf {T}}}
  3. 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
    ( A B ) ( C D ) = ( A C ) ( B D ) . {\displaystyle (\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ă,
    A B = ( I m 2 B ) ( A I n 1 ) = ( A I n 1 ) ( I n 2 B ) . {\displaystyle \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ă
    A = Q U {\displaystyle \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:
    ( A B ) v = vec ( B V A T ) {\displaystyle \left(\mathbf {A} \otimes \mathbf {B} \right)\mathbf {v} =\operatorname {vec} (\mathbf {B} \mathbf {V} \mathbf {A} ^{T})}
    unde V = vec 1 ( v ) {\displaystyle \mathbf {V} =\operatorname {vec} ^{-1}(\mathbf {v} )} este inversul operatorului de vectorizare (format prin remodelarea vectorului v {\displaystyle \mathbf {v} } ).
  4. 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
    ( A B ) ( C D ) = ( A C ) ( B D ) . {\displaystyle (\mathbf {A} \otimes \mathbf {B} )\circ (\mathbf {C} \otimes \mathbf {D} )=(\mathbf {A} \circ \mathbf {C} )\otimes (\mathbf {B} \circ \mathbf {D} ).}
  5. Inversul produsului Kronecker: Rezultă că AB este inversabil dacă și numai dacă atât A, cât și B sunt inversabile, caz în care inversul este dat de
    ( A B ) 1 = A 1 B 1 . {\displaystyle (\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ă
    ( A B ) + = A + B + . {\displaystyle (\mathbf {A} \otimes \mathbf {B} )^{+}=\mathbf {A} ^{+}\otimes \mathbf {B} ^{+}.}
  6. Transpusa: Transpusa și adjuncta sunt distributive față de produsul Kronecker:
    ( A B ) T = A T B T {\displaystyle (\mathbf {A} \otimes \mathbf {B} )^{\textsf {T}}=\mathbf {A} ^{\textsf {T}}\otimes \mathbf {B} ^{\textsf {T}}} and ( A B ) = A B . {\displaystyle (\mathbf {A} \otimes \mathbf {B} )^{*}=\mathbf {A} ^{*}\otimes \mathbf {B} ^{*}.}
  7. Determinantul: Fie A o matrice n × n și B o matrice m × m. Atunci
    | A B | = | A | m | B | n . {\displaystyle \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.
  8. Suma și ridicarea la putere Kronecker: Dacă A este n × n, B este m × m, iar Ik este matricea unitate k × k, atunci se poate defini ceea ce uneori este numită suma Kronecker, ⊕, astfel:
    A B = A I m + I n B . {\displaystyle \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 ( N M ) = exp ( N ) exp ( M ) {\displaystyle \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 Hk al k-lea hamiltonian al unui astfel de sistem. Atunci hamiltonianul total al ansamblului este
    H T o t = k H k . {\displaystyle H_{\mathrm {Tot} }=\bigoplus _{k}H^{k}.}

Proprietăți abstracte

  1. Spectrul⁠(d):

    Fie matricile pătrate A de dimensiune n și B de dimensiune m. Fie λ1, ... , λn valorile proprii ale lui A și μ1, ... , μm cele ale lui B (corespunzător multiplicității). Atunci valorile proprii ale lui AB sunt

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

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

    tr ( A B ) = tr A tr B and det ( A B ) = ( det A ) m ( det B ) n . {\displaystyle \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. Valori singulare:

    Dacă A și B sunt matrici dreptunghiulare, atunci se pot lua în considerare valorile singulare⁠(d). Se presupune că A are rA valori singulare diferite de zero, și anume

    σ A , i , i = 1 , , r A . {\displaystyle \sigma _{\mathbf {A} ,i},\qquad i=1,\ldots ,r_{\mathbf {A} }.}

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

    σ B , i , i = 1 , , r B . {\displaystyle \sigma _{\mathbf {B} ,i},\qquad i=1,\ldots ,r_{\mathbf {B} }.}

    Atunci produsul Kronecker AB are rArB valori singulare diferite de zero, și anume

    σ A , i σ B , j , i = 1 , , r A , j = 1 , , r B . {\displaystyle \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ă

    rang ( A B ) = rang A rang B . {\displaystyle \operatorname {rang} (\mathbf {A} \otimes \mathbf {B} )=\operatorname {rang} \mathbf {A} \,\operatorname {rang} \mathbf {B} .}
  3. 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 {v1 , ... , vm}, {w1, ... , wn}, {x1, ... , xd}, și respectiv {y1, ... , ye}, și dacă matricile A și B reprezintă transformările liniare S : VX și respectiv T : WY, în bazele corespunzătoare, atunci matricea AB reprezintă produsul tensorial al celor două aplicații, ST : VWXY cu privire la baza {v1w1, v1w2, ... , v2w1, ... , vmwn} din VW și baza definită în mod similar pentru XY cu proprietatea că AB(viwj) = (Av i) ⊗ (Bwj), unde i și j sunt numere întregi în intervalul corespunzător.[6]

    Când V și W sunt algebre Lie, iar S : VV și T : WW sunt homomorfisme de algebre Lie, suma Kronecker a lui A și B reprezintă homomorfismele de algebră Lie induse VWVW.
  4. 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

  1. ^ en Weisstein, Eric W. „Kronecker product”. mathworld.wolfram.com. Accesat în . 
  2. ^ en Henderson, H.V.; Searle, S.R. (). „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 Accesibil gratuit. 
  3. ^ en Van Loan, Charles F. (). „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 Accesibil gratuit. 
  4. ^ en Langville, Amy N.; Stewart, William J. (). „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 Accesibil gratuit. 
  5. ^ en Brewer, J.W. (). „A note on Kronecker matrix products and matrix equation systems”. SIAM Journal on Applied Mathematics. 17 (3): 603–606. doi:10.1137/0117057. 
  6. ^ en Dummit, David S.; Foote, Richard M. (). Abstract Algebra (ed. 2). New York: John Wiley and Sons. pp. 401–402. ISBN 978-0-471-36857-1. 
  7. ^ 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 . Accesat în ,  Parametru necunoscut |arhivat= ignorat (ajutor); Mai multe valori specificate pentru |urlarhivă= și |archive-url= (ajutor); Mai multe valori specificate pentru |deadurl= și |dead-url= (ajutor) to appear as part of Knuth, D.E. The Art of Computer Programming. 4A. 

Bibliografie

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

Legături externe

  • 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). . 
  • en „Kronecker product”. RosettaCode.org. . Accesat în .  Software source in more than 40 languages.
Portal icon Portal Matematică