Înmulțirea matricilor

operație matematică în algebra liniară

În matematică, în special în algebra liniară, înmulțirea matricilor sau înmulțirea matricială[1] este o operație binară care produce o matrice din două matrici. La înmulțirea matricială, numărul de coloane din prima matrice trebuie să fie egal cu numărul de linii din a doua matrice. Matricea rezultată, cunoscută sub numele de produs matricial, are numărul de linii ale primei matrice și numărul de coloane ale celei de-a doua matrice. Produsul matricilor A și B este notat AB.[2]

La înmulțirea matricilor, numărul de coloane din prima matrice trebuie să fie egal cu numărul de linii din a doua matrice. Matricea rezultată are numărul de linii ale primei matrice și numărul de coloane ale celei de-a doua matrice.

Înmulțirea matricială a fost descrisă pentru prima dată de matematicianul francez Jacques Philippe Marie Binet în 1812,[3] pentru a reprezenta compunerea funcțiilor⁠(d) de transformări liniare care sunt reprezentate cu ajutorul matricilor. Astfel, înmulțirea matricială a devenit un instrument de bază al algebrei liniare și, ca atare, are numeroase aplicații în multe domenii ale matematicii, precum și în matematica aplicată, statistică, fizică, economie și inginerie.[4][5] Calculul produselor matriciale este o operație centrală în toate aplicațiile algebrei liniare.

Notație

modificare

În acest articol convențiile privind notațiile sunt următoarele: matricile sunt reprezentate prin litere majuscule grase (bold), de exemplu A; vectorii cu litere minuscule grase, de exemplu a; iar elementele vectorilor și matricilor cu italice, de exemplu A sau a. Notația indexată este adesea cel mai clar mod de a exprima definițiile și este notația standard folosit în literatura de specialitate. Linia din matrice este indicată de indicele i, iar coloana de indicele j. Elementul matricei A este indicat prin (A)ij, Aij sau aij. Prin excepție, un singur indice, de exemplu A1, A2, se folosește pentru a indica o matrice (nu un element al unei matrice) dintr-o colecție de matrici.

Definiție

modificare

Dacă A este o matrice m × n iar B este o matrice n × p,

 

Produsul matricial C = AB (notat fără punct sau semnul înmulțirii) este definit ca fiind matricea m × p [6][7][8][9]

 

asfel încât

 

pentru i = 1, ..., m și j = 1, ..., p.

Adică elementul cij al produsului se obține prin înmulțirea termen cu termen a elementelor din linia i a matricei A cu cele din coloana j a matricei B și sumând aceste n produse. Altfel spus, cij este produsul scalar al liniei i a matricei A cu coloana j a matricei B.

Prin urmare AB poate fi scris și ca

 

Astfel produsul AB este definit dacă și numai dacă numărul de coloane din A este egal cu numărul de linii din B,[2] în acest caz n.

În majoritatea cazurilor elementele matricilor sunt numere, dar pot fi orice fel de obiecte matematice pentru care sunt definite o adunare și o înmulțire, care sunt asociative, adunarea să fie comutativă, iar înmulțirea să fie distributivă în raport cu adunarea. În particular, elementele pot fi ele înseși matrici.

Ilustrare

modificare
 
Prezentare vizuală a calculului termenilor produsului matricial

Figura din dreapta ilustrează schematic produsul a două matrice A și B, arătând cum fiecare intersecție din matricea produsului corespunde cu o linie din A și o coloană din B.

 

Valorile de la intersecții, marcate cu cercuri în figura din dreapta, sunt:

 

Principalele aplicații

modificare

Istoric, înmulțirea matricilor a fost introdusă pentru a facilita și clarifica calculele din algebra liniară. Această relație strânsă între înmulțirea matricilor și algebra liniară rămâne fundamentală în toate ramurile matematicii, precum și în fizică, chimie, inginerie și informatică.

Aplicații liniare

modificare

Dacă un spațiu vectorial are o bază finită, orice vector este reprezentat în mod unic printr-un șir finit de scalari, numit componentele vectorului, ale cărui elemente sunt coordonatele vectorului în acea bază. Aceste componente formează un alt spațiu vectorial, care este izomorf cu spațiul vectorial inițial. Componentele vectorului sunt plasate de obicei într-o matrice coloană (numită și vector coloană), care este o matrice cu o singură coloană. Deci, un vector coloană reprezintă atât componentele vectorului, cât și un vector din spațiului vectorial inițial.

