Famille de parties et déterminant

OShine · May 2023

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$.

Math Coss · May 2023

Ce serait bien de savoir interpréter ces cardinaux comme des produits scalaires de fonctions indicatrices.

OShine · May 2023

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.

JLapin · May 2023

Comment fais-tu pour intégrer sur $[0,1]$ de telles fonctions ?

OShine · May 2023

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.

JLapin · May 2023

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.

raoul.S · May 2023

Il faut reconnaître un déterminant de Gram, c'est la suite de l'indication de MathCoss...

Madec · May 2023

@OShine
Matrice de Gram abordée dans le sujet X/ENS Math A de 2022

Pour le produit scalaire considérer je pense une sommation discrète sur l'ensemble ${1,m}$

OShine · May 2023

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.

Madec · May 2023

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.

raoul.S · May 2023

OShine a dit :
Je ne connais pas les sommations discrètes.

@OShine as-tu remarqué qu'un élément de $\R^m$, qu'on écrit sous la forme $\begin{pmatrix} v_1 \\ \vdots \\ v_m \\ \end{pmatrix}$ , peut être regardé comme une fonction $f:[\![1,m]\!]\to \R$, en posant simplement $f(i):=v_i$ ?

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.

john_john · May 2023

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.

NicoLeProf · May 2023

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... )

Madec · May 2023

@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.

OShine · May 2023

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.

Non ça me parle encore moins.
Je ne maitrise pas les formes quadratiques et je vois encore moins le lien entre forme quadratique, espérance et l'exercice.

OShine · May 2023

Je ne connais que le produit scalaire pour les fonctions continues, ici les indicatrices ne sont pas des fonctions continues.

Alexique · May 2023

OShine a dit :

Je ne connais pas les sommations discrètes.
OShine:
Je ne connais que le produit scalaire pour les 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,...

OShine · May 2023

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}$.

bd2017 · May 2023

une remarque tout de même. L'hypothèse $m\in[[1,n]]$ ne sert pas, je pense.

Madec · May 2023

@ 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$.

raoul.S · May 2023

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

puis on se rend compte que quitte à compléter par des 0 on peut prendre $A$ de dimension $n\times n$ et donc $\det(A^TA)=\det(A)^2\geq 0$.

OShine · May 2023

@Madec
Je ne comprends pas ta méthode.
Je ne vois pas comment utiliser la fonction caractéristique, j'ai un produit scalaire de vecteurs pas de fonction.

Madec · May 2023

@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).

OShine · May 2023

Ok merci je ne savais pas qu'une matrice de Gram pouvait s'écrire $A^T A$.

SkyMtn · May 2023

@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.

OShine · May 2023

@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}$

Madec · May 2023

$\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$,
or on a le résultat $ \rg ( {}^t\!A\times A)\le \rg(A)$.

Il y a même égalité je pense mais l'inégalité est suffisante.
$\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$