Famille de parties et déterminant
Bonjour
Un exercice d'oral dont je n'ai pas de solution. Je n'ai pas d'idée pour commencer.
Soit $n \in \N^{*}$ et $m \in [|1,n|]$. Soit $(A_i)_{1 \leq i \leq n}$ une famille de parties de $[|1,m|]$.
On note $\forall (i,j) \in [|1,n|]^2 \ a_{ij} = | A_i \cap A_j |$.
Montrer que $\det ( (a_{ij})_{1 \leq i,j \leq n}) \geq 0$.
On note $\forall (i,j) \in [|1,n|]^2 \ a_{ij} = | A_i \cap A_j |$.
Montrer que $\det ( (a_{ij})_{1 \leq i,j \leq n}) \geq 0$.
Réponses
-
Ce serait bien de savoir interpréter ces cardinaux comme des produits scalaires de fonctions indicatrices.
-
D'accord merci.
Posons $f_i = 1_{A_i}$ et $f_j = 1_{A_j}$ où $f_i : A_i \longrightarrow \{0,1\}$.
On a $f_j f_j =1_{A_i \cap A_j}$.
J'ai donc fait apparaître un $A_i \cap A_j$.
Je définis le produit scalaire $\langle f,g \rangle = \displaystyle\int_{0}^1 f(t) g(t) dt$.
Donc $\langle f_i , f_j\rangle = \displaystyle\int_{0}^1 1_{A_i \cap A_j} (t) dt$.
Mais à partir de là je bloque un peu.
-
Comment fais-tu pour intégrer sur $[0,1]$ de telles fonctions ?
-
Impossible elles sont définies sur des ensembles de parties.
L'exercice me paraît très difficile, pourtant ce n'est pas un oral XENS, c'est niveau Centrale-Mines.
-
Tu sembles oublier que derrière un exercice d'oral, il y a un examinateur pour poser le genre de question que MathCoss a posé.Evidemment, comme il y a un écrit avant d'avoir le droit de passer cet oral, il y a très peu de chance pour qu'un élève admissible réponde la même chose que toi. Il fera plutôt une réponse un peu plus censée et ensuite, pourra suivant son niveau finir tout seul ou avec aide l'exercice.
-
Il faut reconnaître un déterminant de Gram, c'est la suite de l'indication de MathCoss...
-
Je veux bien utiliser le déterminant de Gram, mais il faudrait d'abord savoir le produit scalaire à utiliser.
Je ne connais pas les sommations discrètes. -
la fonction caractéristique de $ A_i\cap A_j$ est définie sur ton ensemble de départ $\{1, \dots,m\}$.
Sommation discrète veut dire que l'on somme la fonction sur un ensemble fini.
Et je pense (à vérifier) que cette sommation doit avoir les attributs d'un produit scalaire. -
OShine a dit :Je ne connais pas les sommations discrètes.
Or, sur $\R^m$ il y a un produit scalaire standard non ? Donc tu as un produit scalaire "standard" sur l'espace vectoriel des fonctions de $[\![1,m]\!]$ dans $\R$... applique ceci à tes fonctions caractéristiques. -
OShine : voici une façon d'interpréter les indications que tu as eues qui te parlera peut-être davantage. Munis l'ensemble discret $\{1,...,m\}$ de la probabilité uniforme et regarde la forme quadratique $(x_1,...,x_m)\mapsto\sum a_{i,j}x_ix_j$ comme l'espérance de $\big(m\sum x_i{\bf1}_{A_i}\big)^2$, espérance toujours positive ou nulle.
-
Plus simplement, je pense que l'on peut écrire un truc du genre : pour tout $i \in \{1,...,n\}$, $Card(A_i)=\displaystyle \sum_{x \in \{1, ...,m\}} \mathbb{1}_{A_i}(x)$ .Ainsi, pour tous $i,j \in \{1,...,n\}$, $Card(A_i \cap A_j)=\displaystyle \sum_{x \in \{1, ...,m\}} \mathbb{1}_{A_i \cap A_j}(x)$ .Maintenant, il faudrait prouver deux choses pour résoudre l'exo :1) pour tous $i,j \in \{1,...,n\}$, on a pour tout $x \in \{1,...,m\}$, $\mathbb{1}_{A_i \cap A_j}(x)=\mathbb{1}_{A_i}(x) \times \mathbb{1}_{A_j}(x)$ .2) Soit $E$ l'ensemble des fonctions de $\{1,...,m\}$ dans $\mathbb{R}$ . On définit $f : E \times E \rightarrow \mathbb{R}$ telle que $f(\mathbb{1}_{A},\mathbb{1}_{B})=\displaystyle \sum_{x \in \{1, ...,m\}} \mathbb{1}_{A}(x) \times \mathbb{1}_{B}(x)$ . Et Il faudrait prouver que $f$ est un produit scalaire. (? Pas sûr du tout... )
-
@NicoLeProf
ta définition de $f$ est partielle car tu ne donnes son expression que pour les fonctions caractéristiques qui ne forment pas un espace vectoriel, il faut l'étendre à l'espace vectoriel des fonctions réelles définies sur l'ensemble discret $\{1 , \dots,m\}$ que tu as noté $E$.
Et alors $f$ est bien une forme de $(E \times E) $ dans $\R$ bilinéaire symétrique définie positive. -
john_john a dit :OShine : voici une façon d'interpréter les indications que tu as eues qui te parlera peut-être davantage. Munis l'ensemble discret $\{1,...,m\}$ de la probabilité uniforme et regarde la forme quadratique $(x_1,...,x_m)\mapsto\sum a_{i,j}x_ix_j$ comme l'espérance de $\big(m\sum x_i{\bf1}_{A_i}\big)^2$, espérance toujours positive ou nulle.
Je ne maitrise pas les formes quadratiques et je vois encore moins le lien entre forme quadratique, espérance et l'exercice.
-
Je ne connais que le produit scalaire pour les fonctions continues, ici les indicatrices ne sont pas des fonctions continues.
-
Moi si j'étais examinateur à l'oral d'OS : "Merci d'être venu, c'est bon pour moi, bonne journée !".. Sans compter qu'on t'a déjà bien aidé pour trouver le bon produit scalaire etc... donc à un moment... J'attends qu'on vienne te défendre et m'expliquer que je suis méchant, vilain,...
-
Posons $\forall x,y \in \R^m ,\ \langle x,y \rangle= \displaystyle\sum_{i=1}^m x_i y_i$.
Posons $\hat{A_i} = (\hat{A_{ik}})_{1 \leq k \leq m}$ où $\hat{A_{ik}}= \begin{cases} 1 \ \text{si} \ k \in A_i \\ 0 \ \text{si} \ k \notin A_i \end{cases}$.
$\hat{A_i} \in \R^m$.
On a alors $\langle \hat{A_i} ,\hat{A_j} \rangle=\displaystyle\sum_{k=1}^m \hat{A_{ik}} \hat{A_{jk}} =| A_i \cap A_j |$.
Soit $X=(x_1,x_2, \cdots, x_n) \in \R^n$.
Posons : $Y=\displaystyle\sum_{i=1}^n x_i \hat{A_i} \in \mathcal M_{m1}(\R)$. Donc $\langle Y,Y \rangle=\langle \displaystyle\sum_{i=1}^n x_i \hat{A_i} ,\displaystyle\sum_{j=1}^n x_j \hat{A_j} \rangle$.
Par bilinéarité du produit scalaire : $\langle Y,Y \rangle= \displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^n x_i x_j \langle \hat{A_i}, \hat{A_j} \rangle$.
Finalement : $\boxed{\langle Y,Y \rangle=\displaystyle\sum_{i=1}^n \displaystyle\sum_{j=1}^n x_i x_j | A_i \cap A_j|}$.
Soit $P=(|A_i \cap A_j |)_{1 \leq i,j \leq n}$
Un calcul facile donne $XP X^T=\langle Y,Y \rangle$.
On a donc montré $\boxed{\forall X \in \R^n \ XPX^T=\langle Y, Y \rangle= || Y||^2 \geq 0}$.
$P$ est une matrice symétrique positive, donc $Sp(P) \subset \R^{+}$.
Donc $\boxed{ \det P \geq 0}$.
-
une remarque tout de même. L'hypothèse $m\in[[1,n]]$ ne sert pas, je pense.
-
@ Oshine
Première ligne $ x$ et $ y$ sont des vecteurs de $\R^m$
ta définition du vecteur $\hat A_i$ est auto référente on devrait voir la notation habituelle de la fonction caractéristique pour ses $m$ composantes .
Par ailleurs la suite est un peu confuse tu introduits des coordonnées dont on n'a pas vraiment besoin.
La matrice qui nous intéresse est une matrice $n\times n$ qui s'écrit comme ${}^t\!A A$ ou $A$ est une matrice $m \times n$ constituée des $n$ vecteurs correspondants aux valeurs prises par les $n$ fonctions caractéristiques aux points $1,2, \dots,m$.
Par construction les coefficients sont des produits scalaires usuels de vecteurs de $\R^m$
Ensuite on déroule le classique matrice symétrique donc à valeurs propres réelles puis la positivité des valeurs propres par l'introduction d'un vecteur propre $X$ associé à $\lambda$ et $ {}^t\!X {\,}^t\!AA X = \lambda<X,X>\, =\,< AX, AX>\ge 0$. -
On peut faire un peu plus court peut-être en commençant par remarquer comme Madec ci-dessus que :Madec a dit :La matrice qui nous intéresse est une matrice $nxn$ qui s'écrit comme $tA A$ ou $A$ est une matrice $m x n$
constituée des n vecteurs correspondants aux valeurs prises par les n fonctions caractéristiques aux points 1,2, ..m
-
@OShine
Je ne te comprends pas bien , dans ton développement tu as introduit
$ <\hat A_i,\hat A_j>$ qui est bien l'expression d'un produit scalaire de 2 vecteurs de $ \R^m$ chacun de ses 2 vecteurs ayant des composantes formées par les valeurs que prennent les fonctions caractéristique des ensembles $A_i$ et $A_j$ aux points $\{1,2 ,\dots,m\}$ ;
tu as montré par ailleurs que cette expression était égale à $ | A_i \cap A_j |$.
Donc tu as quasiment fini, tu reconnais une matrice de Gram $G= {\,}^t\!A A$ etc. (avec la remarque de raoul.S qui permet de conclure encore plus vite sur la positivité du déterminant sans passer par le signe des valeurs propres).
-
Ok merci je ne savais pas qu'une matrice de Gram pouvait s'écrire $A^T A$.
-
@OShine Étant donnée une famille $u_1,\ldots,u_n$ de vecteurs dans un espace euclidien $E$, en notant $A$ la matrice des coordonnées de $(u_1,\ldots,u_n)$ dans une base orthonormée de $E$ quelconque, tu as $G(u_1,\ldots,u_n) = A^\mathsf T A$ où $G(u_1,\ldots,u_n)$ désigne la matrice de Gram.
-
@SkyMtn
Démontrons ce résultat.
Soit $\mathcal B=(e_1, \cdots, e_n)$ une base orthonormée de $E$.
$\forall j \in [|1,n|] \ u_j=\displaystyle\sum_{i=1}^n u_{ij} e_i$
Donc $\langle u_i,u_j \rangle= \langle \displaystyle\sum_{p=1}^n u_{pi} e_p,\displaystyle\sum_{q=1}^n u_{qj} e_q \rangle= \displaystyle\sum_{p=1}^n u_{pi} \displaystyle\sum_{q=1}^n u_{qj} \delta_{pq} $
Donc $\langle u_i,u_j \rangle= \displaystyle\sum_{p=1}^n u_{pi} u_{pj}=[A^T A]_{ij}=\displaystyle\sum_{k=1}^n [A^T]_{ik} [A]_{kj}$ -
$\newcommand{\rg}{\mathrm{rg}}$Une petite remarque (suite à l'idée de raoul.s de rajouter des zéros à la matrice $A$ afin de la rendre carrée)
L'énoncé précise $m\leq n$On a vu que la matrice $ B$ dont on cherche le signe du déterminant pouvait s'écrire $B={\,}^t\!A \times A$,Il y a même égalité je pense mais l'inégalité est suffisante.
or on a le résultat $ \rg ( {}^t\!A\times A)\le \rg(A)$.
$\rg(A)\le \min( m,n) = m$
et comme $B$ est une matrice $n\times n$ alors $B$ est non inversible si $m<n$ donc de déterminant nul.
si $m=n$ alors $A$ est une matrice carrée et $ \det(B)= (\det(A))^2 \ge 0$
-
Ok merci je connaissais bien cette inégalité sur le rang, elle tombe souvent dans les sujets de concours.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres