Sherman-Morrison

La formule de Sherman-Morrison permet de calculer l’inverse d’une matrice modifiée par un terme de rang \(1\), à partir de l’inverse de la matrice de départ. Elle porte le nom des statisticiens américains Jack Sherman et Winifred Morrison, qui l’ont publiée en 1950 pour mettre à jour une matrice inverse après la modification d’un de ses coefficients.

Introduction

Tu sais qu’inverser une matrice demande des calculs longs, que ce soit par le pivot de Gauss ou par la résolution d’un système. Lorsque l’on ne modifie qu’une petite partie d’une matrice déjà inversée, il serait dommage de tout recommencer. La formule de Sherman-Morrison évite ce travail et sert en statistique, en finance ou en optimisation numérique.

Cette notion est hors programme en prépa ECG. Elle peut toutefois apparaître dans un sujet sous la forme d’une matrice \(I_n+uv^T\) ou d’une matrice dont tous les coefficients hors diagonale sont égaux.

Dans cet article, nous allons énoncer la formule, la démontrer, l’appliquer à des exemples, puis expliquer pourquoi elle fonctionne.

Énoncé de la formule

Soient \(A\in\mathcal M_n(\mathbb R)\) inversible, et \(u\), \(v\) deux vecteurs colonnes de \(\mathbb R^n\). La matrice \(uv^T\) est de rang au plus \(1\), tandis que \(v^TA^{-1}u\) est un réel.

Théorème

La matrice \(A+uv^T\) est inversible si et seulement si :

\[
1+v^TA^{-1}u\neq0
\]

et dans ce cas :

\[
(A+uv^T)^{-1}=A^{-1}-\displaystyle \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}
\]

Démonstration

Étape 1 : le cas \(A=I_n\)

On pose \(t=v^Tu\), qui est un réel. Le point clé est que, dans le produit \(uv^Tuv^T\), le facteur central \(v^Tu\) est un nombre que l’on peut sortir :

\[
(uv^T)^2=u(v^Tu)v^T=t\,uv^T
\]

Supposons \(1+t\neq0\). On développe alors :

\[
(I_n+uv^T)\Big(I_n-\displaystyle \frac{uv^T}{1+t}\Big)=I_n+uv^T-\displaystyle \frac{uv^T+t\,uv^T}{1+t}=I_n
\]

Donc \(I_n+uv^T\) est inversible, d’inverse \(I_n-\displaystyle \frac{uv^T}{1+t}\).

Étape 2 : la condition est nécessaire

Supposons \(1+t=0\). Alors \(u\neq0\), sinon on aurait \(t=0\), et :

\[
(I_n+uv^T)u=u+u(v^Tu)=(1+t)u=0
\]

Le vecteur non nul \(u\) est dans le noyau de \(I_n+uv^T\), qui n’est donc pas inversible.

Étape 3 : le cas général

On factorise par \(A\) :

\[
A+uv^T=A\big(I_n+wv^T\big)
\qquad\text{avec}\qquad
w=A^{-1}u
\]

Comme \(A\) est inversible, \(A+uv^T\) est inversible si et seulement si \(I_n+wv^T\) l’est, c’est-à-dire si et seulement si \(1+v^Tw\neq0\). Dans ce cas, l’étape 1 donne :

\[
(A+uv^T)^{-1}=\Big(I_n-\displaystyle \frac{wv^T}{1+v^Tw}\Big)A^{-1}
\]

En remplaçant \(w\) par \(A^{-1}u\), on obtient exactement la formule annoncée.

Un exemple entièrement résolu

On considère :

\[
A=
\begin{pmatrix}
2&0\\
0&1
\end{pmatrix},
\qquad
u=\begin{pmatrix}1\\1\end{pmatrix},
\qquad
v=\begin{pmatrix}1\\0\end{pmatrix}
\]

de sorte que :

\[
A+uv^T=
\begin{pmatrix}
3&0\\
1&1
\end{pmatrix}
\]

On calcule successivement :

\[
A^{-1}u=\begin{pmatrix}\displaystyle \frac{1}{2}\\1\end{pmatrix},
\qquad
v^TA^{-1}=\begin{pmatrix}\displaystyle \frac{1}{2}&0\end{pmatrix},
\qquad
1+v^TA^{-1}u=\displaystyle \frac{3}{2}
\]

puis :

\[
A^{-1}uv^TA^{-1}=
\begin{pmatrix}
\displaystyle \frac{1}{4}&0\\
\displaystyle \frac{1}{2}&0
\end{pmatrix}
\]

La formule donne alors :

\[
(A+uv^T)^{-1}=
\begin{pmatrix}
\displaystyle \frac{1}{2}&0\\
0&1
\end{pmatrix}
-\displaystyle \frac{2}{3}
\begin{pmatrix}
\displaystyle \frac{1}{4}&0\\
\displaystyle \frac{1}{2}&0
\end{pmatrix}
=
\begin{pmatrix}
\displaystyle \frac{1}{3}&0\\
-\displaystyle \frac{1}{3}&1
\end{pmatrix}
\]

On vérifie en effectuant le produit avec \(A+uv^T\) que l’on obtient bien \(I_2\).

Modifier une colonne ou un coefficient

Le choix \(v=E_j\), où \(E_j\) est le \(j\)-ième vecteur de la base canonique, revient à ajouter le vecteur \(u\) à la \(j\)-ième colonne de \(A\). C’est ce qui se passe dans l’exemple précédent, où l’on a ajouté \((1,1)\) à la première colonne.

