\documentclass{article}
%
% linalg.ltx
% Francois Maltey - janvier 2008
%
\usepackage[utf-8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[french]{babel}
\usepackage{xspace}
\newbox\thina
\newcommand{\axiom}
{\setbox\thina\hbox{.}\wd\thina=0mmax\raise-0.2em\box\thina{}iom\xspace}
\newcommand{\Axiom}
{\setbox\thina\hbox{.}\wd\thina=0mmAx\raise-0.2em\box\thina{}iom\xspace}
\binoppenalty=20000
\relpenalty=20000
\begin{document}
\title{Compléments d'algèbre linéaire}
\author{Fran\c{c}ois Maltey}
\maketitle
\tableofcontents
\begin{abstract}
De nombreuses manipulations d'algèbre linéaire en dimension finie se
traduisent par des systèmes d'équations linéaires.
La résolution de ceux-ci peut s'effectuer en éliminant
successivement les variables dans les équations
par la méthode du pivot de Gauss,
et correspond en fait à des opérations sur les lignes de la matrice
du système pour s'approcher d'une matrice triangulaire.
\par
La fonction \verb!rowEchelon! d'\axiom effectue cette transformation. Elle est
implantée dans le fichier \verb!matfuns.spad!. Les commandes
\verb!nullSpace!, \verb!rank! et \verb!nullity!
de recherche du noyau et du rang d'une matrice en dépendent ;
il en est de même des fonctions \verb!solve! et \verb!particularSolution! de
résolution des systèmes linéaires.
\par
Ce document présente la fonction \verb!rowEchelon! et les fonctions
associées pour les appliquer ensuite à la construction d'une base
d'un sous-espace vectoriel engendré par une famille de vecteurs,
et à la celle de bases de sommes et d'intersections de tels sous-espaces.
\end{abstract}
%%
%%
\section{Les fonctions d'\axiom}
\subsection{Matrice \'echelonn\'ee}
Cette présentation se limite aux espaces vectoriels sur
un corps~$\mathbb K$. Il est possible d'adapter cette théorie aux
modules sur des anneaux principaux.
\Axiom implante les deux méthodes.
\par
L'argument $A\in{\cal M}_{m,n}(\mathbb K)$
de la fonction \verb!rowEchelon!
est une matrice à $m \in {\mathbb N}^*$ lignes et $n \in {\mathbb N}^*$
colonnes ;
son résultat est une matrice échelonnée
$B$ de même type obtenue à partir d'opérations
élémentaires sur les lignes.
\par
Plus précisément ces
trois conditions définissent les matrices écholonnées :
\begin{itemize}
\item
Les lignes de coefficients tous nuls sont en dessous
des lignes non nulles ;
\item
le coefficient non nul le plus à gauche d'une ligne est strictement à droite
du coefficient non nul le plus à gauche de la ligne précédente ;
\item
et, pour chaque ligne le coefficient non nul le plus à gauche est $1$.
\end{itemize}
\par
Ces matrices sont des exemples de matrices échelonnées.
\begin{displaymath}
\begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}
\qquad \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}
\qquad \begin{pmatrix} 1 & 2 \\ 0 & 0 \end{pmatrix}
\qquad
\begin{pmatrix}
0 & \underline 1 & 2 & 1 & 0 & 1 \\
0 & 0 & \underline 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & \underline 1 & 3 \\
0 & 0 & 0 & 0 & 0 & 0
\end{pmatrix}
\end{displaymath}
\par
La première colonne d'une matrice échelonnée est donc le vecteur nul
ou le premier vecteur de la base canonique de $\mathbb K^m$.
Une matrice triangulaire supérieure dont les termes diagonaux
sont unitaires est une matrice échelonnée. La matrice nulle est aussi une
matrice échelonnée.
\par
La commande \verb!rowEchelon A! d'\axiom transforme la matrice initiale
$A$ en une matrice échelonnée $B$ par
des opérations élémentaires sur les lignes de $A$ :
\begin{itemize}
\item
échange de deux lignes, ou
\item
ajout d'une combinaison linéaire des autres lignes à une ligne donnée.
\end{itemize}
Ces opérations sur les lignes de $A$
placent les termes nécessairement
nuls de la matrice $B$, et multiplient éventuellement une ligne dont le
premier terme non nul est $b \neq 0$ par
par $1/b$ de façon à obtenir un coefficient unitaire.
Toute matrice de ${\cal M}_{m,n}(\mathbb K)$ peut être réduite en une matrice
échelonnée et appliquant la méthode classique d'élimination des variables
par le pivot de Gauss, quitte a permuter deux lignes.
\par
Ensuite \axiom poursuit le processus pour placer
des coefficients nuls au dessus des principaux coefficients unitaires.
Dans cet exemple les coefficients sont de type
\verb!Fraction Integer! pour que le corps soit ${\mathbb K} = {\mathbb Q}$ :
\begin{verbatim}
MFI := Matrix Fraction Integer
A1 : MFI := matrix @[[2,3,3],[3,4,5],[4,5,6]]
A2 : MFI := matrix @[[2,3,4],[3,4,5],[4,5,6]]
[rowEchelon A1, rowEchelon A2]
\end{verbatim}
\begin{verbatim}
     +1  0  0+   +1  0  - 1+
   [ |0  1  0| , |0  1   2 | ]
     +0  0  1+   +0  0   0 +  Type: List Matrix Fraction Integer
\end{verbatim}
\par
La transformation d'\axiom est donc plus complète que la simple définition
des matrices échelonnées puisque les colonnes principales correspondent
aux vecteurs de la base canonique. \Axiom transforme la
matrice échelonnée précédente en une autre matrice échelonnée :
\begin{verbatim}
A3 : MFI := matrix
       @[[0,1,2,1,0,1],[0,0,1,0,0,1],[0,0,0,0,1,3],[0,0,0,0,0,0]]
[A3, rowEchelon A3]
\end{verbatim}
\begin{verbatim}
         +0  1  2  1  0  1+   +0  1  0  1  0  - 1+
       [ |0  0  1  0  0  1| , |0  0  1  0  0   1 | ]
         |0  0  0  0  1  3|   |0  0  0  0  1   3 |
         +0  0  0  0  0  0+   +0  0  0  0  0   0 +
\end{verbatim}
\par
Réduire une matrice $A$
consiste donc à multiplier la matrice par une matrice
$P \in \mathcal{GL}_m(\mathbb K)$ inversible décrivant ces opérations sur
les lignes ; la matrice réduite est $B=PA$.
En particulier les matrices $A$ et $B$ sont de même rang, et les
noyaux des applications linéaires associées aux matrices $A$ et $PA$
sont égaux.
\par
Le système \axiom
applique algébriquement cette méthode sans comparer l'ordre
de grandeur des coefficients au contraire des méthodes numériques qui
privilégient les plus grands termes en valeur absolue pour
améliorer le conditionnemeent du système et diminuer l'influence des
erreurs d'arrondis.
\par
Les divisions intervenant lorsque les coefficients sont dans un corps
sont remplacées par la recherche des facteurs communs dans les anneaux
principaux.
%%
%%
\subsection{Noyau d'une application linéaire et rang}
L'algèbre linéaire identifie généralement l'application linéaire
$f : \mathbb K^n \mapsto \mathbb K^m$ et la matrice
$A \in {\cal M}_{m,n}(\mathbb K)$ par
$f(X)=AX$.
\par
Un vecteur $X \in \ker f$ du noyau de $f$ est caractérisé par
$f(X)=\mathbf 0$. Les opérations sur les lignes de $A$ appliquées
par \verb!rowEchelon! laissent invariant les vecteurs du noyau,
d'où l'abus de notation $\ker f =\ker A = \ker B$ :

\begin{displaymath}
P \in {\cal GL}_m({\mathbb K})
\qquad X \in \ker f
\Longleftrightarrow AX={\mathbf 0}
\Longleftrightarrow PAX={\mathbf 0}
\end{displaymath}
\par
La construction d'une base du noyau revient à rechercher
des relations de dépendance linéaire
sur les vecteurs-colonne de la matrice échelonnée. La structure même
de la matrice échelonnée calculée par \axiom énumère une base du noyau
à partir des coefficients des vecteurs-colonne
qui n'introduisent pas un coefficient unitaire
sur une ligne ou une autre.
\par
La commande \verb!nullSpace A! détermine de cette manière
une base du noyau de l'application
linéaire $f:X \mapsto AX$ définie par la matrice $A$.
Cependant, lorsque le noyau est le sous-espace nul, \axiom renvoie la liste
constituée du vecteur nul et non la liste vide qui correspond à la base du
sous-espace nul :
\begin{verbatim}
rowEchelon A2
nullSpace rowEchelon A2
nullSpace A2
\end{verbatim}
\begin{verbatim}
        +1  0  - 1+
        |0  1   2 |
        +0  0   0 +                Type: Matrix Fraction Integer
        @[[1,- 2,1]]           Type: List Vector Fraction Integer
        @[[1,- 2,1]]           Type: List Vector Fraction Integer
\end{verbatim}
\par
Une base de ce noyau est réduite à un seul vecteur.
La colonne $C_3$ de matrice échelonnée $B_2$ associée à la matrice $A_2$
est effectivement un vecteur du noyau, d'où ces
produits matriciels qu'\axiom vérifie par
\verb!A2*vector[1,-2,1]! :
\begin{displaymath}
B_2 = [C_1,C_2,C_3] =
\begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{pmatrix}
\qquad C_3=-C_1+2C_2 \qquad C_1-2C_2+C_3=\mathbf 0
\end{displaymath}
\begin{displaymath}
 \begin{pmatrix} 1 & 0 & -1 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{pmatrix}
 \begin{pmatrix} 1 \\-2 \\ 1 \end{pmatrix}
= \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}
\qquad
 \begin{pmatrix} 2 & 3 & 4 \\ 3 & 4 & 5 \\ 4 & 5 & 6 \end{pmatrix}
 \begin{pmatrix} 1 \\-2 \\ 1 \end{pmatrix}
= \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}
\end{displaymath}
\par
Les résultats sont comparables avec la matrice $A_3$ ; les colonnes
d'indice un, quatre et six décrivent ainsi une base du noyau :
\begin{verbatim}
rowEchelon A3
nullSpace A3
\end{verbatim}
\begin{verbatim}
        +0  1  0  1  0  - 1+
        |0  0  1  0  0   1 |
        |0  0  0  0  1   3 |
        +0  0  0  0  0   0 +       Type: Matrix Fraction Integer
        @[[1,0,0,0,0,0],[0,- 1,0,1,0,0],[0,1,- 1,0,- 3,1]]
\end{verbatim}
\par
Les vecteurs obtenus sont bien des vecteurs du noyau ; la méthode
est similaire pour montrer que ces vecteurs engendrent le noyau
et forment une famille libre. Ils constituent ainsi une base du noyau.
\par
La commande \verb!rank A! calcule le rang d'une matrice $A$ en
dénombrant les lignes non nulles de la matrice échelonnée associée à $A$.
La commande \verb!nullity A! renvoie la dimension du noyau $\dim \ker A$
de l'application linéaire $f$ associée à la matrice en appliquant le théorème
du rang à $f$ :
\begin{verbatim}
[rank A1, rank A2, rank A3]
[nullity A1, nullity A2, nullity A3]
\end{verbatim}
\begin{verbatim}
        [3,2,3]                       Type: List PositiveInteger
        [0,1,3]                       Type: List PositiveInteger
\end{verbatim}
%%
%%
\subsection{Résolution d'un système linéaire}
Les commandes \verb!particularSolution(A,b)! et \verb!solve(A,b)! résolvent
l'équa\-tion matricielle $AX=b$ d'inconnue $X \in {\mathbb K}^n$
où $A \in {\cal M}_{m,n} ({\mathbb K})$
et $b \in {\mathbb K}^m$.
\par
L'ensemble des solutions d'une telle équation est soit l'ensemble vide,
soit un sous-espace affine de la forme $U + \ker A$ où $U \in {\mathbb K}^m$
est une solution particulière.
\par
Le résultat de \verb!particularSolution(A,b)! et de \verb!solve(A,b)!
est \verb!"failed"! si le système l'a pas de solution.
La première commande renvoie sinon une solution, et la seconde
décrit l'ensemble des solutions sous la forme d'un
enregistrement dont le premier terme est une solution particulière, et le
second une base du noyau.
\par
La méthode de résolution consiste à concaténer le vecteur $b$ à
droite de la matrice $A$ du système, puis à étudier la matrice
échelonnée associée.
Le système n'a pas de solution si cette dernière colonne n'est pas une
combinaison linéaire des précédentes, et a au moins une solution sinon.
Ce critère se lit directement sur la matrice échelonnée :
\begin{displaymath}
\begin{cases} x + 2y = 5 \\2x+y=4 \\ {\phantom 2}x+y=3\end{cases}
\qquad
\begin{cases} x + 2y = 5 \\2x+y=5 \\ {\phantom 2}x+y=3\end{cases}
\end{displaymath}
La matrice~$A$ de cet exemple décrit le système précédent de trois équations
à deux inconnues :
\begin{verbatim}
A : MFI := matrix @[[1,2],[2,1],[1,1]]
b1 : Vector Fraction Integer := vector [5,4,3]
b2 : Vector Fraction Integer := vector [5,4,4]
[rowEchelon horizConcat (A, b1), rowEchelon horizConcat (A, b2)]
particularSolution (A, b1)
particularSolution (A, b2)
\end{verbatim}
\begin{verbatim}
         +1  0  1+   +1  0  0+
       [ |0  1  2| , |0  1  0| ]
         +0  0  0+   +0  0  1+
       [1,2]       Type: Union(Vector Fraction Integer,"failed")
       "failed"    Type: Union(Vector Fraction Integer,"failed")
\end{verbatim}
La dernière colonne de la première matrice échelonnée
détermine le couple-solution $(x,y)=(1,2)$,
et celle de la seconde matrice justifie l'absence de solution du système.
%%
%%
%%
%%
\section{Recherche de bases}
\subsection{Base d'un sous-espace}
La fonction \verb!basis! ci-dessous extrait une base du sous-espace
vectoriel $F$ engendré par les colonnes d'une matrice $A$.
Les colonnes de $A$ génératrices de $F$ sont les mêmes que
les colonnes génératrices de la matrice échelonnée
\verb!rowEchelon A!.
Ces vecteurs sont ceux ayant un indice
$1$ sur une nouvelle ligne dans la matrice échelonnée.
\begin{verbatim}
basis mat ==
 mat2 := rowEchelon mat
 basis := []
 indrow : Integer := 1
 n : Integer := ncols mat
 m : Integer := nrows mat
 for k in 1..n repeat
   if indrow <= m and mat2.(indrow,k) ~= 0
     then
       basis := cons (column (mat, k), basis)
       indrow := indrow + 1
 reverse basis
\end{verbatim}
La dernière commande \verb!reverse! conserve l'ordre des vecteurs
extraits de la famille génératrice pour construire la base.
Les matrices échelonnées de $A_2$ et de $A_3$ précédemment calculées
justifient quels vecteurs interviennent dans les bases associées
à ces sous-espaces :
\begin{verbatim}
rowEchelon A2
basis A2
rowEchelon A3
basis A3
\end{verbatim}
\begin{verbatim}
        @[[2,3,4],[3,4,5]]
        @[[1,0,0,0],[2,1,0,0],[0,0,1,0]]
\end{verbatim}
La fonction \verb!basisLV! opère sur des listes de vecteurs
et construit la matrice associée quand les vecteurs sont de
même taille, et provoque une erreur sinon.
\begin{verbatim}
sameSizeVectors? Lb ==
 null Lb => true
 n := #(first Lb)
 every? (t +-> #t=n, rest Lb)
\end{verbatim}
\begin{verbatim}
basisLV Lv ==
 null Lv => []
 not (sameSizeVectors? Lv)
   => error "vectors have not the same size"
 basis transpose matrix Lv
\end{verbatim}
%%
%%
\subsection{Base d'une somme de sous-espaces}
Une base d'une somme de sous-espaces peut être extraite
à partir de la réunion des familles génératrices des sous-espaces.
\begin{verbatim}
sumBasis2 (Lv1, Lv2) == basisLV concat (Lv1, Lv2)
sumBasisLLV LLv == basisLV concat LLv
\end{verbatim}
La fonction \verb!sumBasis2! extrait une base de la réunion de deux
familles géné\-ra\-trices de vecteurs.
La fonction \verb!sumBasisLLV! extrait une base d'une somme de sous-espaces
dont les familles génératrices de vecteurs sont énumérées dans
la liste argument.
%%
%%
\subsection{Base d'une intersection de sous-espaces}
\begin{verbatim}
kernelMat mat ==
 lv := nullSpace mat
 #lv = 1 and lv.1 = 0*lv.1 => []
 lv
\end{verbatim}
La fonction \verb!kernelMat! reprend la fonction \verb!nullSpace!
mais renvoie dans tous les cas une base du noyau, et, au contraire de
\verb!nullSpace!, la liste vide lorsque le noyau est le sous-espace nul.
\par
La fonction \verb!subvector! extrait un sous-vecteur d'un vecteur et
\verb!linearVector! évalue une combinaison linéaire de vecteurs en
fonction de ses coefficients, à la façon d'un produit matriciel.
Ces fonctions interviennent ensuite dans la recherche d'une base
d'une intersection de sous-espaces vectoriels :
\begin{verbatim}
subVector (v, a, b) == vector (elt (entries v, a..b))
linearVector (t, Lv) == reduce (+, [t.i*Lv.i for i in 1..#t])
\end{verbatim}
La fonction suivante \verb!intBasis2! construit une base de l'intersection
de deux sous-espaces vectoriels à partir de leurs bases affectées
dans les variables \verb!Lb1! et \verb!Lb2!.
\par
Dans le cas où ni l'un ni l'autre des sous-espaces n'est
réduit au vecteur nul, les vecteurs de l'intersection sont construits
à partir de relations de dépendance linéaire de vecteurs des bases des
deux sous-espaces. Décomposer cette somme sur chaque sous-espace aboutit
donc à un vecteur de l'intersection.
\par
Les coefficients de cette dépendance linéaire sont
obtenus à partir des vecteurs d'une base du noyau de la matrice
dont les colonnes sont les vecteurs des bases de ces deux sous-espaces.
\begin{verbatim}
intBasis2 (Lv1, Lv2) ==
 Lb1 := basisLV Lv1
 Lb2 := basisLV Lv2
 null Lb1 => []
 null Lb2 => []
 #(first Lb1) ~= #(first Lb2)
   => error "vectors have not the same size"
 lkv := kernelMat transpose matrix concat (Lb2, Lb1)
 d1 := #Lb1
 d2 := #Lb2
 LcoeffV1 := [subVector (kv, d2+1, d1+d2) for kv in lkv]
 [linearVector (cc, Lb1) for cc in LcoeffV1]
\end{verbatim}
L'exemple suivant détaille la recherche d'une base de l'intersection
de deux plans de l'espace :
\begin{verbatim}
B1:List Vector Fraction Integer := [vector[1,2,2], vector[1,1,2]]
B2:List Vector Fraction Integer := [vector[-1,0,1],vector[1,1,1]]
intBasis2 (B1, B2)
\end{verbatim}
\begin{verbatim}
         @[[2,3,4]]            Type: List Vector Fraction Integer
\end{verbatim}
L'intersection des deux plans est bien une droite vectorielle.
La matrice intermédiaire et son noyau sont ceux-ci :
\begin{verbatim}
M := transpose (matrix concat (B1, B2))::MFI
nullSpace M
\end{verbatim}
\begin{verbatim}
         +1  1  - 1  1+
         |2  1   0   1|
         +2  2   1   1+            Type: Matrix Fraction Integer
             1   1 1
         @[[- -,- -,-,1]]
             3   3 3          Type: List Vector Fraction Integer
\end{verbatim}
Le noyau ne comporte qu'un vecteur d'où ces égalités :
\begin{displaymath}
{\mathbf u}_1 \begin{pmatrix} 1 \\ 2 \\ 2 \end{pmatrix}
{\mathbf u}_2 \begin{pmatrix} 1 \\ 1 \\ 2 \end{pmatrix}
{\mathbf v}_1 \begin{pmatrix} -1 \\ 0 \\ 1 \end{pmatrix}
{\mathbf v}_2 \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}
\quad
- \frac 1 3 {\mathbf u}_1 - \frac 1 3 {\mathbf u}_2 +
\frac 1 3 {\mathbf u}_3 + {\mathbf u}_4 = \mathbf 0
\end{displaymath}
\begin{displaymath}
 \frac 1 3 {\mathbf u}_1 + \frac 1 3 {\mathbf u}_2 =
 \frac 1 3 {\mathbf u}_3 + {\mathbf u}_4
= \begin{pmatrix} 2/3 \\ 1 \\ 4/3 \end{pmatrix}
\end{displaymath}
Ce dernier vecteur est proportionnel à celui déterminé par \axiom.
\par
Cette méthode décrit donc une construction des vecteurs de l'intersection
de deux sous-espaces ;
en outre ces vecteurs forment une famille libre de vecteurs et réciproquement
tous les vecteurs de l'intersection sont une combinaison linéaire de ceux-ci.
\par
Cette dernière fonction \verb!intBasisLLV!
construit une base d'une intersection
d'une famille quelconques de sous-espaces.
\begin{verbatim}
intBasisLLV LLv ==
 #LLv = 0 => error "no space to intersect"
 #LLv = 1 => LLv.1
 intBasis2 (LLv.1, intBasisLLV rest LLv)
\end{verbatim}
\par
L'exemple suivant détermine de deux façons différentes le sous-espace
orthogonal à une famille de quatre vecteurs de ${\mathbb K}^6$.
L'égalité des deux bases résultats est une condition suffisante
d'égalité des deux sous-espaces, de dimension trois dans ce cas :
\begin{verbatim}
U1 : Vector Fraction Integer := [1,2,1,2,3,4]
U2 : Vector Fraction Integer := [1,-1,1,1,1,0]
U3 : Vector Fraction Integer := [0,1,0,2,1,1]
U4 := U3 - 2*U1
nullSpace matrix [U1,U2,U3,U4]
LV := [U1, U2, U3, U4]
intBasisLLV [nullSpace matrix [U] for U in LV]
\end{verbatim}
\begin{verbatim}
                             7   3     1         8   7   1
         @[[- 1,0,1,0,0,0],[- -,- -,0,- -,1,0],[- -,- -,0,-,0,1]]
                             5   5     5         5   5   5
\end{verbatim}
%%
%%
\end{document}