Produit matriciel

Le produit matriciel désigne la multiplication de matrices, initialement appelé la « composition des tableaux »^[1].

Produit matriciel ordinaire

Il s'agit de la façon la plus fréquente de multiplier des matrices entre elles.

En algèbre linéaire, une matrice A de dimensions m lignes et n colonnes (matrice m×n) représente une application linéaire ƒ d'un espace de dimension n vers un espace de dimension m. Une matrice colonne V de n lignes est une matrice n×1, et représente un vecteur v d'un espace vectoriel de dimension n. Le produit A×V représente ƒ(v).

Si A et B représentent respectivement les applications linéaires f et g, alors A×B représente la composition des applications $f\circ g$ .

Cette opération est utilisée notamment en mécanique lors des calculs de torseur statique, ou en informatique pour la matrice d'adjacence d'un graphe.

Le produit de deux matrices ne peut se définir que si le nombre de colonnes de la première matrice est le même que le nombre de lignes de la deuxième matrice, c'est-à-dire lorsqu'elles sont de type compatible.

Si $A=(a_{ij})$ est une matrice de type $(m,n)$ et $B=(b_{ij})$ est une matrice de type $(n,p)$ , alors leur produit, noté $AB=(c_{ij})$ est une matrice de type $(m,p)$ donnée par :

\forall i,j:c_{ij}=\sum _{k=1}^{n}a_{ik}b_{kj}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots +a_{in}b_{nj}

La figure suivante montre comment calculer les coefficients $c_{12}$ et $c_{33}$ de la matrice produit $AB$ si $A$ est une matrice de type $(4,2)$ , et $B$ est une matrice de type $(2,3)$ .

${\color {BrickRed}c_{12}}=\sum _{r=1}^{2}a_{1r}b_{r2}=a_{11}b_{12}+a_{12}b_{22}$

${\color {NavyBlue}c_{33}}=\sum _{r=1}^{2}a_{3r}b_{r3}=a_{31}b_{13}+a_{32}b_{23}$

Exemples

{\begin{pmatrix}1&0\\2&-1\end{pmatrix}}\times {\begin{pmatrix}3&4\\-2&-3\\\end{pmatrix}}

={\begin{pmatrix}(1\times 3+0\times -2)&(1\times 4+0\times -3)\\(2\times 3+-1\times -2)&(2\times 4+-1\times -3)\end{pmatrix}}={\begin{pmatrix}3&4\\8&11\end{pmatrix}}

En général, la multiplication des matrices n'est pas commutative, c'est-à-dire que $AB$ n'est pas égal à $BA$ , comme le montre l'exemple suivant.

{\begin{pmatrix}1&2&0\\4&3&-1\\\end{pmatrix}}\times {\begin{pmatrix}5&1\\2&3\\3&4\\\end{pmatrix}}={\begin{pmatrix}9&7\\23&9\\\end{pmatrix}}

tandis que

{\begin{pmatrix}5&1\\2&3\\3&4\\\end{pmatrix}}\times {\begin{pmatrix}1&2&0\\4&3&-1\\\end{pmatrix}}={\begin{pmatrix}9&13&-1\\14&13&-3\\19&18&-4\\\end{pmatrix}}

Multiplication de matrices par bloc

Si l'on considère les matrices $M=\left({\begin{smallmatrix}A&B\\C&D\end{smallmatrix}}\right)$ et $N=\left({\begin{smallmatrix}A'&B'\\C'&D'\end{smallmatrix}}\right)$ , où $A,A',B,B',C,C'$ et $D,D'$ sont des matrices vérifiant :

Le nombre de colonnes de $A$ et $C$ est égal au nombre de lignes de $A'$ et $B'$
Le nombre de colonnes de $B$ et $D$ est égal au nombre de lignes de $C'$ et $D'$

on a alors l'égalité

MN={\begin{pmatrix}AA'+BC'&AB'+BD'\\CA'+DC'&CB'+DD'\end{pmatrix}}