O aplicație liniară A dintr-un spațiu vectorial de dimensiune n într-un spațiu vectorial de dimensiune m aplică un vector coloană

 

pe vectorul coloană

 

Aplicația liniară A este astfel definită de matricea

 

și aplică vectorul coloană   pe produsul matricial

 

Dacă B este o altă aplicație liniară din spațiul vectorial precedent de dimensiunea m, într-un spațiu vectorial de dimensiunea p, este reprezentată printr-o matrice   (p × m). Un calcul simplu arată că matricea compunerii   este produsul matricial   Formula generală   care definește funcția compusă este prezentată aici ca un caz particular de asociativitate al produsului matricial:

 

Rotațiile geometrice

modificare

Folosind un sistem de coordonate carteziene într-un plan euclidian, rotația cu un unghi   în jurul originii este o aplicație liniară. Mai exact,

 

unde punctul inițial   și imaginea sa   sunt scrise ca vectori coloană.

Compunerea rotației cu unghiul   și cea cu unghiul   corespunde apoi cu produsul matricial

 

în care membrul drept al ultimei identități conține identitățile trigonometrice pentru sinusul și cosinusul sumei și diferenței unghiurilor, compunerea corespunde rotației cu unghiul  , cum era de așteptat.

Alocarea resurselor în economie

modificare
 
Calculul elementului din stânga jos a   corespunde luării în considerare a tuturor căilor (evidențiate) de la materia primă   la produsul final   în graful fluxului de producție

De exemplu, o fabrică fictivă folosește 4 tipuri de materii prime,   pentru a produce 3 tipuri de bunuri intermediare ,  , care la rândul lor sunt folosite pentru a produce 3 tipuri de produse finite,  . Matricile

    și    

furnizează cantitatea de materii prime necesare pentru o anumită cantitate de bunuri intermediare și, respectiv, cantitatea de bunuri intermediare necesară pentru o anumită cantitate de produse finite. De exemplu, pentru a produce o unitate de bun intermediar  , sunt necesare o unitate de materie primă  , două unități de  , nicio unitate de   și o unitate de  , corespunzătoare primei coloane din  .

Folosind înmulțirea matricilor se calculează

 

această matrice indică direct cantitățile de materii prime necesare pentru cantități date de produse finite. De exemplu, intrarea din stânga jos a   este calculată ca fiind  , reflectând faptul că pentru a produce o unitate de   sunt necesare   unități de  . Efectiv, este necesară o unitate de   pentru  , 2 pentru   și   pentru fiecare dintre cele două   unități care intră în unitatea  , vezi imaginea.

Pentru a produce de exemplu 100 de unități din produsul final  , 80 de unități de   și 60 de unități de  , cantitățile necesare de materii prime pot fi calculate prin

 

adică   unități de  ,   unități de  ,   unități de   și   unități de  . Similar, matricea produsului   poate fi utilizată pentru a calcula cantitățile necesare de materii prime pentru alte date privind cantitățile de produse finale.[10]

Sisteme de ecuații liniare

modificare

Forma generală a unui sistem de ecuații liniare este:

 

Folosind aceeași notație ca mai sus, un astfel de sistem este echivalent cu o singură ecuație matricială:

 

Produsul scalar, forma biliniară și sesquiliniară

modificare

Produsul scalar al doi vectori coloană este elementul unic al produsului matricial

 

unde   este vectorul linie obținut prin transpunerea  . (De obicei o matrice 1×1 este identificată prin unicul său element.)

În general, orice formă biliniară pe un spațiu vectorial de dimensiune finită poate fi exprimată ca produs matricial:

 

și orice altă formă sesquiliniară⁠(d) poate fi exprimată prin

 

unde   este adjuncta lui   (transpusa conjugată).

Proprietăți generale

modificare

Înmulțirea matricială are unele proprietăți asemănătoare cu înmulțirea obișnuită. Totuși, înmulțirea matricială nu este definită dacă numărul de coloane al primului factor diferă de numărul de linii al celui de-al doilea factor și este necomutativă,[11] chiar și când produsul rămâne definit după schimbarea ordinii factorilor.[12][13]

Necomutativitatea

modificare

O operație este comutativă dacă, fiind date două elemente A și B astfel încât produsul   este definit, atunci   este definit și  

