[PDF] Document - Dénombrement dans un espace vectoriel fini

View - Download Document - Dénombrement dans un espace vectoriel fini

Previous PDF

Next PDF

Document - Dénombrement dans un espace vectoriel fini Préparation à l"agrégation - Jérôme Von Buhren -http://vonbuhren.free.frDénombrement dans un espace vectoriel fini

Dans ce document, on considère un espace vectorielEde dimension finien?N? sur un corps finiFq. CommeEest isomorphe àFnq, le cardinal deEestqn.

1. Dénombrement des endomorphismes deE

On commence par dénombrer l"ensemble des endomorphismes deE.

Proposition :Le cardinal deL(E)estqn2.

Démonstration:L"espace vectorielL(E)est de dimensionn2sur le corpsFq, donc il est iso- morphe àFn2 q, d"où le résultat.On peut également dénombrer les endomorphismes bijectifs.

Proposition :Le cardinal du groupeGL(E)est

Card(GL

n(Fq)) =n-1? k=0(qn-qk). Démonstration:1)En fixant une base deE, on obtient une bijection deGL(E)surGLn(Fq).

Il suffit donc de calculer le cardinal deGLn(Fq).

2)SiM?Mn(Fq), notonsM1,...,Mn?Fnqles colonnes deM. Une ma-

triceM?Mn(Fq)est inversible si et seulement si M

1?= 0, M2?Fnq\Vect(M1), ..., Mn?Fnq\Vect(M1,...,Mn-1).

On dispose donc deqn-1possibilités pour la colonneM1, puisqn-qpossibilités pour la colonneM2,..., puisqn-qn-1possibilités pour la colonneMn, d"où le résultat.On en déduit le cardinal du groupeSL(E).

Proposition :Le cardinal du groupeSL(E)est

Card(SL

n(Fq)) =1q-1·n-1? k=0(qn-qk). Démonstration:1)En fixant une base deE, on obtient une bijection deSL(E)surSLn(Fq)qui ont donc le même cardinal.

2)Le morphisme de groupesdet : GL(E)→F?qest surjectif de noyauSL(E).

On a donc la relation

Card(GL(E)) = Card(SL(E))·Card(F?q),

d"où le résultat.Finalement, rappelons que les centres respectifs deGL(E)et deSL(E)ne contiennent que des homothéties. Proposition :Le centre deGL(E)est de cardinalq-1et le centre deSL(E) est de cardinaln?(q-1).

Démonstration:1)Les homothéties dansGL(E)sont lesλ·IdEavecλ?F?q, d"où le résultat

pour le cardinal du centre deGL(E).

2)Les homothéties dansSL(E)sont lesλ·IdEavecλ?F?qvérifiantλn= 1.

CommeF?qest un groupe d"ordreq-1, on aλq-1= 1pour toutλ?F?q. En notantd=n?(q-1), on en déduit queλn= 1si et seulement siλd= 1en utilisant l"identité de Bézout, donc

Z(SL(E)) ={λ·IdE?GL(E)|λ?F?q, λd= 1}.

Finalement, commeddiviseq-1et queF?qest un groupe cyclique d"ordreq-1, il est classique que{λ?F?q|λd= 1}est l"unique sous-groupe d"ordreddeF?q, d"où le résultat.1/4

Document - Dénombrement dans un espace vectoriel fini Préparation à l"agrégation - Jérôme Von Buhren -http://vonbuhren.free.fr2. Nombres de sous-espaces vectoriels

Dans cette partie, on va compter le nombre de sous-espaces vectoriels deE d"une dimension donnée. Proposition :Soitd?J0,nK. Le nombre de sous-espace vectoriels deEde dimensiondest?n d? q =d-1? k=0(qn-qk)(qd-qk). Démonstration:SiFest sous-espace vectoriel deEde dimensiond, alors chaque base deFest une famille libre de cardinalddans l"espace vectorielE. Par le même argument utilisé pourCard(GL(E)), le nombre de telle famille libre est d=d-1? k=0(qn-qk). De plus, l"espace vectorielFadmetCard(GLd(Fq))bases distinctes. On conclut que le nombre cherché estαd/Card(GLd(Fq)), d"où le résultat.Remarques : a) En particulier, le nom brede droites v ectoriellesd ansEest(qn-1)/(q-1). b)