On remarquera l'analogie entre le produit de matrice par blocs et le produit de deux matrices carrées d'ordre 2.

N.B. : on ne définit pas ainsi une nouvelle forme de multiplication de matrices. Cela correspond simplement à une méthode de calcul du produit matriciel ordinaire pouvant simplifier les calculs.

Produit d'Hadamard

Pour deux matrices de même type, nous avons le produit d'Hadamard ou produit composante par composante. Le produit d'Hadamard de deux matrices $A=(a_{ij})$ et $B=(b_{ij})$ de type $(m,n)$ , noté $A \cdot B = (c ij)$ , est une matrice de type $(m,n)$ donnée par

c_{ij}=a_{ij}\times b_{ij}.

Par exemple :

{\begin{pmatrix}1&3&2\\1&0&0\\1&2&2\end{pmatrix}}\cdot {\begin{pmatrix}0&0&2\\7&5&0\\2&1&1\end{pmatrix}}={\begin{pmatrix}1\times 0&3\times 0&2\times 2\\1\times 7&0\times 5&0\times 0\\1\times 2&2\times 1&2\times 1\end{pmatrix}}={\begin{pmatrix}0&0&4\\7&0&0\\2&2&2\end{pmatrix}}.

Ce produit est une sous-matrice du produit de Kronecker (voir ci-dessous).

Produit de Kronecker

Pour deux matrices arbitraires $A=(a_{ij})$ et $B$ , nous avons le produit tensoriel ou produit de Kronecker $A \otimes B$ qui est défini par

{\begin{pmatrix}a_{11}B&a_{12}B&\cdots &a_{1n}B\\\vdots &\vdots &\ddots &\vdots \\a_{m1}B&a_{m2}B&\cdots &a_{mn}B\end{pmatrix}}

Si $A$ est une matrice de type $(m,n)$ et $B$ est une matrice de type $(p,r)$ alors $A \otimes B$ est une matrice de type $(mp,nr)$ . À nouveau cette multiplication n'est pas commutative.

Par exemple

{\begin{pmatrix}1&2\\3&1\\\end{pmatrix}}\otimes {\begin{pmatrix}0&3\\2&1\\\end{pmatrix}}={\begin{pmatrix}1\times 0&1\times 3&2\times 0&2\times 3\\1\times 2&1\times 1&2\times 2&2\times 1\\3\times 0&3\times 3&1\times 0&1\times 3\\3\times 2&3\times 1&1\times 2&1\times 1\\\end{pmatrix}}={\begin{pmatrix}0&3&0&6\\2&1&4&2\\0&9&0&3\\6&3&2&1\end{pmatrix}}

Si $A$ et $B$ sont les matrices d'applications linéaires $V 1 \to W 1$ et $V 2 \to W 2$ , respectivement, alors $A \otimes B$ représente le produit tensoriel des deux applications, $V 1 \otimes V 2 \to W 1 \otimes W 2$ .

Propriétés communes

Les trois multiplications matricielles précédentes sont associatives

A\times (B\times C)=(A\times B)\times C

distributives par rapport à l'addition :

A\times (B+C)=A\times B+A\times C

(A+B)\times C=A\times C+B\times C

et compatibles avec la multiplication par un scalaire :

c(A\times B)=(cA)\times B=A\times (cB)

Multiplication par un scalaire

La multiplication par un scalaire $r$ d'une matrice $A=(a_{ij})$ donne le produit

rA=(ra_{ij})

Si nous travaillons avec des matrices sur un anneau, alors la multiplication par un scalaire est parfois appelée la multiplication à gauche tandis que la multiplication à droite est définie par :

Ar=(a_{ij}r)

Quand l'anneau fondamental est un anneau commutatif, par exemple, le corps des réels ou des complexes, les deux multiplications sont identiques.

Cependant, si l'anneau n'est pas commutatif, tel que celui des quaternions, alors ils peuvent être différents. Par exemple

