SEMAINE 2

ALGÈBRE LINÉAIRE (Programme de MPSI)

EXERCICE 1 : Idéaux à droite de L(E) en dimension finie

a. Théorème de factorisation
Soient E, F , G trois espaces vectoriels, soient w ∈ L(E, G) et v ∈ L(F, G). Montrer
l’équivalence
Im w ⊂ Im v ⇐⇒ ∃u ∈ L(E, F ) w = v ◦ u .
k
X
b. Soient u1 , · · ·, uk et v des endomorphismes d’un espace vectoriel E tels que Im v ⊂ Im ui .
i=1
k
X
Montrer qu’il existe des endomorphismes a1 , · · ·, ak de E tels que v = ui ◦ ai .
i=1
c. Soit E un IK-espace vectoriel de dimension finie. Montrer que les idéaux à droite de l’algèbre
L(E) sont les ensembles de la forme IF = {u ∈ L(E) | Im u ⊂ F }, où F est un sous-espace
vectoriel de E.
Solution proposée par François CHARLES, étudiant en MP* au Lycée Louis-le-Grand
-------------------------------
a. L’implication dans le sens indirect est immédiate.
Supposons donc Im w ⊂ Im v. Soit T un supplémentaire de Ker v dans F (on en admet
l’existence). On sait que v induit un isomorphisme (que nous noterons v) de T sur Im v.
Pour tout x de E,
on a w(x) ∈ Im v d’après l’hypothèse, il est donc loisible de poser
u(x) = v −1 w(x) . On définit
ainsi une application de E dans F , dont la linéarité est
immédiate et on a bien v u(x) = w(x) pour tout x de E.
Autre solution en admettant l’existence d’une base (ei )i∈I de E : si Im w ⊂ Im v alors, pour
tout i ∈ I, il existe un vecteur fi de F tel que w(ei ) = v(fi ). Si on appelle u l’unique
application linéaire de E vers F telle que u(ei ) = fi pour tout i, on a bien v ◦ u = w.
k
X
b. Considérons l’application linéaire f : E k → E définie par f (x1 , · · · , xk ) = ui (xi ). On a
i=1
k
X
clairement Im f = Im ui , donc Im v ⊂ Im f et il existe une application linéaire A de E
i=1
vers E k telle que v = f ◦ A. En posant A(x) = a1 (x), · · · , ak (x) pour tout x de E, on a

k


X

∀x ∈ E v(x) = f A(x) = f a1 (x), · · · , ak (x) = ui ai (x) ,
i=1
k
X
donc v = ui ◦ ai .
i=1

1
c. On appelle idéal à droite de L(E) toute partie I qui est un sous-groupe additif de L(E) et qui
vérifie
∀u ∈ I ∀a ∈ L(E) u◦a∈I .

• D’abord, si F est un sous-espace vectoriel de E, l’ensemble IF = {u ∈ L(E) | Im u ⊂ F }

est bien un idéal à droite de L(E).
• Soit I un idéal à droite de L(E).
Alors il est clair que I est un sous-espace vectoriel de L(E), soit (f1 , · · · , fk ) une base de
k
X
l’espace vectoriel I (on est en dimension finie), posons F = Im fi . On a alors I = IF :
i=1
en effet,
k
X
- si f ∈ I, on a f = λi fi où les λi sont des scalaires, donc Im f ⊂ F et f ∈ IF .
i=1
k
X
- si f ∈ IF , d’après la question b., on peut écrire f = fi ◦ ai , où les ai sont des
i=1
endomorphismes de E, et f ∈ I (car les fi appartiennent à I et I est un idéal à droite).
Remarque. Si p est un projecteur sur F , on peut noter que
IF = p ◦ L(E) = {p ◦ f ; f ∈ L(E)} :
IF est l’“idéal à droite engendré par p”.
Ce qui précède ne se généralise pas dans un espace vectoriel E de dimension infinie ; l’ensemble
I des endomorphismes de E de rang fini est alors un idéal (bilatère) de L(E) qui n’est pas
de la forme IF .

EXERCICE 2 : Idéaux à gauche de L(E) en dimension finie

a. Théorème de factorisation
Soient E, F , G trois espaces vectoriels, soient w ∈ L(E, G) et u ∈ L(E, F ). Montrer l’équivalence
Ker u ⊂ Ker w ⇐⇒ ∃v ∈ L(F, G) w = v ◦ u .
k
\
b. Soient u1 , · · ·, uk et v des endomorphismes d’un espace vectoriel E tels que Ker ui ⊂ Ker v.
i=1
Xk
Montrer qu’il existe des endomorphismes a1 , · · ·, ak de E tels que v = ai ◦ ui .
i=1
c. Soit E un IK-espace vectoriel de dimension finie. Montrer que les idéaux à gauche de l’algèbre
L(E) sont les ensembles de la forme JF = {u ∈ L(E) | F ⊂ Ker u}, où F est un sous-espace
vectoriel de E.
Source : Jacques CHEVALLET, Algèbre MP/PSI, Éditions Vuibert, ISBN 2-7117-2092-6

2
 ------------------------------
a. L’implication dans le sens indirect est immédiate.
Supposons donc Ker u ⊂ Ker w. Soit S un supplémentaire de Ker u dans E (on en admet
l’existence). On sait que u induit un isomorphisme (que nous noterons u) de S sur Im u.
Soit, par ailleurs, T
un supplémentaire de Im u dans F . Pour tout y dans Im u, posons
v(y) = w u−1 (y) et, pour tout y dans T , posons v(y) = 0G ; on a ainsi défini (de
façon unique puisque T ⊕ Im u = F ) une application linéaire v de F vers G.
Si x ∈ E, alors u(x) ∈ Im u, donc u−1 u(x) est un élément x0 de S, donc de E (pas

nécessairement égal à x), tel que u(x0 ) = u(x) ; puisque Ker u ⊂ Ker w par hypothèse,
on a aussi w(x0 ) = w(x), ce qui se traduit par v u(x) = w(x), on a donc w = v ◦ u.

b. Considérons l’application linéaire f : E → E k définie par f (x) = u1 (x), · · · , uk (x) . On a

\k
clairement Ker f = Ker ui , donc Ker f ⊂ Ker v et il existe une application linéaire A de
i=1
E k vers E telle que v = A ◦ f . En posant a1 (x) = A(x, 0, 0, · · · , 0), a2 (x) = A(0, x, 0, · · · , 0),
et ainsi de suite, pour tout x de E, on a

∀x ∈ E v(x) = A f (x) = A u1 (x), · · · , uk (x)



= A u1 (x), 0, 0, · · · , 0 + A 0, u2 (x), 0, · · · , 0 + · · ·
k
X

= ai ui (x) ,
i=1

k
X
donc v = ai ◦ ui .
i=1

c. On appelle idéal à gauche de L(E) toute partie J qui est un sous-groupe additif de L(E) et
qui vérifie
∀u ∈ J ∀a ∈ L(E) a◦u∈J .

• D’abord, si F est un sous-espace vectoriel de E, l’ensemble JF = {u ∈ L(E) | F ⊂ Ker u}

est bien un idéal à gauche de L(E).
• Soit J un idéal à gauche de L(E).
Alors il est clair que I est un sous-espace vectoriel de L(E), soit (f1 , · · · , fk ) une base de
k
\
l’espace vectoriel I (on est en dimension finie), posons F = Ker fi . On a alors I = JF :
i=1
en effet,
k
X
- si f ∈ I, on a f = λi fi où les λi sont des scalaires, donc F ⊂ Ker f et f ∈ JF .
i=1

3
 k
X
- si f ∈ JF , d’après la question b., on peut écrire f = ai ◦ fi , où les ai sont des
i=1
endomorphismes de E, et f ∈ I (car les fi appartiennent à I et I est un idéal à gauche).
Remarque. Si p est un projecteur de direction F (c’est-à-dire Ker p = F ), on peut noter que
JF = L(E) ◦ p = {f ◦ p ; f ∈ L(E)} :
JF est l’“idéal à gauche engendré par p”.
Ce qui précède ne se généralise pas dans un espace vectoriel E de dimension infinie ; l’ensemble
J des endomorphismes de E de rang fini est alors un idéal (bilatère) de L(E) qui n’est pas
de la forme JF .

EXERCICE 3 :
C’est un paysan, l’a 2n + 1 vaches. Quand qu’y met d’côté l’une quelconque d’ses vaches, ben
les 2n qui restent, y peut les répartir en deux sous-troupeaux de n vaches chacun et ayant
le même poids total.
Montrer qu’les vaches, è z’ont toutes le même poids.
Source : Merci à Christophe HÉNOCQ
------------------------------
Soient p1 , . . ., p2n+1 les poids
 des vaches (nommées V1 , . . ., V2n+1 , c’est plus pratique que “Mar-
p1
 . 
guerite”). Soit P =  ..  ∈ IR2n+1 .
p2n+1
Traduisons l’hypothèse : pour tout i ∈ [[1, 2n + 1]], les vaches Vj (j 6= i) peuvent être réparties en
deux sous-troupeaux de même effectif et de même poids total. Il existe donc des coefficients
ai,j (avec 1 ≤ j ≤ 2n + 1) tels que
• (1) ai,i = 0 (la vache Vi part brouter dans son coin) ;
• (2) ai,j = ±1 si j 6= i ; (le signe dépend du sous-troupeau dans lequel on met la vache
Vj )
2n+1
X
• (3) ai,j = 0 (les deux sous-troupeaux ont même effectif)
j=1
2n+1
X
• (4) ai,j pj = 0 (les deux sous-troupeaux ont même poids total).
j=1
Autrement dit, il existe une matrice A = (ai,j ) ∈ M2n+1 (IR) telle que
• (1) : les coefficients diagonaux sont nuls ;
• (2) : les autres coefficients valent ±1 ;

