exercice sup, algèbre lineaire

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Je change de prepa entre la sup et la spé et pour rattraper un potentiel retard j'essaie de faire quelques exos. Tandis que la plupart passe presque (du moins avec une indication) je reste complètement bloqué sur celui ci:

Soit $n \in \mathbb N*$ Soit $X_i$ ($ i \in \{1 ... n+1\}$) une famille de parties non vides de {1 … n} Montrer qu'il existe deux ensembles disjoints I et J tel que :

$$\bigcap _{i \in I} X_i = \bigcap _{j \in J} X_j$$

union […] = union […]

Comme indication, il y a qu'il faut passer par le vecteur indicateur des parties (dans $\{0,1\}^n$ je suppose donc ) et trouver une relation non triviale entre les vecteurs.

Malheureusement je n'arrive pas à trouver grand chose (le systeme est evidemment lié (n+1 vecteurs), on peut les supposer tous distincts (sinon trivial) , rien d'autre de réellement concluant )

Si quelqu'un a une piste un peu plus, disons précise, je suis preneur.

Édité par regz

+0 -0

Tu es sûr que ce n'est pas des unions plutôt ? Parce qu'avec des intersections, c'est faux pour n=2 mais c'est vrai pour des unions (ce qui revient à interdire X_i={1,…,n} au lieu de X_i=∅). Par contre ma preuve ne passe pas par de l'algèbre linéaire (je ne vois pas comment parler de l'intersection ou de l'union dans ce langage (si on se met dans un demi-anneau ?), au contraire de la différence symétrique). Et ça prouve un truc plus fort et plus facile à prouver.

Édité par blo yhg

+0 -0
Auteur du sujet

C'est bien des unions (mathjax m'affiche des intersections avant de passer aux unions, je pensais que c'était le cas pour tout le monde mais tu dois rester bloqué à l'étape 1 …)

Du coup tu t'es orienté vers quoi ? en tout cas qu'elle est le "truc plus fort et plus facile à prouver" ?

Merci :)

+0 -0

Pour les unions versus les intersections, si je regarde ton code tu as bien mis \bigcap, non ? C'est des intersections en latex. Bizarre tout ça…