Le nom bre?n

d? q est appelé un coefficientq-binomial. c) Comme un sous-espace v ectorielde Ede dimensiondcorrespond de manière unique à un sous-espace vectoriel de dimensionn-ddeE?par dualité, on en déduit la relation ?d?J0,nK,?n d? q =?n n-d? q .Proposition :Soit(n1,...,nr)?(N)ravecn1+···+nr=netr?N?. Le nombre de décompositions en somme directeE=F1? ··· ?FroùFiest un sous-espace vectoriel deEvérifiantdim(Fi) =nipour touti?J1,rKest

Card(GL

n(Fq))Card(GL n1(Fq))···Card(GLnr(Fq)). Démonstration:NotonsDl"ensemble des(F1,...,Fr)vérifiant les conditions ci-dessus. Le groupeGL(E)agit transitivement surDpar u·(F1,...,Fr) = (u(F1),...,u(Fr)). De plus, le stabilisateur d"un élément(F1,...,Fr)?Dest isomorphe à GL(F1)× ··· ×GL(Fr)?GLn1(Fq)× ··· ×GLnr(Fq). On obtient donc le résultat avec la formule usuelle Card(Orb(F1,...,Fr)) =Card(GL(E))Card(Stab(F1,...,Fr)).3. Les endomorphismes diagonalisables

Dans la suite, sin > q, on considèrera que?q

n?= 0. Nous allons déterminer le nombre d"endomorphismes deEdont le polynôme caractéristique est scindé à racines simples. Proposition :Le nombre d"endomorphismes deEadmettant un polynôme ca- ractéristique scindé à racines simples est ?q n?

·Card(GLn(Fq))(q-1)n.

2/ 4

Document - Dénombrement dans un espace vectoriel fini Préparation à l"agrégation - Jérôme Von Buhren -http://vonbuhren.free.frDémonstration:1)Dans le cas oùq < n, le cardinal cherché est nul, donc le résultat énoncé est

valable. Dans la suite, on suppose queq>n.

2)En fixant une base, on se ramène à raisonner sur les matrices. On noteC

l"ensemble des matrices deMn(Fq)dont le polynôme caractéristique est scindé à racines simples. Le groupeGLn(Fq)agit par conjugaison surC. Deux matrices deCsont dans la même orbite pour cette action si et seulement si elles ont le même spectre. On en déduit qu"il y a?q n?orbites. De plus, tous les éléments de l"ensembleCsont diagonalisables et siD?Cest une matrice diagonale, on a par un calcul direct que Stab(D) ={Diag(λ1,...,λn)?GLn(Fq)|(λ1,...,λn)?(F?q)n}. On obtient donc le résultat avec la formule usuelle

Card(Orb(D)) =Card(GLn(Fq))Card(Stab(D))=Card(GLn(Fq))(q-1)n.Exemple :En appliquant la formule à l"espace vectorielE=F22sur le

corpsF2, on trouve qu"il y a6matrices dansM2(F2)admettant deux valeurs propres distinctes. Par un calcul direct, on trouve que ce sont les matrices ?1 0 0 0? ,?0 0 0 1? ,?1 1 0 0? ,?0 0 1 1? ,?1 0 1 0? ,?0 1 0 1? On dispose aussi d"une formule pour le nombre de tous les endomorphismes diagonalisables deE. Proposition :Le nombre d"endomorphisme diagonalisable deEest (n1,...,nq)?ΩqCard(GL n(Fq))Card(GL n1(Fq))···Card(GLnq(Fq))

avecΩq={(n1,...,nq)?Nq|n1+···+nq=n}.Démonstration:Un endomorphisme diagonalisableu?L(E)est caractérisé par la décomposi-

tion en somme directe E=?

λ?FqF

λavecFλ= Ker(u-λ·IdE)

En distinguant selon leq-uplet des dimensions(dim(Fλ))λ?Fq, on obtient le

résultat avec la dernière proposition de la partie précédente.Exemple :En appliquant la formule à l"espace vectorielE=F22sur le