4
 1
 
.
• (3) : la somme des éléments de chaque ligne est nulle, ce qui revient à dire que X0 =  .. 
1
appartient au noyau Ker A ;
• (4) : la somme des éléments de chaque ligne, pondérés des coefficients pj , est nulle,
c’est-à-dire P ∈ Ker A.
Nous allons montrer que toute matrice A ∈ M2n+1 (IR) vérifiant les conditions (1) et (2) est
de rang 2n, ce qui signifie que son noyau est de dimension 1. Les conditions (3) et (4)
entraı̂neront alors que les vecteurs P et X0 sont colinéaires, donc que les vaches ont toutes
le même poids.
Soit donc une matrice A ∈ M2n+1 (IR) vérifiant les conditions (1) et (2). Considérons la matrice
extraite B = (aij )1≤i,j≤2n obtenue en ôtant la dernière ligne et la dernière colonne, et
montrons qu’elle est inversible. Son déterminant est
X
D = det(B) = ε(σ) a1,σ(1) . . . a2n,σ(2n) .
σ∈S2n

Les termes diagonaux étant nuls, les seuls termes non nuls du développement de ce déter-
minant sont ceux pour lesquels σ est un dérangement (permutation sans point fixe) de
[[1, 2n]]. Par ailleurs, chacun de ces termes non nuls vaut ±1, donc le déterminant D est un
entier relatif de même parité que le nombre de dérangements de l’ensemble [[1, 2n]]. Si nous
prouvons que ce nombre est impair, la démonstration est achevée.

