A Concepts d’algèbre linéaire

Nous ne révisons ici que les principaux résultats qui seront repris en cours de session. Une revue exhaustive des notions d’algèbre linéaire utiles en statistique est donnée par Harville (2008), tandis qu’un résumé plus succinct est disponible dans l’annexe C du livre sur l’apprentissage automatisé machine learning de Bishop (2006). Et bien sûr une recherche sur le web vous mènera à une grande quantité de pages où sont recensées la majorité des définitions et formules utiles dans ce cours … ainsi que plusieurs autres.

A.1 Calcul matriciel

Voici un rappel de quelques identités qui nous seront utiles.

Proposition A.1 Soit \({\bf M}\), \({\bf N}\) et \({\bf P}\) des matrices, \({\bf A}\) et \({\bf B}\) des matrices carrées, \({\bf v}\) et \({\bf w}\) des vecteurs colonne et \({\bf I}_n\) la matrice identité de dimension \(n\times n\).

  1. \(({\bf M}^\top)^\top={\bf M}\), \(({\bf M}{\bf N})^\top={\bf N}^\top{\bf M}^\top\), \(({\bf N}+{\bf M})^\top={\bf N}^\top+{\bf M}^\top\);
  2. \({\bf A}\) est symétrique \(\Leftrightarrow{\bf A}^\top={\bf A}\);
  3. \({\bf A}{\bf A}^\top\) et \({\bf A}^\top{\bf A}\) sont symétriques;
  4. \({\bf P}({\bf M}+{\bf N})={\bf P}{\bf M}+{\bf P}{\bf N}\);
  5. \({\bf A}^{-1}{\bf A}={\bf I}={\bf A}{\bf A}^{-1}\);
  6. \({\bf A}\) est symétrique \(\Leftrightarrow{\bf A}^{-1}\) est symétrique;
  7. \(({\bf A}{\bf B})^{-1}={\bf B}^{-1}{\bf A}^{-1}\);
  8. \(({\bf A}+{\bf M}{\bf B}^{-1}{\bf N})^{-1}={\bf A}^{-1}-{\bf A}^{-1}{\bf M}({\bf B}+{\bf N}{\bf A}^{-1}{\bf M})^{-1}{\bf N}{\bf A}^{-1}\)  (identité de Woodbury, très utile pour réduire le temps de calcul si \({\bf A}\) est diagonale, mais de grande dimension)
  9. \(|{\bf A}^\top|=|{\bf A}|\), \(|{\bf A}^{-1}|=1/|{\bf A}|\), \(|{\bf A}{\bf B}|=|{\bf A}||{\bf B}|\);
  10. Si \({\bf M}\) et \({\bf N}\) sont \(n\times m\), alors \(|{\bf I}_n+{\bf M}{\bf N}^\top|=|{\bf I}_m+{\bf M}^\top{\bf N}|\)  
    (un cas particulier utile: \(|{\bf I}_n+{\bf v}{\bf w}^\top|=|1+{\bf v}^\top{\bf w}|\));
  11. \(\mbox{tr}({\bf A}+{\bf B})=\mbox{tr}({\bf A})+\mbox{tr}({\bf B})\);
  12. \(\mbox{tr}({\bf M}{\bf N})=\mbox{tr}({\bf N}{\bf M})\), \(\mbox{tr}({\bf M}{\bf N}{\bf P})=\mbox{tr}({\bf P}{\bf M}{\bf N})=\mbox{tr}({\bf N}{\bf P}{\bf M})\).

A.2 Décompositions d’une matrice

Il existe plusieurs façons de décomposer une matrice que nous exploiterons tout au long du cours. Avant de procéder, quelques définitions seront utiles.