corpsF2, on trouve qu"il y a8 = 1+6+1matrices diagonalisables dansM2(F2). Par un calcul direct, on trouve que ce sont les matrices?0 0 0 0? ,?1 0 0 1? ,?1 0 0 0? ,?0 0 0 1? ,?1 1 0 0? ,?0 0 1 1? ,?1 0 1 0? ,?0 1 0 1?

4. Dénombrement des endomorphismes nilpotents

En utilisant des méthodes analogues, nous allons montrer le résultat suivant. Proposition :On suppose quen= dim(E)>2. Le nombre d"endomorphismes nilpotents deEd"indicenest

Card(GL

n(Fq))q n-1(qn-1)=n-2? k=0(qn-qk). Démonstration:1)On travaille matriciellement. Avec la réduction de Jordan, on a qu"une ma- triceM?Mn(Fq)est nilpotente d"indicensi et seulement si elle est conjuguée

à la matrice

J=( (((((0 (0) 1 (0) 1 0) 3/ 4

Document - Dénombrement dans un espace vectoriel fini Préparation à l"agrégation - Jérôme Von Buhren -http://vonbuhren.free.fr2)La matriceJest la matrice compagnon deXn, doncJest matrice d"un

endomorphisme cyclique. On en déduit que son commutant estFq[J]. De plus, siP?Fq[X]avecdeg(P)6n, on a par un calcul direct deP(J)queP(J)est inversible si et seulement siP(0)?= 0. On en déduit que

Card(Com(J)∩GLn(Fq)) =qn-1(q-1).

3)Le groupeGLn(K)agit transitivement sur la classe de conjugaison deJpar

conjugaison. On en déduit avec le point 2 que Card(Orb(J)) =Card(GLn(Fq))Card(Stab(J))=Card(GLn(Fq))q n-1(q-1).Exemple :En appliquant la formule à l"espace vectorielE=F22sur le corpsF2, on trouve qu"il y a3matrices nilpotentes d"indice2dansM2(F2). Par un calcul direct, on trouve que ce sont les matrices?0 1 0 0? ,?0 0 1 0? ,?1 1 1 1? Pour terminer, nous allons déterminer le nombre d"endomorphismes nilpotents deE. Nous commençons par rappeler un résultat général d"algèbre linéaire. Décomposition de Fitting :Siu?L(E)est un endomorphisme, alors il existe un unique couple(F,G)de sous-espaces vectoriels stables parutel que (i)

On a la somme dir ecteE=F?G.

(ii)

L ar estrictionde uàFest nilpotente.

(iii)

L ar estrictionde uàGest inversible.

Démonstration:On commence par remarquer que les conditions énoncées imposent nécessai- rement queFest la réunion desKer(uk)pourk?NetGest l"intersection desIm(uk)pourk?N. Réciproquement, c"est un exercice classique de montrer

que ces deux sous-espaces vectoriels conviennent.Proposition :Le nombre d"endomorphismes nilpotents deEestqn2-n.

Démonstration:Pour toutk?N, on noteNkle nombre d"endomorphismes nilpotents deFkq etGkle nombre d"automorphismes deFkq. D"après la décomposition de Fitting, on en déduit une bijection deL(E)sur l"ensemble des quadruplets(F,G,f,g) vérifiantE=F?Get(f,g)?L(F)×GL(G)avecfnilpotent. On utilisant la formule déterminée précédemment pour le nombre de décomposition en somme directe deEavec deux sous-espaces vectoriels, on obtient donc la relation q n2=n? k=0N k·Gn-k·GnG k·Gn-k=n? k=0N k·GnGquotesdbs_dbs28.pdfusesText_34

[PDF] cardinal de l ensemble des parties d un ensemble

[PDF] formule cardinal probabilité

[PDF] comment calculer cardinal avec calculatrice

[PDF] intersection probabilité formule

[PDF] comment calculer p(a)

[PDF] diviser des puissances de 10

[PDF] méthode de horner factorisation d'un polynôme

[PDF] méthode de horner exercices

[PDF] methode de horner pdf

[PDF] methode de horner algorithme

[PDF] horner method

[PDF] méthode de horner exercice corrigé

[PDF] schema de horner

[PDF] algorithme de horner python

[PDF] seuil de rentabilité cours pdf