Soit donc, pour tout k entier naturel non nul, dk le nombre de dérangements de l’ensemble [[1, k]].
Nous allons prouver la relation de récurrence
(R) : dk = (k − 1)(dk−1 + dk−2 ) (k ≥ 3) .
Preuve de la relation (R) : soit k ≥ 3, soit σ un dérangement de [[1, k]]. Il y a k − 1 choix possibles
pour le nombre j = σ(k) ∈ [[1, k − 1]]. Deux possibilités s’excluent alors mutuellement :
- si σ(j) = k, alors la restriction de σ à l’ensemble [[1, k]] \ {j, k} est un dérangement d’un
ensemble à k − 2 éléments, il y en a dk−2 ;
- si σ(j) 6= k, le dénombrement est un peu moins évident. Introduisons pour cela l’ensemble
Ej des dérangements de [[1, k]] tels que σ(k) = j et σ(j) 6= k, puis l’ensemble F des
dérangements
( de [[1, k − 1]]. A tout élément σ de Ej , associons l’élément τ de F défini
τ σ −1 (k) = j


par (en quelque sorte, on “zappe” l’élément k). On
τ (p) = p si p 6= σ −1 (k)
voit facilement que la correspondance
 −1

σ 7→ τ est une bijection de Ej sur F, la bijection

 σ τ (j) = k
réciproque est τ 7→ σ, avec σ(k) = j . Donc le cardinal de Ej est dk−1 ,

σ(p) = τ (p) sinon

ce qui achève la démonstration.
Revenons à nos vaches... De la relation (R), il résulte que d2n−1 = (2n − 2)(d2n−2 + d2n−3 ) est
toujours un nombre pair, puis on montre par récurrence sur n que d2n est impair :

5
 - pour n = 1, d2 = 1 ;
- si d2n−2 est impair (pour n ≥ 2), alors d2n = (2n − 1)(d2n−1 + d2n−2 ) avec 2n − 1 impair,
d2n−1 pair et d2n−2 impair, donc d2n est impair, ce qui achève le troupeau.

******************************

Quelques compléments sur les dérangements, sans plus déranger les vaches qui finiraient par
devenir folles...
La relation de récurrence (R) permet d’écrire une fonction récursive en MAPLE pour calculer
le nombre dn , not der(n) :

> der:= proc(n) option remember:

if n=1 then 0
elif n=2 then 1
else (n-1)*(der(n-1)+der(n-2))
fi
end:
 
La relation (R) peut s’écrire dn − ndn−1 = − dn−1 − (n − 1)dn−2 ; la suite de terme général
un = dn − ndn−1 est donc géométrique de raison −1, d’où un = dn − ndn−1 = (−1)n pour
dk dk−1 (−1)k
n ≥ 2. On a donc, pour tout k ≥ 2, la relation − = . En sommant pour
k! (k − 1)! k!
k de 2 à n, on obtient
n
!
X (−1)k
dn = n!
k!
k=2

n!
et, comme conséquence, l’équivalence dn ∼ .
e

EXERCICE 4 :
Soient P et Q deux polynômes de C[X], de degrés m et n respectivement.
1. Montrer que P et Q ont une racine commune si et seulement si la famille
(P, XP, . . . , X n−1 P, Q, XQ, . . . , X m−1 Q)
est liée dans C[X].
m
X n
X
2. On pose P = ak X k , Q = bj X j .
k=0 j=0

Écrire un déterminant qui s’annule si et seulement si P et Q ont une racine commune.

3. En déduire une condition nécessaire et suffisante pour que le polynôme P = X 3 + pX + q
admette une racine double.

6
4. Un nombre complexe a est dit algébrique s’il annule un polynôme (non nul) à coefficients
rationnels.
Montrer que la somme de deux nombres algébriques est algébrique.
Ecrire un polynôme non nul de Q[X], de plus petit degré possible, admettant pour racine i + j.
Source : Jean-Pierre ESCOFIER, Théorie de Galois, Éditions Masson, ISBN 2-225-82948-9.

------------------------------

1. Les polynômes P et Q ont une racine commune si et seulement si leur pgcd P ∧ Q est non
constant, c’est-à-dire si et seulement si leur ppcm P ∨ Q est de degré strictement inférieur
à m + n (puisque les polynômes P Q et (P ∧ Q)(P ∨ Q) sont associés). Cela équivaut à
l’existence d’un multiple commun non nul de degré < m + n, ou encore de deux polynômes
U et V non tous deux nuls tels que
UP − V Q = 0 , avec deg U < n et deg V < m .
Une condition nécessaire et suffisante est donc que la famille de polynômes
P = (P, XP, . . . , X n−1 P, Q, XQ, . . . , X m−1 Q)
soit liée.
2. Il suffit de considérer le déterminant (d’ordre m + n) de la famille P dans la base canonique
(1, X, X 2 , . . . , X m+n−1 ) de C m+n−1 [X] :
 a0 0 . . . 0 b0 0 ... ... 0
 

 .. .. .. .. .. .. 
 a1
 . . . b1 . . .


 .. .. .. .. .. .. 

 . . 0 . . . . 

 . . .. .. 

 . a0 . . 0 
SX (P, Q) = 
 .. 
 a1 bn . b0 
 .. 
 am 0 . b1 
.. .. .. ..

. . .
 
 0 . 
 . .. .. .. .. .. 
 . . . . .
 . .


0 . . . 0 am 0 ... ... 0 bn
 

(les n premières colonnes sont constituées des coefficients du polynôme P , que l’on décale
et les m colonnes suivantes des coefficients du polynôme Q, que l’on décale). SX (P, Q) est
le déterminant de Sylvester des polynômes P et Q.
3. On cherche une condition pour que le polynôme P et sa dérivée P 0 aient une racine commune.
Or,

q 0 p 0 0 0 0 p −3q 0 
   
0 p −3q 0 
 
p q 0 p 0 0 q 0 −2p 0 
   
0 0 −2p −3q 
 
SX (P, P 0 ) = 0 p 3 0 p = 0 0 3 0 −2p  = − 
   
0 3 0 −2p 

1 0 0 3 0 1 0 0 3 0 
   
1 0 0 3
 
0 1 0 0 3 0 1 0 0 3
   

7
  
p −3q 0 
−3q  = 4p3 + 27q 2

=  0 −2p
3 0 −2p 

(on a effectué d’abord les opérations L1 ← L1 − qL4 , L2 ← L2 − pL4 , L3 ← L3 − pL5 ,

puis un développement par rapport à la première colonne et L2 ← L2 − qL4 ). La condition
cherchée est donc 4p3 + 27q 2 = 0.
4. Soient a et b deux nombres algébriques, soient P et Q deux polynômes non nuls de Q[X] tels
que P (a) = 0 et Q(b) = 0. Les polynômes P (X) et Q(a + b − X)
ont une racine commune
a, donc leur déterminant de Sylvester SX P (X), Q(a + b − X) est nul.


Posons R(Y ) = SX P (X), Q(Y − X) : c’est un déterminant dont les coefficients sont des
polynômes de Q[Y ], donc R(Y ) est un polynôme de Q[Y ] admettant a + b pour racine. Le
nombre complexe a + b est donc algébrique.
Avec a = i et b = j, on peut choisir P = X 2 + 1 et Q = X 2 + X + 1 qui sont leurs polynômes
minimaux respectifs sur Q (si a ∈ C est algébrique, l’ensemble {P ∈ Q[X] | P (a) = 0}
est un idéal non nul de Q[X] et le générateur normalisé de cet idéal est appelé polynôme
minimal de a sur Q). Un polynôme de Q[X] annulateur de i + j est alors

= SX X 2 + 1, (Y − X)2 + (Y − X) + 1


R(Y )
X 2 + 1, X 2 − (2Y + 1)X + (Y 2 + Y + 1)


= SX
1 0 Y2+Y +1 0
 

2
0 1 −(2Y + 1) Y + Y + 1 
 
=   = Y 4 + 2Y 3 + 5Y 2 + 4Y + 1 .
1 0 1 −(2Y + 1) 
0 1 0 1
 

Montrons le caractère minimal de ce polynôme R. Supposons qu’il existe un polynôme

S ∈ Q[Y ], diviseur strict (normalisé) de R, tel que S(i + j) = 0. Un tel polynôme S
ne peut être de degré 1 car on aurait alors i + j ∈ Q ; il ne peut être de degré 3
car on aurait alors R = ST avec T ∈ Q[Y ] de degré un, et le polynôme R aurait une
racine rationnelle (ce n’est pas le cas car le polynôme R, par construction, admet pour
racines tous les nombres que l’on peut écrire comme somme d’une racine de P et d’une
racine de Q, à savoir les quatre nombres irrationnels distincts α = i + j, β = −i + j,
γ = i + j 2 , δ = −i + j 2 appelés conjugués de i + j sur le corps Q et ces quatre nombres sont
donc ses seules racines). Enfin,
si S tait
de degré deux, √ on aurait
2 2
S(Y ) = (Y − α)(Y − α) = Y − (i + j) Y − (−i + j ) = Y + Y + 2 + 3 qui n’est pas
à coefficients rationnels.
Le polynôme minimal de α = i + j sur Q est donc R(Y ) = Y 4 + 2Y 3 + 5Y 2 + 4Y + 1.
******************************
Quelques compléments sur ce “déterminant de Sylvester” : on note les propriétés suivantes :
• si Q est un polynôme constant (Q = λ), alors SX (P, Q) = λdeg(P ) ;
• on a SX (Q, P ) = (−1)deg(P )·deg(Q) SX (P, Q) : en effet, en reprenant les notations de la question
1., on voit que SX (P, Q) est transformé en SX (Q, P ) si l’on fait opérer sur les colonnes de la

8
  
1 2 ··· n n + 1 n + 2 ··· n + m
matrice la permutation σ =
m + 1 m + 2 ··· m + n 1 2 ··· n
et cette permutation a pour signature (−1)mn , on peut la décomposer en produit de mn
transpositions par exemple en échangeant l’élément n successivement avec les m éléments
qui le suivent, puis idem pour l’élément n − 1, et ainsi de suite jusqu’à l’élément 1 ;
• si m = deg(P ) ≥ n = deg(Q) et si R est le reste de la division euclidienne de P par Q, on a
SX (P, Q) = bdeg(P
n
)−deg(R)
SX (P, R) ;
en effet, notons R1 le premier reste partiel dans la division euclidienne de P par Q (le
lecteur est vivement invité à traiter un exemple), en effectuant sur la matrice présentée
am
à la question 2. les opérations sur les colonnes Cj ← Cj − Cm+j (1 ≤ j ≤ n) et
bn
en développant par rapport à la dernière ligne deg(P ) − deg(R1 ) fois, on obtient l’égalité
SX (P, Q) = bdeg(P
n
)−deg(R1 )
SX (P, R1 ), il ne reste plus qu’à itérer.
Cela montre que l’on peut calculer le déterminant de Sylvester de deux polynômes de façon
récursive (cf. procédure ci-dessous) et cela prouve aussi que ce déterminant de Sylvester est
la même chose que le résultant défini dans l’exercice 5 de la semaine 1.
Procédure de calcul récursive :
> result:= proc(P,Q,X):
if (P=0) or (Q=0) then 0
elif degree(Q,X)=0 then lcoeff(Q,X) b degree(P,X)
else (-1) b degree(P,X)*degree(Q,X))*
lcoeff(Q,X) b (degree(P,X)-degree(rem(P,Q,X),X)) *
factor(result(Q,rem(P,Q,X),X))
fi
end;