Définition A.1 Soit \({\bf A}\) une matrice \(n\times n\). Alors

  1. \({\bf A}\) est définie non-négative si \({\bf x}^\top{\bf A}{\bf x}\ge0\) pour tout vecteur \({\bf x}\in\mathbb{R}^n\);
  2. \({\bf A}\) est définie positive si elle est définie non-négative et \({\bf x}^\top{\bf A}{\bf x} = 0\) seulement quand \({\bf x}={\bf 0}\) \(\Leftrightarrow\) si \({\bf x}^\top{\bf A}{\bf x}>0\) pour tout vecteur \({\bf x}\neq0\);
  3. \({\bf A}\) est définie semi-positive si elle est définie non-négative, mais elle n est pas définie positive (donc \({\bf x}^\top{\bf A}{\bf x}\ge0\) pour tout vecteur \({\bf x}\in\mathbb{R}^n\) et il existe \({\bf x}\neq{\bf 0}\) tel que \({\bf x}^\top{\bf A}{\bf x}=0\));
  4. \({\bf A}\) est orthogonale si elle est non-singulière et \({\bf A}^{-1}={\bf A}^\top\).

Une grande proportion des matrices avec lesquelles nous travaillerons seront symétriques et définies non négatives (voire même définies positives). Dans ces situations, des décompositions utiles de ces matrices sont possibles.

Théorème A.1 Soit \({\bf A}\) une matrice carrée symétrique définie positive. Alors il existe une unique décomposition telle que \({\bf A}=\mathrm{L}\mathrm{D}\mathrm{U}\) où \(\mathrm{L}\) est une matrice triangulaire inférieure unitaire,11 \(\mathrm{U}\) est une matrice triangulaire supérieure unitaire et \(\mathrm{D}\) est une matrice diagonale. De plus, les éléments sur la diagonale principale de \(\mathrm{D}\) sont tous positifs.

Un corollaire du théorème A.1 est que dans ce cas il existe une décomposition \({\bf A}=\mathrm{U}^\top\mathrm{D}\mathrm{U}\) où \(\mathrm{D}\) et \(\mathrm{U}\) sont telles que définies dans le théorème. Si on prend \(\mathrm{T}=\mathrm{D}^{1/2}\mathrm{U}\), alors on peut écrire \({\bf A}=\mathrm{T}^\top\mathrm{T}\), et cette dernière décomposition s’appelle décomposition de Choleski. Ces résultats tiennent aussi quand \({\bf A}\) est définie non-négative, mais dans ce cas tout ce que l’on peut dire des éléments sur la diagonale de \(\mathrm{D}\) est qu’ils sont non-négatifs.

A.3 Valeurs et vecteurs propres

Les valeurs et vecteurs propres d’une matrice vont jouer un rôle majeur dans ce cours.

Définition A.2 Soit \({\bf A}\) une matrice carrée. Alors on dit que \(\lambda\) est une valeur propre de \({\bf A}\) s’il existe un vecteur \({\bf x}\neq {\bf 0}\) tel que \[\begin{equation} {\bf A}{\bf x} = \lambda{\bf x}. \end{equation}\]

Le vecteur \({\bf x}\) est appelé vecteur propre correspondant à la valeur propre \(\lambda\) et l’ensemble des nombres réels \(\lambda\) satisfaisant l’équation précédente est appelé spectre de la matrice \({\bf A}\).

La proposition suivante donne quelques propriétés intéressantes des valeurs et vecteurs propres.

Proposition A.2 Soit une matrice carrée \({\bf A}\) de dimension \(n\times n\).

  1. Si \({\bf x}\) est un vecteur propre de \({\bf A}\) correspondant à une valeur propre \(\lambda\), alors \(c{\bf x}\) sera également un vecteur propre de \({\bf A}\) correspondant à \(\lambda\).
  2. Si \({\bf A}\) est symétrique et \({\bf x}_1\) et \({\bf x}_2\) sont des vecteurs propres correspondant à des valeurs propres différentes de \({\bf A}\), alors \({\bf x}_1\) et \({\bf x}_2\) sont orthogonaux, i.e., \({\bf x}_1^\top{\bf x}_2=0\).
  3. Si \({\bf A}\) a comme valeurs propres (réelles, mais pas nécessairement distinctes) \(\lambda_1,\ldots,\lambda_n\), alors \(|{\bf A}|=\prod_{i=1}^n\lambda_i\) et \(\mbox{tr}({\bf A})=\sum_{i=1}^n\lambda_i\).
  4. Si \({\bf A}\) est symétrique, toutes ses valeurs propres sont réelles.
  5. Si \({\bf A}\) est définie non-négative [définie positive] alors toutes ses valeurs propres sont non-négatives [positives].
  6. Une matrice symétrique \({\bf A}\) est définie non-négative [définie positive] si et seulement si toutes ses valeurs propres sont non-négatives [positives].