Înmulțirea matricială a două matrici A și B al căror produs matricial   este definit, ar fi comutativă dacă produsul   este și el definit, iar  

Dacă A și B sunt matrici de dimensiunile m×n respectiv p×q, atunci   este definit dacă n = p, iar   este definit dacă m = q. Prin urmare, dacă unul dintre produse este definit, celălalt ar trebui să fie nedefinit. Dacă  , cele două produse sunt definite, dar au dimensiuni diferite; astfel că ele nu pot fi egale. Doar dacă m = q= n= p, adică dacă A și B sunt ambele pătrate, de aceeași dimensiune, ambele produse sunt definite și au aceeași dimensiune. Chiar și în acest caz, în general

 

De exemplu

 

dar

 

Acest exemplu poate fi extins pentru a arăta că dacă A este o matrice n×n cu elementele într-un corp F, atunci   pentru orice matrice B n×n cu elementele din F dacă și numai dacă   unde   și I este matricea unitate n×n. Dacă, în loc de un corp, se presupune că elementele aparțin unui inel, atunci trebuie adăugată condiția ca c să aparțină centrului inelului.

Un caz particular în care comutativitatea apare este atunci când D și E sunt două matrici diagonale pătrate de aceeași mărime. Atunci DE = ED.[11] Din nou, dacă matricile sunt peste un inel generic în loc de a fi peste un corp, elementele corespunzătoare ale fiecăreia trebuie, de asemenea, să fie comutative unul față de celălalt pentru ca acest lucru să fie valabil.

Distributivitatea

modificare

Produsul matricial este distributiv față de adunarea matricilor. Adică dacă A, B, C, D sunt matrici de dimensiunile respective m×n, n×p, n×p, și p×q, există atât distributivitatea la stânga[11]

 

cât și la dreapta[11]

 

Aceasta rezultă din distributivitatea coeficienților

 
 

Asociativitatea

modificare

Fiind date matricile A, B și C, produsele (AB)C și A(BC) sunt definite dacă și numai dacă numărul de coloane din A este egal cu numărul de linii din B și numărul de coloane din B este egal cu numărul de linii din C (în special, dacă unul dintre produse este definit, atunci celălalt este și el definit). În acest caz există asociativitatea

 

Ca la orice operație asociativă, aceasta permite omiterea parantezelor și scrierea produselor de mai sus ca  

Aceasta se extinde natural la produsul a oricâte matrici, cu condiția ca dimensiunile să se potrivească. Adică dacă A1, A2, ... , A n sunt matrici astfel încât numărul de coloane ale Ai este egal numărul de linii ale Ai + 1 pentru i = 1, ... , n−1, atunci produsul

 

este definit și nu depinde de ordinea în care se fac înmulțirile, cât timp ordinea matricilor este păstrată fixă.

Aceste proprietăți pot fi demonstrate prin operații de adunare simple, dar lungi. Acest rezultat rezultă și din faptul că matricile sunt aplicații liniare. Prin urmare, proprietatea asociativă a matricilor este pur și simplu un caz particular al proprietății asociative a compunerii funcțiilor⁠(d).

Produsul cu un scalar

modificare

Dacă A este o matrice și c un scalar, atunci matricile   și   se obțin înmulțind la stânga sau la dreapta toate elementele lui A cu c. Dacă scalarii sunt comutativi, atunci  

Dacă produsul   este definit (adică numărul de coloane din A este egal cu numărul de linii din B), atunci

    și    

Dacă scalarii sunt comutativi, atunci toate cele patru matrici sunt egale. În general, toate cele patru sunt egale dacă c aparține centrului unui inel care conține elementele matricei, deoarece în acest caz, cX = Xc pentru toate matricile X.

Aceste proprietăți rezultă din biliniaritatea produsului scalarilor:

 
 

Operații cu matricea transpusă

modificare

Dacă scalarii sunt comutativi, transpusa produsului matricial este produsul, în ordine inversă, al transpuselor factorilor. Acesta este

 

unde cu T este notată transpusa.

Această identitate nu este valabilă pentru elementele necomutative, deoarece ordinea dintre elementele lui A și B este inversată atunci când se extinde definirea produsului matricial.

Conjugata complexă

modificare

Dacă A și B au elemente complexe, atunci

 

unde cu * sunt notate conjugatele complexe ale elementelor matricei.