i{\begin{pmatrix}i&0\\0&j\\\end{pmatrix}}={\begin{pmatrix}-1&0\\0&k\\\end{pmatrix}}\neq {\begin{pmatrix}-1&0\\0&-k\\\end{pmatrix}}={\begin{pmatrix}i&0\\0&j\\\end{pmatrix}}i

Aspects algorithmiques

Multiplication efficace de deux matrices

Le problème qui consiste, étant donné deux matrices carrées, à les multiplier rapidement, est un problème important en algorithmique. L'algorithme qui découle de la définition a une complexité en temps en $O(n^{3})$ , où $n$ est le nombre de lignes des matrices. Une borne inférieure est $O(n^{2})$ (car chacun des $n^{2}$ coefficients de la matrices doit être écrit). L'exposant optimal pour la complexité est donc compris entre 2 et 3 mais sa valeur exacte est un problème ouvert^[2]. De nombreux algorithmes ont été inventés pour ce problème, citons par exemple l'algorithme de Strassen en $O(n^{2,807})$ , le premier à avoir été découvert^[2], et l'algorithme de Coppersmith-Winograd en $O(n^{2,376})\!\$ ^[3]. En 1993, Bahar et al. ont donné un algorithme de multiplications de matrices pour des matrices représentées symboliquement à l'aide d'une structure de données appelée Algebraic Decision Diagrams (ADD), qui est une généralisation des diagrammes de décision binaire^[4].

Multiplications matricielles enchaînées

On se donne une suite de matrices rectangulaires $\langle A_{1}\dots ,A_{k}\rangle$ et on souhaite en calculer le produit $A_{1,n}=A_{1}\dots A_{k}$ (on suppose que toutes les matrices ont une taille compatible, c'est-à-dire que le produit est bien défini). Le produit matriciel étant associatif, n'importe quel parenthésage du produit donnera le même résultat. Cependant le nombre de multiplications scalaires à effectuer dépend du parenthésage retenu si les matrices sont de tailles différentes.

Ainsi si l'on prend $A={\begin{pmatrix}a_{1}&a_{2}&a_{3}\\\end{pmatrix}}$ , $B={\begin{pmatrix}b_{1}\\b_{2}\\b_{3}\\\end{pmatrix}}$ et $C={\begin{pmatrix}c_{1}&c_{2}&c_{3}\\\end{pmatrix}}$ on a bien $(AB)C$ = $A(BC)$ mais le calcul de $(AB)C$ nécessite 6 multiplications scalaires tandis que celui de $A(BC)$ en nécessite 18.

Il peut donc être utile d'exécuter un algorithme d'optimisation de produit matriciel enchaîné afin d'identifier le parenthésage le plus efficace avant d'effectuer les produits proprement dits.

Vérification d'un produit matriciel

Pour vérifier un produit matriciel, il existe des algorithmes plus efficaces que de simplement le recalculer.

Par exemple l'algorithme de Freivalds est un algorithme probabiliste qui permet de vérifier le résultat d'un produit matriciel en $O(n^{2})$ avec une probabilité d'erreur aussi faible que voulue.

Notes et références

↑ Alain Connes, Triangle de pensées, Édition Odile Jacob, p. 72.
1 2 (en) Thomas H. Cormen, Charles E. Leiserson et Ronald L. Rivest, Introduction à l'algorithmique, Paris, Dunod, 2002, xxix+1146 (ISBN 978-2-10-003922-7, SUDOC 068254024), chap. 28 (« Calcul matriciel »).
↑ Markus Bläser, « Fast Matrix Multiplication », Theory of Computing, Graduate Surveys, vol. 5,‎ 2013, p. 1-60 (lire en ligne).
↑ R. Iris Bahar, Erica A. Frohm, Charles M. Gaona et Gary D. Hachtel, « Algebraic decision diagrams and their applications », ICCAD '93 Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, IEEE Computer Society Press,‎ 7 novembre 1993, p. 188–191 (ISBN 0818644907, lire en ligne, consulté le 9 février 2018)