Avant de définir une décomposition d’une matrice basée sur ses valeurs et vecteurs propres, la définition suivante est utile.

Définition A.3 Une matrice \(n\times n\) carrée \({\bf A}\) est dite diagonalisable (par une matrice \(\mathrm{Q}\)) s’ il existe une matrice carrée \(n\times n\) non singulière \(\mathrm{Q}\) et une matrice \(n\times n\) diagonale \(\mathrm{D}\) telles que

\[\begin{equation}\label{eq:diag} \mathrm{Q}^{-1}{\bf A}\mathrm{Q}=\mathrm{D}\Leftrightarrow {\bf A}=\mathrm{Q}\mathrm{D}\mathrm{Q}^{-1}. \end{equation}\]

Deux résultats particulièrement d’intérêt pour nous suivent.

Théorème A.2 Toute matrice carrée symétrique est diagonalisable par une matrice orthogonale \(\mathrm{Q}\).

Théorème A.3 Soit une matrice \(n\times n\) symétrique \({\bf A}\) et ses \(n\) valeurs propres \(\lambda_1,\ldots,\lambda_n\). Alors il existe une matrice orthogonale \(\mathrm{Q}\) telle que

\[\begin{equation}\label{eq:spect} {\bf A}=\mathrm{Q}\boldsymbol{\Lambda}\mathrm{Q}^\top, \end{equation}\]

où \(\boldsymbol{\Lambda}=\mbox{diag}(\lambda_1,\ldots,\lambda_n)\).

On appelle parfois cette décomposition de la matrice \({\bf A}\) décomposition spectrale ou décomposition en valeurs propres. S’en suit du théorème A.3 que si \({\bf A}\) admet \(n\) valeurs propres positives distinctes (par exemple si \({\bf A}\) est définie positive et de plein rang) et que \(\boldsymbol{\Lambda}\) est telle que définie dans le théorème, alors on peut prendre \(\mathrm{Q}\) comme la matrice dont la \(k\)-ème colonne est le vecteur propre normé correspondant à la \(k\)-ème valeur propre \(\lambda_k\).

Proposition A.3 Soit deux matrices symétriques,

\[A \quad \mbox{et} \quad M,\]

pour déterminer le vecteur \(u\) tel que \[u^\top A u \mbox{ est maximal},\]

sachant que \(u^\top Mu = 1\), il faut prendre \[u = \mbox{vecteur propre de } M^{-1}A\] associé à \[\lambda = \mbox{valeur propre maximale de } M^{-1} A.\] On obtient ainsi \[u^\top A u = u^\top \lambda Mu = \lambda (u^\top M u) = \lambda.\]

On peut démonter la proposition A.3 ainsi: Il faut maximiser \(u^\top A u-\lambda(u^\top Mu-1)\), où \(\lambda\) est un multiplicateur de Lagrange. En dérivant par rapport à \(u\) et en égalisant cette dérivée à zéro, on obtient \(Au=\lambda Mu.\) En multipliant chaque élément de l’égalité par \(u^\top\), on obtient bel et bien \(\lambda=u^\top Au\), qui est le terme à maximiser.

Par contre, si nous multiplions chaque élément de l’égalité par \(M^{-1}\), nous avons \[M^{-1}Au=\lambda u,\] ce qui signifie que \(\lambda\) est bel et bien une valeur propre de \(M^{-1}A\) et que \(u\) est le vecteur propre qui lui est associé.

A.4 Valeurs singulières

Dans certaines situations, nous ne travaillerons pas avec des matrices carrées ou des matrices non singulières. Dans ces cas, la décomposition spectrale du théorème A.3 n’est pas définie. Une décomposition plus générale appelée décomposition en valeurs singulières peut être une alternative intéressante.

