Calcul effectif du rang

Plan du chapitre "Matrices et applications linéaires"

Matrices échelonnées

Soit {A=(a_{ij})} une matrice de {\mathcal{M}_{n,p}(\mathbb{K})}. On note {\text{L}_1,\ldots,\text{L}_n} les lignes successives de {A}.
Pour chaque ligne {\text{L}_i} de {A}, soit {d(i)} le plus petit indice {j}, s’il existe, tel que {a_{ij}\ne0}.
On dit que {A} est échelonnée supérieurement s’il existe un entier {r} de {\{0,\ldots,n\}} tel que :

  • pour tout indice {i} inférieur ou égal à {r}, la ligne {\text{L}_i} est non nulle.
  • pour tout indice {i} strictement supérieur à {r}, la ligne {\text{L}_i} est nulle.
  • la suite {d(1),d(2),\ldots,d(r)} est strictement croissante.
Proposition (rang d'une matrice échelonnée)
Avec les notations précédentes, la matrice échelonnée {A} est de rang {r}.
Les {r} coefficients non nuls situés aux positions {(i,d(i))} sont appelés les pivots de {A}.

Ainsi {A=\begin{pmatrix}0&1&3&4&0&1&5\cr 0&0&3&5&1&0&0\cr 0&0&0&0&4&1&2\cr 0&0&0&0&0&9&1\cr 0&0&0&0&0&0&0\end{pmatrix}} est échelonnée (quatre pivots) donc {\text{rg}(A)=4}.

La matrice nulle de {\mathcal{M}_{n,p}(\mathbb{K})} est un cas particulier de matrice échelonnée (avec zéro pivot!).

On définit comme précédemment les matrices “échelonnées inférieurement”. En fait une matrice {A} est échelonnée inférieurement si et seulement si sa transposée est échelonnée supérieurement.

Opérations élémentaires

Définition (opérations élémentaires sur les lignes d'une matrice)
Soit {A} une matrice de {\mathcal{M}_{n,p}(\mathbb{K})}. Notons {\text{L}_1,\text{L}_2,\ldots,\text{L}_n} les lignes de {A}.
On appelle opération élémentaire sur les lignes de {A} l’une des opérations suivantes :

  • multiplier une ligne {\text{L}_i} par un scalaire non nul {\alpha} : on note {\text{L}_i\leftarrow\alpha\text{L}_i}.
  • ajouter à {\text{L}_i} un multiple d’une autre ligne {\text{L}_j} : on note {\text{L}_i\leftarrow \text{L}_i+\beta \text{L}_j}.
  • échanger deux lignes {\text{L}_i} et {\text{L}_j} : on note {\text{L}_i\leftrightarrow \text{L}_j}.

On définit de même les opérations élémentaires sur les colonnes de la matrice {A}.

Elles sont notées : {\text{C}_i\leftarrow\alpha \text{C}_i} (avec {\alpha\ne0}), {\text{C}_i\leftarrow \text{C}_i+\beta \text{C}_j} (avec {j\ne i}), et {\text{C}_i\leftrightarrow \text{C}_j}.

{\vartriangleright} Nécessiter d’utiliser un pivot non nul

Dans les opérations {\text{L}_i\leftarrow\alpha\text{L}_i} et {\text{C}_i\leftarrow\alpha \text{C}_i}, on dit que {\alpha} joue le rôle de “pivot”.
Dans ces deux opérations il est absolument indispensable que {\alpha} soit non nul.

On fera notamment attention au cas où {\alpha} dépend d’un paramètre : pour les valeurs de ce paramètre qui annuleraient {\alpha}, l’opération se traduirait par {\text{L}_i\leftarrow0} ou {\text{C}_i\leftarrow0} et serait “illégale.”

On note {\text{L}_i\leftarrow\alpha\text{L}_i+\beta\text{L}_j} la composée de {\text{L}_i\leftarrow\alpha\text{L}_i} (où {\alpha\ne0}) puis de {\text{L}_i\leftarrow\text{L}_i+\beta\text{L}_j}.

{\vartriangleright} Interprétation matricielle des opérations élémentaires sur les lignes

Proposition (interprétation matricielle d'une opération élémentaire sur les lignes)
Dans {\mathcal{M}_{n,p}(\mathbb{K})} et on considère une opération élémentaire particulière sur les lignes.
Notons {\varphi} l’application qui à {A\in\mathcal{M}_{n,p}(\mathbb{K})} associe sa transformée par cette opération. Alors il existe {Q\in\text{GL}_n(\mathbb{K})} telle que : {\forall\, A\in\mathcal{M}_{n,p}(\mathbb{K}),\;\varphi(A)=QA}.
  • Dans {\mathcal{M}_{n,p}(\mathbb{K})}, toute opération élémentaire sur les lignes équivaut donc à une multiplication à gauche par une certaine matrice inversible {Q} d’ordre {n}. Pour savoir quelle est cette matrice inversible {Q}, il suffit d’appliquer cette opération élémentaire à la matrice identité {I_{n}}.
  • Dans {\mathcal{M}_{n,p}(\mathbb{K})}, on considère une succession donnée d’opérations élémentaires sur les lignes.
    Soit {\varphi} l’application qui à {A\in\mathcal{M}_{n,p}(\mathbb{K})} associe sa transformée par cette succession d’opérations.
    Alors il existe {Q\in\text{GL}_n(\mathbb{K})} telle que : {\forall\, A\in\mathcal{M}_{n}(\mathbb{K}),\;\varphi(A)=QA}.
  • Si on applique à {A} une opération élémentaire sur les lignes (ou une succession de telles opérations), on transforme {A} en une matrice {B} telle que {\text{Ker}(B)=\text{Ker}(A)}.
    Dit familièrement, les opérations élémentaires sur les lignes “conservent le noyau”.

{\vartriangleright} Interprétation matricielle des opérations élémentaires sur les colonnes

Proposition (interprétation matricielle d'une opération élémentaire sur les colonnes)
Dans {\mathcal{M}_{n,p}(\mathbb{K})}, on considère une opération élémentaire particulière sur les colonnes.
Notons {\varphi} l’application qui à {A\in\mathcal{M}_{n,p}(\mathbb{K})} associe sa transformée par cette opération.
Alors il existe {Q\in\text{GL}_p(\mathbb{K})} telle que : {\forall\, A\in\mathcal{M}_{n,p}(\mathbb{K}),\;\varphi(A)=AP}.
  • Dans {\mathcal{M}_{n,p}(\mathbb{K})}, toute opération élémentaire sur les colonnes équivaut donc à une multiplication à droite par une certaine matrice inversible {P} d’ordre {p}. Pour savoir quelle est cette matrice inversible {P}, il suffit d’appliquer cette opération élémentaire à la matrice identité {I_{p}}.
  • Dans {\mathcal{M}_{n,p}(\mathbb{K})}, soit une succession donnée d’opérations élémentaires sur les colonnes.
    Soit {\varphi} l’application qui à {A\in\mathcal{M}_{n,p}(\mathbb{K})} associe sa transformée par cette succession.
    Alors il existe {P\in\text{GL}_p(\mathbb{K})} telle que : {\forall\, A\in\mathcal{M}_{n}(\mathbb{K}),\;\varphi(A)=AP}.
  • En particulier, si on applique à {A} une opération élémentaire sur les colonnes (ou une succession de telles opérations), on transforme {A} en une matrice {B} telle que {\text{Im}(B)=\text{Im}(A)}.
    Dit familièrement, les opérations élémentaires sur les colonnes “conservent l’image”.
Proposition (conservation du rang par des opérations élémentaires)
Toute opération élémentaire (ou toute suite d’opérations élémentaires), sur les lignes et/ou sur les colonnes, transforme une matrice {A} en une matrice de même rang.

Ainsi les opérations élémentaires (sur les colonnes, sur les lignes) “conservent le rang”.

Calcul du rang par la méthode du pivot

Rappelons les trois acceptions du mot “rang” :

  • Soit {E,F} deux espaces vectoriels sur {\mathbb{K}}, avec {\dim(E)=p\ge1}, et {\dim(F)=n\ge1}.
    Soit {f:E\to F} une application linéaire. Le rang de {f} est la dimension de {\text{Im}(f)}.
  • Soit {A} une matrice de {\mathcal{M}_{n,p}(\mathbb{K})}. Alors {\text{rg}(A)=\text{rg}(f)}, où {f:\mathbb{K}^{p}\to \mathbb{K}^{n}} est l’application linéaire canoniquement associée à {A}.

  • Soit {E} un {\mathbb{K}} espace vectoriel, avec {\dim(E)=n}. Soit {(v_{j})_{1\le j\le p}} une famille de {p} vecteurs de {E}.
    Soit {F=\text{Vect}(v)} le sous-espace de {E} engendré par les vecteurs {v_{j}}.
    Le rang de la famille {v=(v_{j})_{1\le j\le p}} est la dimension du sous-espace {F=\text{Vect}(v)}.

En fait, chacune de ces trois définitions se rattache immédiatement aux deux autres :

  • Le rang d’une matrice {A} est celui de la famille de ses vecteurs-colonnes, et celui de la famille de ses vecteurs-lignes, et celui de toute application linéaire susceptible d’être représentée par {A}.
  • Le rang d’une famille de vecteurs de {E} est celui de la matrice des coordonnées de ces vecteurs dans une base {e} quelconque de {E}.
  • Le rang d’une application linéaire {f:E\to F} est le rang de la matrice de {f} dans un couple de bases quelconques ({e} dans {E} et {\varepsilon} dans {F}). C’est aussi le rang de la famille des images des vecteurs d’une base quelconque {e} de {E}.

Finalement tout peut se ramener au calcul du rang d’une matrice.

Proposition (passage à une forme échelonnée supérieure)
Soit {A} une matrice de {\mathcal{M}_{n,p}(\mathbb{K})}. Par une succession bien choisie d’opérations élémentaires sur les lignes, on peut transformer {A} en une matrice échelonnée supérieurement.

Les opérations élémentaires ne modifiant pas le rang de la matrice initiale, on peut ainsi calculer le rang de {A} : c’est celui de la matrice échelonnée finale, c’est-à-dire le nombre de ses pivots non nuls.

Exemple de calcul de rang

On demande de calculer le rang de {A=\begin{pmatrix}1&5&9&13&17\cr3&7&11&15&19\cr2&6&1&0&11\cr1&3&14&21&16\end{pmatrix}}
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Calcul de l’inverse par la méthode du pivot

Proposition (inversion d'une matrice par opérations élémentaires)
Soit {A} une matrice de {\mathcal{M}_n(\mathbb{K})}. Alors {A} est inversible si et seulement si on peut, par une succession bien choisie d’opérations élémentaires sur les lignes, passer de {A} à {\text{I}_n}.
La même succession d’opérations, dans le même ordre, transforme alors {\text{I}_n} en {A^{-1}}.

{\vartriangleright} Principe de la méthode

Soit {A} la matrice de {\mathcal{M}_n(\mathbb{K})} dont on veut calculer l’inverse.
On place {A} et {I_n} côte à côte dans un tableau {(A\mid I_n)} à {n} lignes et {2n} colonnes.

On procède ensuite à une succession d’opérations élémentaires sur les lignes de ce tableau.

Cette suite d’opérations correspond à la multiplication à gauche par une matrice inversible {P}.
On passe donc du tableau {(A\mid I_n)} au tableau {P(A\mid I_n)=(PA\mid PI_n)}.

On choisit la succession d’opérations sur les lignes de {A} qui transforment {A} en {PA=I_n}.
Cela signifie que {P=A^{-1}}, et le tableau final est donc {(I_n\mid A^{-1})}.

{\vartriangleright} Dans la pratique

  • On part de {(A\mid\text{I}_n)=\left(\begin{array}{rrrr|rrrrr}a_{11}&a_{12}&\ldots&a_{1p}&1 &0 &\ldots&0 &0 \cr a_{21}&a_{22}&\ldots&a_{2p}&0 &1 &\ddots&\ddots&0 \cr \vdots&\vdots& &\vdots&\vdots&\ddots&\ddots&\ddots&\vdots\cr \vdots&\vdots& &\vdots&0 &\ddots&\ddots&1 &0 \cr a_{n1}&a_{n2}&\ldots&a_{n,p}&0 &0 &\ldots&0 &1\end{array}\right)}
  • Il y a au moins un coefficient non nul sur la première colonne sinon {A} ne serait pas inversible.
    Au besoin après un échange de deux lignes, on peut supposer {a_{11}\ne0}.

  • On applique les opérations élémentaires : {\text{L}_i\leftarrow a_{11}\text{L}_i-a_{i1}\text{L}_1}, pour {i=2,\ldots,n}.

    Dans cette succession d’opérations, le coefficient non nul {a_{11}} est appelé le pivot.

    Le tableau prend alors la forme suivante : {\left(\begin{array}{rrrr|rrrrr}a_{11}&a_{12}&\ldots&a_{1p}&1 &0 &\ldots&0 &0 \cr 0 &b_{22}&\ldots&b_{2p}&-a_{21}&a_{11} &\ddots&\ddots&0 \cr \vdots&\vdots&\vdots&\vdots&\vdots &0 &\ddots&\ddots&\vdots\cr \vdots&\vdots&\vdots&\vdots&\vdots &\vdots&\ddots&a_{11} &0 \cr 0 &b_{n2}&\ldots&b_{n,p}&-a_{n1}&0 &\ldots&0 &a_{11}\end{array}\right) }

  • La partie gauche du tableau est une matrice qui a le même rang que {A}, et qui est donc inversible.
    Il y a donc au moins un coefficient non nul dans la deuxième colonne et à partir de la deuxième ligne (sinon les deux premières colonnes seraient proportionnelles et {A} ne serait pas inversible).

    Au besoin après échange de {\text{L}_{2}} avec une ligne {\text{L}_{i}} d’indice {i\ge3}, on peut supposer {b_{22}\ne0}.

    Avec le pivot {b_{22}}, on annule les coefficients de la deuxième colonne (sans toucher à {\text{L}_{2}}).

  • On continue ainsi jusqu’à obtenir à la place de {A} une matrice diagonale.
    On termine en divisant chaque ligne par le coefficient diagonal obtenu.
    À la place qu’occupait {\text{I}_n} se trouve maintenant {A^{-1}}.
  • Il n’est pas utile (au contraire) de rendre égaux à {1} les coefficients diagonaux de la moitié gauche du tableau avant d’y avoir obtenu une matrice diagonale, pour éviter d’introduire des coefficients fractionnaires difficiles à manipuler : puisqu’on demande souvent d’inverser des matrices à coefficients entiers, autant garder les coefficients entiers le plus longtemps possible!

{\vartriangleright} Un exercice assez technique

On demande d’inverser {A=\begin{pmatrix}1&1/2&1/3&1/4\cr 1/2&1/3&1/4&1/5\cr 1/3&1/4&1/5&1/6\cr 1/4&1/5&1/6&1/7\end{pmatrix}}.
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

{\vartriangleright} Le même exercice en Python

Reprendre les calculs de l’exercice précédent, mais avec le module numpy de Python
Cliquer ici pour voir (ou cacher) le corrigé
  Pour voir ce contenu, vous devez : 

Page précédente : noyau, image et rang d’une matrice
Page suivante : systèmes linéaires