Acest lucru rezultă din aplicarea la definiția produsului matricial a faptului că conjugatul unei sume este suma conjugatelor sumelor, iar conjugatul unui produs este produsul conjugatelor factorilor.

Transpunerea acționează asupra indicilor elementelor, în timp ce conjugarea acționează independent asupra elementelor în sine. Rezultă că, dacă A și B au elemente complexe, există

 

unde cu sunt notate adjunctele (conjugatele transpuselor, sau, echivalent, transpusele conjugatelor).

Matrici pătrate

modificare

Fie   mulțimea de matrici pătrate n×n cu elementele din inelul R, care, în practică, este adesea un corp.

În  , produsul este definit pentru fiecare pereche de matrici. Acest lucru face din   un inel, care are matricea unitate I ca element neutru (matricea ale cărei elemente pe diagonala principală sunt egale cu 1 și toate celelalte elemente sunt 0). Acest inel este, de asemenea, o R-algebră asociativă⁠(d).

Dacă n > 1, multe matrici nu au o inversă multiplicativă. De exemplu, o matrice care are toate elementele unei linii (sau unei coloane) 0 nu are inversă. Dacă există, inversa unei matrice A se notează A−1 și verifică relația

 

O matrice care are o inversă este o matrice inversabilă. În caz contrar, este o matrice singulară.

Un produs matricial este inversabil dacă și numai dacă fiecare factor este inversabil. În acest caz există relația

 

Când R este comutativ și, în special, când este un corp, determinantul unui produs este produsul determinanților. Deoarece determinanții sunt scalari, iar scalarii sunt comutativi, există relația

 

Ceilalți invarianți⁠(d) matriciali nu se comportă la fel de bine cu produsele. Totuși, dacă R este comutativ, AB și BA au aceeași urmă, același polinom caracteristic⁠(d) și aceleași valori proprii cu aceleași multiplicități. Totuși, vectorii proprii sunt în general diferiți dacă ABBA.

Puterea unei matrice pătrate

modificare

O matrice pătrată poate fi ridicată la orice putere întreagă nenegativă înmulțind-o cu ea însăși în mod repetat, în același mod ca pentru numerele obișnuite. Acesta este,

 
 
 

Calcularea celei de a k-a putere a unei matrice, dacă se face cu algoritmul trivial (înmulțire repetată) necesită de k−1 ori timpul unei singure înmulțiri matriciale. Deoarece acest lucru consumă foarte mult timp, se preferă metoda ridicării la putere rapide⁠(d), care necesită mai puțin de 2 log2 k înmulțiri matriciale, deci este mult mai eficientă.

Un caz ușor de ridicare la putere este cel al unei matrice diagonale. Deoarece produsul matricilor diagonale echivalează cu simpla înmulțire a elementelor diagonale corespunzătoare, a k-a putere a unei matrici diagonale se obține prin ridicarea elementelor ei la puterea k:

 

Aplicație la matrici asemenea

modificare

Orice matrice inversabilă   definește o transformare de asemănare (pe matrici pătrate de aceeași dimensiune ca  )

 

Transformările de asemănare aplică produsul la factori, adică

 

De fapt,

 

Complexitatea de calcul

modificare
 
Îmbunătățirea estimărilor exponentului ω în timp pentru complexitatea de calcul a înmulțirii matriciale  

Un algoritm de înmulțire a matricilor care rezultă din definiție necesită în cazul cel mai rău n3 înmulțiri și (n−1)n2 adunări de scalari pentru a calcula produsul a două matrice pătrate n×n. Într-un model de calcul în care operațiile scalare au timp constant complexitatea sa de calcul⁠(d) este deci O(n3).

Surprinzător, această complexitate nu este optimă, așa cum a arătat în 1969 Volker Strassen, care a furnizat un algoritm, numit acum algoritmul Strassen⁠(d), cu o complexitate de  [14]

Din 2020, cel mai bun algoritm de înmulțire matricială era cel dat de Josh Alman și Virginia Vassilevska Williams, cu complexitatea O(n2.3728596).[15]

Nu se știe dacă înmulțirea matricială poate fi efectuată în timp n2 + o(1). Acest lucru ar fi optim, deoarece trebuie citite cele n2 elementele unei matrice pentru a o înmulți cu o altă matrice.