Théorème A.4 Soit \({\bf M}\) une matrice {} de dimension \(m\times n\) et de rang \(r\). Alors il existe des matrices orthogonales carrées \(\mathrm{U}\) de dimension \(m\times m\) et \(\mathrm{V}\) de dimension \(n\times n\) telles que

\[\begin{equation}\label{eq:svd} {\bf M} = \mathrm{U}\mathrm{D}\mathrm{V}^\top, \end{equation}\]

où \(\mathrm{D}\) est une matrice \(m\times n\) telle que \([\mathrm{D}]_{i,i}=s_i>0\), \(i=1,\ldots,r\) et dont tous les autres éléments sont égaux à zéro.

Les valeurs \(s_1,\ldots,s_r\) du théorème A.4 sont appelées valeurs singulières de \({\bf M}\). Parfois on appelle les colonnes de la matrice \(\mathrm{U}\) vecteurs singuliers à gauche, alors que les colonnes de la matrice \(\mathrm{V}\) sont les vecteurs singuliers à droite. Quelques faits intéressants …

  1. Les éléments non nuls de la matrice \(\mathrm{D}\) (i.e., les valeurs singulières non nulles de \({\bf M}\)) sont les racines carrées des valeurs propres non nulles des matrices \({\bf M}{\bf M}^\top\) et \({\bf M}^\top{\bf M}\).
  2. Les colonnes de \(\mathrm{U}\) sont des vecteurs propres de \({\bf M}{\bf M}^\top\).
  3. Les colonnes de \(\mathrm{V}\) sont des vecteurs propres de \({\bf M}^\top{\bf M}\).
  4. Si \(m=n\) et \({\bf M}\) est définie non-négative, alors \(\mathrm{V}=\mathrm{U}\) et la décomposition en valeurs singulières est également une décomposition spectrale (ou décomposition en valeurs propres).

A.5 Dérivées de vecteurs ou matrices

Nous devrons parfois calculer des dérivées qui impliquent des vecteurs ou matrices.

Proposition A.4 Quelques résultats en vrac sur les dérivées impliquant des vecteurs ou matrices.

  1. \(\partial {\bf w}^\top{\bf v}/\partial{\bf v} = {\bf w}\), où l’élément en position \(i\) ici représente la dérivée de \({\bf w}^\top{\bf v}\) par rapport à \([{\bf v}]_i\).
  2. \(\partial {\bf v}^\top{\bf A}{\bf v}/\partial{\bf v}=({\bf A}+{\bf A}^\top){\bf v}\).
  3. \(\partial ({\bf A}{\bf B})/\partial u = (\partial{\bf A}/\partial u){\bf B}+{\bf A}(\partial{\bf B}/\partial u)\), où l'’élément en position \((i,j)\) ici représente la dérivée de \([{\bf A}{\bf B}]_{ij}\) par rapport à \(u\).
  4. \(\partial ({\bf A}^{-1})/\partial u = -{\bf A}^{-1}(\partial{\bf A}/\partial u){\bf A}^{-1}\).
  5. \(\partial \ln |{\bf A}|/\partial x = \mbox{tr}({\bf A}^{-1}\partial{\bf A}/\partial x)\).
  6. \(\partial \mbox{tr}({\bf A}{\bf B})/\partial {\bf A}={\bf B}^\top\), où l’élément en position \((i,j)\) ici représente la dérivée de \(\mbox{tr}({\bf A}{\bf B})\) par rapport à \([{\bf A}]_{ij}\).
  7. \(\partial \mbox{tr}({\bf A}{\bf B}{\bf A}^\top)/\partial {\bf A}={\bf A}({\bf B}+{\bf B}^\top)\).
  8. \(\partial \ln |{\bf A}|/\partial {\bf A} = ({\bf A}^{-1})^\top\).

Références

Bishop, Christopher M. 2006. Pattern Recognition and Machine Learning. New York: Wiley.

Harville, David A. 2008. Matrix Algebra from a Statistician’s Perspective. New York: Springer.