Si l’on prend de plus \(u=\delta E_i\), on modifie le seul coefficient \(a_{i,j}\), qui devient \(a_{i,j}+\delta\). Le dénominateur de la formule vaut alors :

\[
1+\delta\,E_j^TA^{-1}E_i=1+\delta\,(A^{-1})_{j,i}
\]

La nouvelle matrice est donc inversible si et seulement si \(\delta\,(A^{-1})_{j,i}\neq-1\). C’est précisément le problème qui intéressait Sherman et Morrison : savoir comment l’inverse réagit à la modification d’un seul coefficient.

Cas remarquable : la matrice \(I_n+aJ\)

Notons \(J\) la matrice de taille \(n\) dont tous les coefficients valent \(1\), et \(e\) le vecteur colonne dont toutes les coordonnées valent \(1\). On a \(J=ee^T\) et \(e^Te=n\). L’étape 1 donne, pour \(a\neq-\displaystyle \frac{1}{n}\) :

\[
(I_n+aJ)^{-1}=I_n-\displaystyle \frac{a}{1+na}J
\]

Par exemple, pour \(n=3\) et \(a=1\), on obtient :

\[
(I_3+J)^{-1}=I_3-\displaystyle \frac{1}{4}J
\]

ce que l’on peut vérifier directement à l’aide de la relation \(J^2=3J\). Ce type de matrice, avec des coefficients diagonaux égaux et des coefficients hors diagonale égaux, apparaît souvent dans les sujets, par exemple comme matrice de covariance de variables équicorrélées.

Pourquoi la formule fonctionne

Pour un réel \(x\) tel que \(|x|<1\), on connaît la série géométrique :

\[
\displaystyle \frac{1}{1+x}=1-x+x^2-x^3+\cdots
\]

Appliquons formellement la même idée à \(N=uv^T\). D’après l’étape 1, on a \(N^k=t^{k-1}N\) pour \(k\geq1\). Si \(|t|<1\), on obtient alors :

\[
I_n-N+N^2-N^3+\cdots=I_n-\big(1-t+t^2-\cdots\big)N=I_n-\displaystyle \frac{N}{1+t}
\]

On retrouve l’inverse de l’étape 1. La formule de Sherman-Morrison est donc une série géométrique qui se calcule entièrement, car toutes les puissances de \(N\) sont proportionnelles à \(N\). Elle reste vraie dès que \(1+t\neq0\), même si la série diverge.

En taille \(1\), avec \(A=(a)\), la formule devient \(\displaystyle \frac{1}{a+uv}=\displaystyle \frac{1}{a}-\displaystyle \frac{uv}{a(a+uv)}\), qui n’est qu’une simple mise au même dénominateur.

Intérêt pratique

Inverser une matrice de taille \(n\) par le pivot de Gauss demande de l’ordre de \(n^3\) opérations. La formule de Sherman-Morrison ne fait intervenir que des produits matrice-vecteur et le produit d’une colonne par une ligne, soit de l’ordre de \(n^2\) opérations une fois \(A^{-1}\) connue.

Elle est donc très utilisée lorsque des données arrivent au fil de l’eau. En régression linéaire, ajouter une observation revient à ajouter un terme \(xx^T\) à la matrice \(X^TX\) : la formule met à jour son inverse sans tout recalculer.

Attention aux erreurs classiques

Il ne faut pas confondre \(uv^T\), qui est une matrice de taille \(n\), avec \(v^Tu\), qui est un réel. Au numérateur de la formule figure une matrice, au dénominateur un nombre.

L’ordre des facteurs compte aussi : on écrit \(A^{-1}uv^TA^{-1}\), et non \(uv^TA^{-2}\), car les produits matriciels ne commutent pas.

Enfin, la formule suppose \(A\) inversible. La matrice \(A+uv^T\) peut être inversible sans que \(A\) le soit : par exemple, \(\mathrm{diag}(0,1)+E_1E_1^T=I_2\), où \(E_1\) est le premier vecteur de la base canonique. Dans ce cas, la formule ne s’applique pas.

Comment utiliser la formule dans un exercice ?

Lorsqu’un énoncé fait intervenir une matrice modifiée par un terme de rang \(1\), il est utile :

  • d’écrire la modification sous la forme \(uv^T\), par exemple \(J=ee^T\) ;
  • de vérifier que \(A\) est inversible et calculer \(A^{-1}u\) ;
  • de contrôler que le réel \(1+v^TA^{-1}u\) est non nul ;
  • d’utiliser la relation \((uv^T)^2=(v^Tu)\,uv^T\) pour simplifier les calculs ;
  • de vérifier le résultat en multipliant par \(A+uv^T\).

Conclusion

La formule de Sherman-Morrison affirme que, si \(A\) est inversible et si \(1+v^TA^{-1}u\neq0\) :

\[
(A+uv^T)^{-1}=A^{-1}-\displaystyle \frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u}
\]

Sa démonstration repose sur une seule observation : les puissances d’une matrice de rang \(1\) sont proportionnelles à cette matrice. Elle permet d’inverser rapidement les matrices du type \(I_n+aJ\), et de mettre à jour une inverse sans tout recalculer. Pense à elle dès qu’une matrice de rang \(1\) apparaît dans un calcul d’inverse.

 

Tu peux retrouver le méga-répertoire qui contient toutes les annales de concours et les corrigés. Tu peux également accéder à toutes nos autres ressources mathématiques !