EXERCICE 5 :
Pour toute matrice A = (aij ) ∈ Mn (IR), on appelle permanent de A le réel
X
per(A) = aσ(1),1 · · · aσ(n),n .
σ∈Sn

1. Dégager les propriétés élémentaires du permanent.

2. Théorème de Frobenius et König
Soit A ∈ Mn (IR) une matrice à coefficients positifs ou nuls. Montrer que son permanent est nul
si et seulement si on peut extraire de A une matrice nulle de format s × (n + 1 − s), où s
est un entier appartenant à [[1, n]].
3. Lemme des mariages :
Soient F et G deux ensembles finis, soit Φ : G → P(F ) une application.
Démontrer l’équivalence des assertions (1) et (2) :
(1) : il existe une injection ϕ : G → F telle que ∀g ∈ G ϕ(g) ∈ Φ(g).

9
  
[ 
(2) : ∀ G0 ∈ P(G) Φ(g) ≥ |G0 |.
 


g∈G0 

Source : Jean-Marie MONIER, Algèbre Tome 2, Éditions Dunod, ISBN 2-10-000006-3

-------------------------------

1. Le permanent est une forme n-linéaire symétrique des n lignes (ou des n colonnes) de la
matrice, il est donc invariant par toute permutation de lignes ou de colonnes.
On peut développer le permanent par rapport à une ligne ou une colonne : si on note Aij
la matrice carrée d’ordre n − 1 obtenue en supprimant de A la i-ième ligne et la j-ième
colonne, on a
Xn
per(A) = aij per(Aij ) pour tout i ∈ [[1, n]] ;
j=1
n
X
per(A) = aij per(Aij ) pour tout j ∈ [[1, n]] .
i=1
 
A 0
On peut calculer des permanents par blocs : per = per(A) × per(D).
C D
Enfin, on a per( tA) = per(A).
Les propriétés qui précèdent se démontrent de façon analogue aux propriétés correspondantes
pour les déterminants.
Par contre, si A et B sont deux matrices carrées d’ordre n, alors per(AB) 6= per(A)
 × per(B)

1 1
en général, et on a même per(AB) 6= per(BA) en général, essayer avec A = et
  1 1
1 2
B= .
3 4
2. Notons M+ n l’ensemble des matrices carrées d’ordre n à coefficients positifs ou nuls.
• Soit A ∈ M+ n , supposons que l’on puisse extraire de A une matrice nulle de format
s × (n + 1 − s) pour s ∈ [[1, n]] donné. Par des permutations de lignes et de colonnes
 (qui 
ne
A 0
modifient pas le permanent), on peut transformer A en une matrice A0 = 1 s,n−s
,
A2 A3
avec A1 carrée d’ordre s ayant sa dernière colonne nulle (on en déduit le format des autres
matrices) ; en développant par rapport à cette dernière colonne, on a per(A1 ) = 0, puis
per(A) = per(A0 ) = per(A1 ) × per(A3 ) = 0.
• Pour l’implication réciproque, montrons par récurrence forte sur n ∈ IN∗ l’assertion
(An ) : ∀A ∈ M+
n per(A) = 0 =⇒ ∃s ∈ [[1, n]] 0s,n+1−s est extraite de A .
. pour n = 1, la propriété est immédiate.

10
 . Soit n ∈ IN∗ , supposons l’assertion vérifiée pour les entiers 1, 2, · · ·, n et soit A ∈ M+
n+1
telle que per(A) = 0 et A 6= 0.
Soit aij un coefficient non nul (donc strictement positif) de la matrice A, on a alors
per(Aij ) = 0 : en effet, en développant par rapport à la i-ième ligne, on a
X n
0 = per(A) = aik per(Aik ) et, tous les termes de cette somme étant positifs, ils sont
k=1
donc tous nuls.
D’après l’hypothèse de récurrence, on peut extraire de la matrice Aij (donc de A) une
matrice nulle de format s × (n + 1 − s) avec 1 ≤ s ≤ n et des permutations
 sur les
 lignes
A 0
et les colonnes permettent de transformer A en une matrice A0 = 1 s,n+1−s
, où A1
A2 A3
et A3 sont carrées d’ordres s et n + 1 − s respectivement, et à coefficients positifs ou nuls .
On a
0 = per(A) = per(A0 ) = per(A1 ) × per(A3 ) ,
donc per(A1 ) = 0 ou per(A3 ) = 0.
Supposons per(A1 ) = 0. En utilisant l’hypothèse de récurrence, il existe un entier t
(1 ≤ t ≤ s) tel que l’on puisse extraire de A1 une matrice nulle de format t × (s + 1 − t). En
effectuant des permutations de lignes et de colonnes, on place cette matrice nulle dans
“le coin en haut à droite” de la matrice A1 et, en revenant à la forme diagonale par
A1 0s,n+1−s
blocs A0 = , on voit que l’on peut extraire de A un bloc nul de format
A2 A3
t × ((s + 1 − t) + (n + 1 − s)), c’est-à-dire t × (n + 2 − t), c’est bien ce qu’on voulait obtenir
(raisonnement analogue si per(A3 ) = 0).
3. Pour interpréter la question posée, notons
G = {g1 , . . . , gm } (“ensemble des garçons”)
F = {f1 , . . . , fn } (“ensemble des filles”}
Φ : à chaque garçon g ∈ G, on associe un ensemble de filles Φ(g) ;
(1) : chaque garçon g ∈ G peut choisir une fille ϕ(g) dans l’ensemble Φ(g), de telle sorte que
deux garçons différents ne choisissent jamais la même fille ;
(2) : si un sous-ensemble de garçons a k éléments, la réunion des ensembles de filles dans
lesquels ils peuvent choisir a au moins k éléments.

Allons-y :
• (1) =⇒ (2) est immédiat : si ϕ est une injection, on a |ϕ(G0 )| = |G0 | pour toute partie G0
[ 
[
de G. Or, ϕ(G0 ) ⊂ Φ(g), donc |G0 | = |ϕ(G0 )| ≤ 
 
Φ(g).
g∈G0 g∈G0 

• (2) =⇒ (1) : c’est un peu plus long...

 
 
[
0
 
Avec G = G, on voit que   Φ(g) ≥ |G| donc, a fortiori, |F | ≥ |G| ou n ≥ m (il y a au
g∈G 

11
 moins autant de filles que de garçons).
Construisons une matrice A ∈ M+ n de la façon suivante :
* sur les m premières lignes, le coefficient aij (1 ≤ i ≤ m, 1 ≤ j ≤ n) vaut 1 si le i-ième
garçon peut choisir la j-ième fille, c’est-à-dire si fj ∈ Φ(gi ), et vaut 0 sinon ;
* les coefficients des n − m dernières lignes valent tous 1.
Le permanent de la matrice A est non nul ; en effet, si on avait per(A) = 0, on pourrait
extraire de A une matrice nulle de format s×(n+1−s) et cette matrice serait nécessairement
extraite des m premières lignes (donc s ≤ m), notons i1 < i2 < . . . < is les indices de lignes
et j1 < j2 < . . . < jn+1−s les indices de colonnes de cette matrice nulle extraite ; on aurait
alors
[s
Φ(gik ) ⊂ F \ {fj1 , . . . , fjn+1−s } ,
k=1
 s 
[ 
donc  Φ(gik ) ≤ n − (n + 1 − s) = s − 1 < s, ce qui contredit l’assertion (2) avec
 
 
k=1
G0 = {gi1 , . . . , gis }.
X
Donc per(A) = aσ(1),1 · · · aσ(n),n 6= 0, donc il existe au moins une permutation σ telle
σ∈Sn
que aσ(i),i 6= 0 pour tout i ∈ [[1, n]]. Ainsi, pour tout i ∈ [[1, m]], on a ai,σ−1 (i) 6= 0 et
fσ−1 (i) ∈ Φ(gi ). L’application ϕ : G → F , gi 7→ fσ−1 (i) (1 ≤ i ≤ m) vérifie les conditions de
l’assertion (1).

EXERCICE 6 :
Soit E un IK-espace vectoriel de dimension finie n ≥ 1.
Un élément τ de L(E) est une transvection s’il existe un hyperplan H tel que

τ H = idH et Im(τ − idE ) ⊂ H ,
c’est-à-dire Im(τ − idE ) ⊂ H ⊂ Ker(τ − idE ).
On note SL(E) = {u ∈ GL(E) | det u = 1} le groupe spécial linéaire de E.
1. Montrer que τ ∈ L(E) est une transvection si et seulement si
∃ϕ ∈ E ∗ ∃a ∈ Ker ϕ ∀x ∈ E τ (x) = x + ϕ(x) a .
2. Dans cette question, on suppose dim E ≥ 2. Soient x et y deux vecteurs non nuls de E.
Montrer qu’il existe τ , transvection ou produit de deux transvections, tel que τ (x) = y.
3. Soit x un vecteur non nul de E, soient H1 et H2 deux hyperplans distincts tels que
x 6∈ H1 ∪ H2 . Montrer qu’il existe une transvection τ telle que
τ (x) = x et τ (H1 ) = H2 .
4. En déduire que le groupe SL(E) est engendré par les transvections.

12
Source : Daniel PERRIN, Cours d’Algèbre, Éditions Ellipses, ISBN 2-7298-5552-1
-------------------------------
1. Soit τ une transvection.
• Si τ = idE , on peut choisir ϕ = 0 et a ∈ E quelconque.
• Si τ 6= idE , alors Ker(τ −idE ) est un hyperplan H, et Im(τ −idE ) est une droite vectorielle D
contenue dans H, soit a un vecteur directeur de D. Pour tout x de E, notons ϕ(x) l’unique
scalaire tel que τ (x) − x = ϕ(x)a. L’application ϕ : E → IK est une forme linéaire de noyau
H, donc a ∈ Ker ϕ.

Réciproquement, soit τ un endomorphisme de E tel que τ (x) = x+ϕ(x)a, avec ϕ forme linéaire
sur E et a ∈ Ker ϕ.
• si a = 0 ou ϕ = 0, alors τ = idE : c’est une transvection ;
• sinon, H = Ker ϕ est un hyperplan, on a bien ∀x ∈ H τ (x) = x et
∀x ∈ E τ (x) − x = ϕ(x)a ∈ H ,
donc τ est une transvection “d’hyperplan H”.

2. Supposons d’abord x et y non colinéaires, soit a = y − x (a 6= 0), soit H un hyperplan vectoriel

contenant a mais pas x. Soit ϕ la forme linéaire sur E nulle sur H et telle que ϕ(x) = 1.
La transvection τ : v 7→ v + ϕ(v)a envoie x sur y.
Si x et y sont colinéaires, puisque dim E ≥ 2, il suffit de “transiter” par un vecteur z non
colinéaire à x et y pour trouver un produit de deux transvections qui envoie x sur y.

3. Le sous-espace F = H1 ∩ H2 est de dimension n − 2, considérons l’hyperplan H = F ⊕ IKx.

Soient D1 et D2 des droites telles que H1 = F ⊕ D1 et H2 = F ⊕ D2 . On peut choisir des
vecteurs directeurs x1 et x2 de D1 et D2 respectivement, de façon que x1 − x2 ∈ H : en
effet, (D1 ⊕ D2 ) ∩ H 6= {0} pour des raisons de dimensions.

Soit enfin τ l’unique endomorphisme de E tel que τ H = idH et τ (x1 ) = x2 (on a x1 6∈ H
car, sinon, on aurait aussi x2 ∈ H, puis H1 ⊂ H, H2 ⊂ H et finalement H1 = H2 = H
absurde). On vérifie immédiatement que Im(τ − idE ) ⊂ H, donc
 τ est bien une transvection
“d’hyperplan H”. Enfin, τ (x) = x puisque x ∈ H et, comme τ F = idF et τ (x1 ) = x2 , on a
τ (H1 ) = H2 .
Il existe donc une transvection laissant stable x et envoyant H1 sur H2 .

4. Vérifions d’abord que les transvections appatiennent à SL(E) : pour τ = idE , c’est immédiat,
sinon si τ : x 7→ x + ϕ(x)a avec a ∈ H = Ker ϕ, construisons une base B = (e1 , · · · , en−1 , en )
de E avec en−1 = a, (e1 , · · · , en−1 ) base de H et ϕ(en ) = 1, alors MB (τ ) = In + En−1,n
a pour déterminant 1.
Démontrons le lemme suivant :
Soit E un IK-espace vectoriel de dimension n ≥ 2, soit u ∈ SL(E). Soit H un hyperplan de E,
soit x ∈ E \ H. Alors il existe un élément v de SL(E) vérifiant v(H) = H et v(x) = x et
tel que u = σv où σ est composé d’un nombre fini de transvections.

13
Preuve du lemme : D’après la question 2., il existe τ (transvection, ou produit de deux transvec-
tions) tel que τ (x) = u(x), c’est-à-dire τ −1 u(x) = x.
Soit l’hyperplan H 0 = τ −1 u(H) :
. si H 0 = H, on prend v = τ −1 u ;
. si H 0 6= H, on a x 6∈ H ∪ H 0 , il existe donc (question 3.) une transvection µ telle que
µ(x) = x et µ(H) = H 0 et v = µ−1 τ −1 u répond à la question (fin de la preuve du lemme).

On montre alors que les transvections engendrent le groupe SL(E) par récurrence sur
n = dim(E) :
• pour n = 1, c’est clair puisque la seule transvection est idE et SL(E) = {idE } ;
• soit n ≥ 2, supposons l’assertion vraie au rang n − 1, soit E de dimension n, soit u ∈ SL(E).
Soit H un hyperplan de E, soit x ∈ E \ H (alors E = H ⊕ (IKx)), on écrit u = σ0 v,
où σ0 est un produit de transvections de E, et v ∈ SL(E) laisse stables H et x (lemme).
On vérifie alors que v H ∈ SL(H) (écrire la matrice de v dans une base adaptée à la
décomposition E = H ⊕ (IKx)), l’hypothèse de récurrence permet d’écrire v H = τ1 · · · τk ,
où les τi (1 ≤ i ≤ k) sont des transvections
 de H ; on a alors v = σ1 · · · σk , où chaque σi
est l’endomorphisme de E défini par σi H = τi et σi (x) = x (on vérifie facilement que σi
est une transvection de E). Finalement, u = σ0 σ1 · · · σk est un produit de transvections.

14