Deoarece înmulțirea matricială formează baza pentru mulți algoritmi și multe operații pe matrici chiar au aceeași complexitate ca și înmulțirea matricială (până la o constantă multiplicativă), complexitatea de calcul a înmulțirii matriciale este o chestiune importantă în algebra liniară numerică⁠(d) și informatica teoretică⁠(d).

Complexitatea de calcul în funcție de ordinea operațiilor

modificare

Deși rezultatul unei secvențe de produse matrice nu depinde de ordinea efectuării produselor (cu condiția ca ordinea matricelor să nu fie schimbată), complexitatea de calcul poate depinde mult de această ordine.

De exemplu, dacă A, B și C sunt matrici cu dimensiunile 10×30, 30×5, 5×60, calculul (AB)C necesită 10×30×5 + 10×5×60 = 4500 de înmulțiri, în timp ce calculul A(BC) necesită 30×5×60 + 10×30×60 = 27 000 de înmulțiri.

Au fost concepuți algoritmi pentru alegerea ordinii optime de efectuare a produselor, adică printr-un număr minim de operații. Când numărul n de matrici crește, s-a demonstrat că alegerea ordinii optime are o complexitate de  

Alte tipuri de produse ale matricelor

modificare

Înmulțirea „standard” a matricilor prezentată în articolul de față este singurul mod de înmulțire al matricilor studiat în învățământul preuniversitar din România.[16] Însă există și alte tipuri de produse de matrici:

  1. ^ Anca Ignat, Calcul numeric Arhivat în , la Wayback Machine. (curs 2, 2022, p. 2), Universitatea „Alexandru Ioan Cuza” din Iași, accesat 2023-06-13
  2. ^ a b en Nykamp, Duane. „Multiplying matrices and vectors”. Math Insight. Accesat în . 
  3. ^ en O'Connor, John J.; Robertson, Edmund F., „Jacques Philippe Marie Binet”, MacTutor History of Mathematics archive, University of St Andrews .
  4. ^ en Lerner, Rita G.; Trigg, G. L. (). Encyclopaedia of Physics (ed. 2nd). VHC publishers. ISBN 978-3-527-26954-9. 
  5. ^ en Parker, C. B. (). McGraw Hill Encyclopaedia of Physics  (ed. 2nd). ISBN 978-0-07-051400-3. 
  6. ^ en Lipschutz, S.; Lipson, M. (). Linear Algebra. Schaum's Outlines (ed. 4th). McGraw Hill (USA). pp. 30–31. ISBN 978-0-07-154352-1. 
  7. ^ en Riley, K. F.; Hobson, M. P.; Bence, S. J. (). Mathematical methods for physics and engineering . Cambridge University Press. ISBN 978-0-521-86153-3. 
  8. ^ en Adams, R. A. (). Calculus, A Complete Course (ed. 3rd). Addison Wesley. p. 627. ISBN 0-201-82823-5. 
  9. ^ en Horn, Johnson (). Matrix Analysis (ed. 2nd). Cambridge University Press. p. 6. ISBN 978-0-521-54823-6. 
  10. ^ de Peter Stingl (). Mathematik für Fachhochschulen – Technik und Informatik (ed. 5th). München: Carl Hanser Verlag. ISBN 3-446-18668-9.  Here: Exm. 5.4.10, pp. 205–206
  11. ^ a b c d en Weisstein, Eric W. „Matrix Multiplication”. mathworld.wolfram.com. Accesat în . 
  12. ^ en Lipcshutz, S.; Lipson, M. (). „2”. Linear Algebra. Schaum's Outlines (ed. 4th). McGraw Hill (USA). ISBN 978-0-07-154352-1. 
  13. ^ en Horn, Johnson (). „Chapter 0”. Matrix Analysis (ed. 2nd). Cambridge University Press. ISBN 978-0-521-54823-6. 
  14. ^ Volker Strassen (). „Gaussian elimination is not optimal”. Numerische Mathematik. 13 (4): 354–356. doi:10.1007/BF02165411. 
  15. ^ Alman, Josh; Williams, Virginia Vassilevska (), „A Refined Laser Method and Faster Matrix Multiplication”, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), arXiv:2010.05846  
  16. ^ Burtea, Marius; Burtea, Georgeta (). Carminis, ed. Matematică: Manual pentru clasa a XI-a (PDF). Pitești. pp. 22–26, accesat 2023–03–18. ISBN 978-973-123-417-5. Arhivat din original (PDF) la . Accesat în . 

Bibliografie

modificare

Legături externe

modificare