Extraire une base d'une famille
Salut
Je révise (enfin j'appends) l'algèbre linéaire et comme je n'ai jamais rien écouté en cours, je suis en galère dès que je veux faire un truc :-D
Le problème est le suivant : Soit $v_1,\dots,v_m$ une famille de vecteurs de $k^n$ ($k$ un corps). En notant $F= \text{Vect}(v_1,\dots,v_m)$, comment trouver un sous-ensemble $I$ de $\{1,\dots,m\}$ tel que la famille $(v_i)_{i \in I}$ soit une base de $F$ ?
En théorie, je suis certain que $I$ existe, car on a la propriété qui dit : une famille est liée si et seulement si un des vecteurs de la famille s'exprime comme une combinaison linéaire des autres qui permet d'enlever des vecteurs jusqu'à ce que la famille soit libre. Mais en pratique c'est pas trop efficace.
Donc la question, c'est comment je fais le pivot de Gauss ? Si je place les vecteurs en ligne et que je travaille sur des combinaisons linéaires des lignes, je vais obtenir une base de $F$ mais les vecteurs vont changer :-S
Je révise (enfin j'appends) l'algèbre linéaire et comme je n'ai jamais rien écouté en cours, je suis en galère dès que je veux faire un truc :-D
Le problème est le suivant : Soit $v_1,\dots,v_m$ une famille de vecteurs de $k^n$ ($k$ un corps). En notant $F= \text{Vect}(v_1,\dots,v_m)$, comment trouver un sous-ensemble $I$ de $\{1,\dots,m\}$ tel que la famille $(v_i)_{i \in I}$ soit une base de $F$ ?
En théorie, je suis certain que $I$ existe, car on a la propriété qui dit : une famille est liée si et seulement si un des vecteurs de la famille s'exprime comme une combinaison linéaire des autres qui permet d'enlever des vecteurs jusqu'à ce que la famille soit libre. Mais en pratique c'est pas trop efficace.
Donc la question, c'est comment je fais le pivot de Gauss ? Si je place les vecteurs en ligne et que je travaille sur des combinaisons linéaires des lignes, je vais obtenir une base de $F$ mais les vecteurs vont changer :-S
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si les vecteurs sont libres, alors c'est une base.
S'ils sont liés, on en enlève un et il en reste $m-1$. Mais peut-être ne faut-il pas enlever n'importe lequel...
Puis on recommence.
Merci GBZM. Je n'ai pas complètement compris. Je pose $\phi : k^m \to k^n$ donnée par $(x_1,\dots,x_m) \to \sum x_i v_i$. Si je comprends, la procédure que tu proposes donne le noyau $\ker(\phi)$ i.e une base de l'ensemble des relations entre les vecteurs. Donc là je vois que ça rejoint mon problème.
Je détaille un peu plus (histoire de voir un peu mieux), je note $I$ les indices des colonnes des pivots et $J$ le complémentaire de $I$ dans $\{1,\dots,m\}$. Avec ta procédure, on obtient une famille de vecteurs $(\beta_j)_{j \in J}$ de $k^n$ telle que :
1. $\beta_{j,k} = 1$ si $k=j$, $0$ si $k \in J \setminus \{ j\}$.
2. $(x_1,\dots,x_m) \in \ker(\phi)$ si et seulement si $(x_1,\dots,x_m) = \sum_{j \in J} x_j \beta_j$.
De là on montre que pour tout $j \in J$ on a : $v_j \in \text{Vect} (v_i \mid i \in I)$. En effet, on écrit que $\beta_j \in \ker(\phi)$ i.e $$
v_j + \sum_{i \in I} \beta_{j,i} v_i = 0
$$ Ok, ce n'est pas complètement clean, je dois prendre un peu le temps ! Question : Est-ce que tu sais s'il y a quelque chose d'intelligent à dire sur le nombre de sous-ensemble $I$ qui donne une base ?
Un exemple. Donc les vecteurs colonnes Donc $I = \{1,2,3\}$. Et ça veux dire que $v_4$ et $V_5$ sont combinaisons linéaires de $v_1,v_2,v_3$. Donc j'explicite le noyau de $\phi$.
$$
\ker(\phi) = \{ x_4 (10,-5,-6,1,0) +x_5(3/2,-1/2,0,0,1)\mid x_4,x_5 \in k^2 \}
$$
En particulier $x_4=1$ et $x_5 =0$ donne la relation :
$$
10 v_1-5v_2-6v_3+v_4 = 0
$$
Ce qui permet de voir que $v_4 \in \text{Vect}(v_1,v_2,v_3)$. Je vérifie quand même Remarque : je pense que c'est plus clair si on introduit la matrice $P$ telle que $M P$ est échelonnée. Merci, je pense que c'est ok !
[$\LaTeX$ fournit la commande \ker qui gère les espacements. AD]
Quand tu échelonnes selon les lignes, tu multiplies à gauche par une matrice inversible. Ça ne change rien aux vecteurs colonnes, sauf qu'on les réécrit dans une autre base ; la matrice de changement de base est l'inverse de la matrice par laquelle on multiplie à gauche.
Et une fois la matrice échelonnée suivant les lignes, les relations de dépendance linéaires entre les colonnes deviennent évidentes (elles se voient comme un nez au milieu de la figure dans ton exemple).
J'ai beau essayer de m'en souvenir mais rien n'y fait.
Soit P une matrice fixée.
Le sens de "lecture" est de la gauche vers la droite.
- Si on accole une matrice M à gauche de P, M est en contact direct avec toutes les lignes de P, donc M va agir sur les lignes (Il faut imaginer que l'on a écrit les matrices sous forme de tableaux).
- Si on accole une matrice M à droite de P, M est aussi en contact direct avec lignes me direz-vous, mais selon le sens de "lecture" donné, il faut parcourir avant toutes les colonnes de P, en partant de P pour aller jusqu'à M.
Donc M va agir sur les colonnes.
C'est visuel et cela permet de ne plus me tromper (et c'est très personnel comme méthode).
Mais en fait je pense que je fais un peu comme toi pour le nombre de lignes et de colonnes quand on écrit $M \in \text{M}_{n,m}(k)$. En gros, je mets $n$ et $m$ dans le sens de lecture, je pense que ce genre de truc c'est vraiment perso :-D
C'est ce qu'a dû se dire Pierre-Frédéric Sarrus en voyant un déterminant 3$\times$3 :-D
Dans le même ordre d'idée pour trouver la matrice codant une opération élémentaire il suffit d'appliquer cette opération à la matrice identité.
Etant donnée :$(v_1,\dots,v_m)$ une famille libre de vecteurs de $k^n$, déterminer un système d'équations de $F = \text{Vect}(v_1,\dots,v_m)$.
Ici, ça revient à trouver les $x = (x_1,\dots,x_n) \in k^n$ tels qu'il existe $\alpha = (\alpha_1,\dots,\alpha_m) \in k^m$ tel que : $(x_1,\dots,x_m) = \sum \alpha_i v_i$.
J'introduis la matrice $M$ des vecteurs $(v_1,\dots,v_m)$ et la matrice $N = (M \mid I_n)$ obtenu en ajoutant à $M$ la matrice $I_n$. On a $\ker(N) = \{ (\alpha,x) \mid M \alpha^t = x^t \}$.
On échelonne, et comme la famille $(v_1,\dots,v_m)$ est libre on trouve une matrice de la forme :
$$
\begin{pmatrix} I_m & A \\ 0_{n-m} & B \end{pmatrix}
$$
La matrice $B$ nous donne le système d'équations i.e $B x^t = 0$.
Un exemple :
Et donc :
$$
x - 1/2 z -2/3 t = 0 \qquad y -3/4 z -5/6 t = 0
$$
est un système d'équation de $\text{Vect}(v_1,v_2)$ avec $v_1 = (2,3,4,0)$ et $v_2 = (3,4,2,3)$.
"Preuve" :
il s'agit de montrer que les deux ensembles $X = \{ x \mid \exists \alpha \mid N (\alpha,x)^t = 0 \}$ et $Y = \{ x \mid Bx^t = 0\}$ sont égaux. Doubles inclusions.
1. Soit $x \in X$ et $\alpha$ tel que $N (\alpha,x)^t = 0$ en calculant par bloc on a : $B x^t= 0$.
2. Soit $x \in Y$, on pose $\alpha = -A x^t$, et en calculant par bloc on a : $N (\alpha,x)^t = 0$.
Si quelqu'un a un texte qui explique ça de manière complète, je suis preneur, là ce que je raconte n'est pas vraiment clean :-D D'ailleurs GBZM, ça me fait penser à une histoire sur les idéaux d'éliminations (tu avais parlé de ça y'a quelques mois), je me souviens car il y avait une histoire de projection que l'on retrouve ici $\ker(N) \to k^n$ donnée par $(\alpha,x) \mapsto x$. Je vais peut-être finir par comprendre :-D Mais faut d'abord que maîtrise bien le pivot de Gauss !
On range les vecteurs (disons à $n$ coordonnées) en colonnes dans la matrice $M$, on échelonne : $PM=E$ avec $P$ inversible de taille $n$ et $E$ échelonnée selon les lignes. Si $r$ (le rang) est le nombre de lignes non nulles de $E$, les $n-r$ lignes de $P$ à partir de la $r+1$-ème donnent un système d'équations pour le sous-espace engendré.
Sage permet de récupérer une matrice $P$ qui échelonne sans avoir besoin de coller une matrice identité après la matrice $M$.
en conservant les vecteurs nuls qui apparaissent.
Alors
$F_1$ et $F_2$ engendrent le même sous-espace. (En particulier si $F_1$ est génératrice, $F_2$ est génératrice.)
Si $F_1$ est libre, $F_2$ est libre et réciproquement. (En particulier, si $F_2$ contient des vecteurs nuls, $F_1$ n'est pas libre.)
@Soland : tu es plutôt ligne ou colonne ?