Cherches des manières de te représenter la situation (tu en as déjà donnée une, avec des points du cube {0,1}n, mais je ne l'ai pas trouvée très utile). Ensuite tu peux supposer ta propriété vraie de 1 jusqu'à n-1, ça ne peut pas faire de mal… Regardes alors les cas éliminés par cette récurrence. Demandes-toi ensuite ce que tu aimerais prouver pour les cas non couverts (c'est légèrement plus fort que la propriété de départ du coup mais devient plus compliqué). Il reste encore des idées à trouver après ça mais voilà le début si ça peut te débloquer.

Si tu ne trouves pas d'autre représentation, voici celle que j'ai utilisée.

Un graphe biparti : d'un côté les nœuds correspondent aux ensembles X_i et de l'autre aux entiers de 1 à n.

edit Sinon, je suis curieux de voir quelle preuve l'indication suggère… S'il y a une correction tu pourrais nous la donner quand tu auras résolu l'exo ? Quelqu'un a une idée ?

Édité par blo yhg

+0 -0

Tu as un premier ensemble, dont le cardinal est 2^n.

Et si tu regardes bien, tu as un 2ème ensemble dont le cardinal est 2^(n+1).

Or, ce 2ème ensemble est inclus dans le 1er ! Je te laisse conclure.

Édité par elegance

+0 -0

@elegance : Ça ne fonctionne pas, il faut que I et J soient disjoints. C'est aussi le premier truc auquel j'ai pensé aussi le principe des pigeons, mais je vois pas trop comment l'utiliser ici. Si c'était une différence symétrique au lieu d'unions ça fonctionnerait en enlevant à I et J les éléments qu'ils ont en commun (et on pourrait aussi faire avec de l'algèbre linéaire). Au fait, tu vois des unions ou des intersections ?

+0 -0
Auteur du sujet

Voila comment j'ai finalement traité le problème:

On se place dans $\mathbb R^n$, $\mathbb R$-ev (celui dont les vecteurs indicateurs à une composante égale à 1 forment une base) et on s’intéresse à E, l'ensemble des vecteurs de cette espace à coordonnées positifs.

On crée une partition de E en fonction de la nullité de chacune des composantes sur la base ($2^n$ classes, chaque vecteur de $\{0,1\}^n$ est un représentant de chaque classe)

On prend les vecteurs indicateurs des parties On a n+1 vecteurs non nuls pour un espace à n dimensions, ils sont donc forcément liés On prend une famille de coefficient $\alpha$ qui lie les vecteurs (en particulier $\alpha \neq (0,...,0)$)

Soit A l'ensemble des vecteurs indicateurs avec un coef positif Soit B l'ensemble des vecteurs indicateurs avec un coef negatif

N.B.: on ignore ceux avec un coef nul

Soit a la somme des vecteurs de A multipliés par $\alpha_i$, b la somme des vecteurs de B multipliés par - $\alpha_i$ On a : a - b = 0 donc a = b

En particulier on remarquera que : Soit Y,Z deux parties; Q,R les vecteurs associés, s,t dans $\mathbb {R^*_+}^2$ s.Q+t.R est dans la classe d'équivalence associée au vecteur de Y union Z

(il y a t'il un nom pour ce genre d'homomorphisme entre "demi-structure ?")

donc les parties associés aux vecteurs de A et ceux associés aux vecteurs de B recouvrent le même ensemble

Édité par regz

+0 -0

Ah oui, c'est beaucoup plus simple que ce que j'ai fait !

La mienne passe par le théorème de Hall (on peut faire en utilisant le théorème ou bien en utilisant l'idée de sa preuve algorithmique). On commence par mettre un X_i de côté. Deux cas se présentent : soit on peut trouver parmi les X_i restants un nombre k d'ensembles dont l'union est de cardinal strictement inférieur à k, soit non. Dans le premier cas, on peut appliquer une récurrence. Dans le deuxième, on peut d'après le théorème de Hall coupler les X_i avec les entiers de 1 à n, de telle sorte que chaque ensemble contienne l'élément avec lequel il est couplé. Cela nous donne un graphe orienté à n nœuds, avec un arc de i vers j si l'ensemble couplé avec i contient j. On ajoute à ce graphe un nœud correspondant au X_i que l'on a mis de côté, avec un arc vers chaque entier qu'il contient. On considère la composante du graphe constituée des nœuds accessibles depuis ce nouveau nœud. On prend un arbre couvrant de cette composante (dont la racine est le nœud ajouté, tous les arcs de l'arbre dirigés comme on l'imagine). On sépare ensuite les nœuds en deux parties, en plaçant un nœud sur deux dans chaque partie lors d'un parcours de l'arbre. Chaque entier correspondant à un nœud de l'arbre est alors contenu dans un ensemble correspondant à un nœud pour chaque partie.

La question qui reste est de comprendre le lien entre ces deux manières de faire… Peut-être que l'on peut faire quelque chose en interprétant le graphe biparti comme un application linéaire sur ℝ2n+1, je sais pas…

Sinon, qu'entends-tu par « demi-structure » ici ?

+0 -0
Auteur du sujet

C'est à dire que l'on travail sur des structures stables par une loi mais qui ne presentent pas d'inverse: d'un coté l'ensemble des parties, stable par union avec un element nul ($\emptyset$) et de l'autre les classes d'équivalences muni de l'addition. Est-ce que cela forme des semi-groupes ? peut-on parler d'isomorphisme ?

+0 -0

Cette réponse a aidé l'auteur du sujet

Est-ce que cela forme des semi-groupes ?

Oui. Dans le cas de tes classes d'équivalences on peut aussi dire que c'est un truc comme un demi-module, mais sans 0 pour le demi-anneau (on a un demi-groupe au lieu d'un monoïde). Je ne sais pas si ça a un nom, mais ça n'en mérite peut-être pas.

peut-on parler d'isomorphisme ?

Tant qu'on précise de quelle structure algébrique on parle, oui. Tu peux regarder du côté de l'algèbre universelle.

Après, je préfère voir ta preuve avec des demi-modules. On se place dans le demi-module ℕn, et on voit que c'est un sous-demi-module de ℚn, grâce à quoi on obtient l'égalité que tu as notée a = b dans ta preuve. Notons ensuite 2 le demi-anneau {0,1} muni de max pour l'addition et de la multiplication usuelle. On a un morphisme de demi-anneaux ℕ → 2 envoyant 0 sur 0 et tous les autres entiers sur 1. On a donc un morphisme de demi-modules ℕn → 2n. Additionner deux vecteurs dans 2n correspond à prendre l'union, on a ce qu'on veut.

edit Quand je dis morphisme de demi-module, c'en est pas, on a un morphisme du demi-anneau aussi. Et aussi dit comme ça il faut faire en sorte de n'avoir que des coefficients entiers dans a=b, mais au pire ce ne serait pas un problème.

Édité par blo yhg

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte