Matrice triangulaire et produit
Bonjour
Ma solution à la question $1$ est-elle correcte et suffisante ? J'y réfléchis depuis 2 jours, je viens de trouver une solution ce matin.
J'ai fait $A=(a_{ij})_{1 \leq i,j \leq d}$ puis $\boxed{(A^2)_{i,j}=\displaystyle\sum_{k=i}^j a_{ik}a_{kj}}$ car $A$ est triangulaire supérieure.
En posant $U=(\displaystyle\sum_{k=i}^j a_{i k}a_{kj})_{ij}$
On a : $(A^3)_{i,j}= \displaystyle\sum_{k=1}^d a_{ik} u_{kj}$ puis $\boxed{(A^3)_{ij}= \displaystyle\sum_{l=i}^j \displaystyle\sum_{k=l}^j a_{il} a_{lk} a_{kj}}$
La formule vérifie bien les conditions 1 et 2. Par itération, on obtient la formule générale. La condition $3$ est aussi vérifiée car $1 \leq i \leq l \leq j \leq d$ et il y a $d-1$ possibilités pour avoir $i \ne j$. Puis $1 \leq i \leq l \leq k \leq j \leq d \leq d$ donc il y a au plus $d-1$ possibilités d'avoir $l \ne k$ etc...
Ma solution à la question $1$ est-elle correcte et suffisante ? J'y réfléchis depuis 2 jours, je viens de trouver une solution ce matin.
J'ai fait $A=(a_{ij})_{1 \leq i,j \leq d}$ puis $\boxed{(A^2)_{i,j}=\displaystyle\sum_{k=i}^j a_{ik}a_{kj}}$ car $A$ est triangulaire supérieure.
En posant $U=(\displaystyle\sum_{k=i}^j a_{i k}a_{kj})_{ij}$
On a : $(A^3)_{i,j}= \displaystyle\sum_{k=1}^d a_{ik} u_{kj}$ puis $\boxed{(A^3)_{ij}= \displaystyle\sum_{l=i}^j \displaystyle\sum_{k=l}^j a_{il} a_{lk} a_{kj}}$
La formule vérifie bien les conditions 1 et 2. Par itération, on obtient la formule générale. La condition $3$ est aussi vérifiée car $1 \leq i \leq l \leq j \leq d$ et il y a $d-1$ possibilités pour avoir $i \ne j$. Puis $1 \leq i \leq l \leq k \leq j \leq d \leq d$ donc il y a au plus $d-1$ possibilités d'avoir $l \ne k$ etc...
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je voulais tester 2-3 questions. Je sais que ce n'est pas mon niveau mais j'ai je pense réussi la question 3a.
La 3b c'est du dénombrement et je suis faible dans ce domaine.
En calculant $A^3$ on comprend la formule demandée.
Heuristique voici le rapport :
Je ne trouve pas que la récurrence soit utile ici, elle n'apporte aucune clarté au raisonnement, je pense que dire que ça marche pour $n=2$ et $n=3$ puis que c'est le même raisonnement pour $n$ quelconque est beaucoup plus clair.
Montrons par récurrence sur $n$ que $(A^n)_{ij}=\displaystyle\sum_{i_1,j_1, \cdots, i_n,j_n \in \varepsilon_n (i,j)} a_{i_1 j_1} \times \cdots a_{i_n j_n}$
Au rang $n=1$ on a $(A)_{ij}=a_{ij}$ et le résultat est évident en choisissant $i_1=i$ et $j_1= j$.
Supposons $H(n)$ vraie.
On a $(A^{n+1})_{ij}= \displaystyle\sum_{k=1}^d \displaystyle\sum_{i_1,j_1, \cdots, i_n, k \in \varepsilon_n (i,j)} a_{i_1 j_1} \times \cdots a_{i_n k} a_{kj}$
Ce qui donne, comme la matrice $A$ est triangulaire supérieure :
$(A^{n+1})_{ij}= \displaystyle\sum_{k=i_n}^j \displaystyle\sum_{i_1,j_1, \cdots, i_n , k \in \varepsilon_n (i,j)} a_{i_1 j_1} \times \cdots a_{i_n k} a_{kj}$
Il suffit de poser $k=i_{n+1}$ et $j_{n+1}=j$ ce qui fournit :
$\boxed{(A^{n+1})_{ij}= \displaystyle\sum_{i_1,j_1, \cdots, i_n , j_n , i_{n+1} , j_{n+1} \in \varepsilon_{n+1} (i,j)} a_{i_1 j_1} \times \cdots a_{i_n j_n} a_{i_{n+1} j_{n+1}} }$
On vérifie facilement que $i_{n+1} \leq j_{n+1}$ car $k \leq j$ par définition de la somme.
J'ai fait n'importe quoi car je ne comprends pas les sommes écrites de cette façon.
Je vais essayer de trouver ma propre expression de $A^n$ en continuant comme j'ai fait pour $n=3$ .
On a $(A^2)_{ij} = \displaystyle\sum_{i_1 =1}^d a_{i i_1} a_{i_1 j}$
Puis $(A^3)_{ij}= \displaystyle\sum_{i_2 =1}^d \displaystyle\sum_{i_1 =1}^d a_{i i_1} a_{i_1 i_2} a_{i_2 j}$
Puis $(A^4)_{ij}=\displaystyle\sum_{i_3 =1}^d \displaystyle\sum_{i_2 =1}^d \displaystyle\sum_{i_1 =1}^d a_{i i_1} a_{i_1 i_2} a_{i_2 i_3 } a_{i_3 j}$
Et $\boxed{(A^n)_{ij}= \displaystyle\sum_{i_{n-1} =1}^d \cdots \displaystyle\sum_{i_3 =1}^d \displaystyle\sum_{i_2 =1}^d \displaystyle\sum_{i_1 =1}^d a_{i i_1} a_{i_1 i_2} a_{i_2 i_3 } \times \cdots \times a_{i_{n-2} i_{n-1}} a_{i_{n-1} j} }$
C'est correct jusqu'ici ?
Il y a bien $n-1$ somme pour le calcul de $A^n$.
On a $(A^n)_{ij}= \displaystyle\sum_{j_{n-1} =1}^d \cdots \displaystyle\sum_{j_3 =1}^d \displaystyle\sum_{j_2 =1}^d \displaystyle\sum_{j_1 =1}^d a_{i j_1} a_{j_1 j_2} a_{j_2 j_3 } \times \cdots \times a_{j_{n-2} j_{n-1}} a_{j_{n-1} j}$
La fait que $A$ est triangulaire permet d'obtenir :
$\boxed{(A^n)_{ij}= \displaystyle\sum_{j_{n-1} =j_{n-2}}^j \cdots \displaystyle\sum_{j_3 =j_2}^{j_4} \displaystyle\sum_{j_2 =j_1}^{j_3} \displaystyle\sum_{j_1 =i}^{j_2} a_{i j_1} a_{j_1 j_2} a_{j_2 j_3 } \times \cdots \times a_{j_{n-2} j_{n-1}} a_{j_{n-1} j} }$
En comparant à la formule donnée par l'énoncé, on a bien $i=i_1$, puis $j_1=i_2$, $j_2=i_3$ etc $j_n =j$
Montrons que $\forall k \in [|1,n|] \ i_k \leq j_k$
D'après la formule encadrée $i_1 \leq j_1 \leq j_2 \leq j_3 \leq \cdots \leq j_{n-2} \leq j_{n-1} \leq j$ et comme $j_k =i_{k+1}$ on voit facilement que $i_k \leq j_k$
Il reste à montrer le dernier point, qu'il existe au plus $d-1$ valeurs tels que $i_k \ne j_k$.
Ce point là je n'ai pas réussi, je ne comprends pas ce passage.
Le rapport du jury dit que le 3ème point est immédiat, je ne vois pas pourquoi.
Dans le cas où $1 =i_1 < j_1 = i_2 < j_2 = i_3 < \cdots i_n < j_n = d$ on a pourtant $d$ valeur qui vérifient $i_k \ne j_k$ non ?
Je n'arrive pas à démontrer qu'il existe au plus $d-1$ valeurs tels que $i_k \ne j_k$ en utilisant les points $1$ et $2$.
Si je combine les points $1$ et $2$ je trouve :
$\boxed{1 \leq i_1 \leq j_1 =i_2 \leq j_2 =i_3 \leq j_3 \leq \cdots \leq j_{n-1} =i_n \leq j_n \leq d}$
Que faire avec ça ? Ce point me bloque depuis hier.
Par contre la question $b$ m'a l'air archi difficile, aucune idée de comment démarrer
Il y a donc $\displaystyle\binom{n-1+(j-i)}{n+1}$ suites $(u_i)_{0 \leq i \leq n}$ strictement croissantes de $n+1$ entiers tels que $u_0=0$ et $u_n= n+(j-i)$
Mais je ne comprends pas le rapport avec les $\varepsilon_n(i,j)$
Déterminons le cardinal du nombre d'applications strictement croissantes de $[|0,n|]$ dans $[|0,n+(j-i) |]$.
Soit $f : [|0,n|] \longrightarrow [|0,n+(j-i) |]$ une application strictement croissante. Alors $f$ est nécessairement injective. Pour construire $f$, il faut se donner une telle injection, il y a $A_{n+1+(j-i)}^{n+1}$ choix.
Parmi toutes ces injections, un certain nombre ont la même image $Im f =\{ f(0), \cdots, f(n) \}$ il en a $(n+1)!$ c'est le nombre de façons de permuter les $n+1$ éléments de $Im(f)$.
Parmi ces $(n+1)!$ injections de même image, une seule est strictement croissante.
Le nombre d'applications strictement croissantes de $[|0,n|]$ dans $[|0,n+(j-i) |]$ est $\boxed{\binom{n+1+(j-i)}{n+1}}$
2) Montrons qu'il y a au plus $d-1$ valeurs $k$ telles que $i_k \ne j_k$.
D'après les deux premiers points, on a $1 \leq i_1 \leq j_1 = i_2 \leq j_2 =i_3 \leq j_3 \leq \cdots \leq i_n \leq j_n \leq d$
Si on avait $d$ valeurs distinctes ou plus, pour $d=4$ par exemple la configuration $1= i_1 < j_1 = i_2< j_2 = i_3 < j_3 = i_4 < j_4 =d=4$ et ceci est impossible car dans ce cas on obtient $d=5$ ce qui est absurde.
Pour le cas général, le même raisonnement s'applique.
3) Je ne comprends pas le rapport entre les suites strictement croissantes et $\varepsilon_n(i,j)$.
1) Le nombre de suites strictement croissantes $(u_i)_{0 \leq i \leq n}$ de $n+1$ éléments qui vérifient $u_0=0$ et $u_n=n+(j-i)$ est le nombre d'applications strictement croissantes $f$ de $[|0,n|]$ dans $[|0,n+(j-i) |]$ qui vérifient les conditions $f(0)=0$ et $f(n)=n+(j-i)$
Pour détermine le cardinal des applications $f : [|0,n|] \longrightarrow [|0,n+(j-i) |]$ avec les conditions $f(0)=0$ et $f(n)=n+(j-i)$, revient à choisir une partie de cardinal $n-1$ parmi les $n-1+(j-i)$ éléments restants car $f(0)$ et $f(n)$ sont fixés, qui constituera son image, l'ordre des éléments étant imposé par la stricte croissance.
Ainsi, son cardinal vaut $\binom{n-1+(i-j)}{n-1} \times 1= \boxed{\binom{n-1+(j-i)}{n-1} }$
2) Montrons qu'il existe au plus $d-1$ valeurs tels que $i_k \ne j_k$.
Pour $d=3$ par exemple, le cas où on a plus de $i_k \ne j_k$ est le suivant : $1 \leq i_1 <j_1 =i_2 <j_2=i_3 <j_3 \leq 3$.
Il y a 3 inégalités strictes sont associées aux $j_1,j_2,j_3$, on remarque que le nombre d'inégalités strictes est égal à $d$.
Ceci est impossible d'avoir $d$ valeurs $i_k \ne j_k$ car on aurait $4$ entiers différents compris entre $1$ et $3$.
Dans le cas général, le cas où on a le plus d'éléments qui vérifient $i_k \ne j_k$ est le suivant :
On prend $i_1 = 1$ et $j_n=d$.
On a : $1 \leq i_1 < j_1 =i_2 <j_2=i_3 < \cdots < j_{n-2} =i_{n-1} < j_n \leq d$ il y a $d$ inégalités strictes, donc $d+1$ éléments distincts à placer dans $[|1,d|]$ de cardinal $d$ ce qui est impossible.
3) Je ne vois toujours pas le lien entre $\varepsilon_n(i,j)$ et les suites strictement croissantes vues précédemment.
3) On a la suite $i_1,j_1 =i_2,j_2=i_3, \cdots, j_{n-2}=i_{n-1},j_{n-1}=i_n,j_n$
Donc la suite $i_1,j_1,i_2,j_2, \cdots, i_{n-1},j_{n-1},i_n,j_n$ est croissante d'après les hypothèses, en ajoutant $1$ à $i_1$ puis $2$ à $j_1$ puis $3$ à $i_3$ etc, on rend la suite strictement croissante.
Mais je n'ai pas vraiment compris pourquoi ça ne modifie pas le cardinal ni le rapport avec les suites $(u_i)_{0 \leq i \leq n}$ de $n+1$ entiers telles qui $u_0=0$ et $u_n=n+(j-i)$.
OShine, tu m'étonneras toujours. Un nouveau spectacle toujours surprenant, avec régulièrement des nouvelles blagues.
Là tu essaies de démontrer une certaine égalité, et tu n'y arrives pas. Soit, jusque là, c'est banal.
Mais en fait, ce que tu nous dis, c'est que tu ne sais pas ce que tu dois démontrer.
Si on me demande de démontrer que $x= y \varepsilon z$ , la première chose que je vais faire, c'est d'essayer de savoir ce que c'est que ce symbole $\varepsilon$. Et tant que je ne saurai pas ce que c'est, je ne vais pas me lancer dans des calculs idiots.
Avant de prendre la route, je demande à mon GPS si je dois aller à droite ou à gauche. Je ne pars pas au hasard sans savoir où je dois aller.
J'aime ce forum, J'aime ces surprises.
Ce qui me surprendrait vraiment, la surprise qui serait vraiment top, ce serait qu'un jour, tu saches faire un exercice comme il faut.
Bd2017 après plus d'une heure de réflexion et de recherche acharnée, je pense avoir enfin trouvé même si j'ai un doute de pourquoi les opérations réalisées conservent le cardinal. C'est vraiment dur ENS maths D, dès les premières questions, c'est un casse-tête.
Ok pour le $\Delta$ j'avais oublié qu'on travaillait avec une suite croissance d'entiers, donc la différence donne un entier nul ou positif.
Dans $\varepsilon_n(i,j)$ on a les $i_1,j_1, \cdots, i_n,j_n$ mais avec les égalités on a $i=i_1,i_2,i_2,i_3,i_3, \cdots, i_{n-1}i_n,i_n, j_n=j$
$\varepsilon_n(i,j)$ est donc défini par $n+1$ termes qui sont $\boxed{\{i=i_1, \cdots, i_n,j_n=j \}}$
La suite $i=i_1,i_2,i_2,i_3,i_3, \cdots, i_{n-1}i_n,i_n, j_n=j$ est une suite d'entiers qui contient $n+1$ éléments et ces entiers sont compris entre $i$ et $j$.
La suite est croissante, pour la rendre strictement croissante, on a ajoute $0$ à $i$, $1$ à $i_2$, $2$ à $i_3$ etc $n-1$ à $i_n$ et $n$ à $j_n$.
Si on translate de $-i$ on trouve une suite d'entiers entre $0$ et $n+(j-i)$, elle est strictement croissante.
Il me semble que la translation ne modifie pas le cardinal par bijectivité non ? Pour le fait d'ajouter des nombres aux termes de la suite pour la rendre strictement croissante, pourquoi ça ne modifie pas le cardinal ?
La suite du sujet, ces questions ont pour but de démontrer le théorème de Gelfand.
J'ai écrit $|(A^n)_{ij}| \leq \displaystyle\sum_{i_1, \cdots, j_n \in \varepsilon_n(i,j)} | a_{i_1 j_1} | \times \cdots \times | a_{i_n j_n} |$
Mais je ne vois pas comment majorer les $a_{i_1 j_1}$ etc ...
Merci je vais chercher avec cette indication. J'avais oublié l'hypothèse triangulaire qui donne les valeurs propres sur la diagonale !
Si $\rho(A)=0$ alors l'unique valeur propre de $A$ est $0$ et donc $A$ est nilpotente, l'indice de nilpotence étant inférieur à $d$, on a $A^n=0$ donc l'inégalité est vraie.
Supposons $\rho(A) \ne 0$ alors $M=\dfrac{1}{\rho(A)} \max_{ i \ne j} |a_{ij} |$ est bien définie et $M>0$ car $A$ est non nulle.
On a $|(A^n)_{ij} | \leq \displaystyle\sum_{i_1, \cdots j_n \in \varepsilon_n(i,j)} |a_{i_1 j_1}| \times \cdots \times |a_{i_n j_n}|$
Mais je bloque ici comment savoir qui sont les diagonaux et qui sont ceux qui ne sont pas sur la diagonale ?
Il y a au plus $d-1$ valeurs telles que $i_k \ne j_k$ donc au moins $d$ valeurs telles que $i_k =j_k$.
Mais on ne sait pas leur nombre exact c'est ça qui me bloque.
Repasser à la somme bizarre m'embrouille. Je dois majorer $|a_{i_1 j_1}| \times \cdots \times |a_{i_n j_n}|$ et sortir le majorant de la somme.
Le nombre de termes dans $\varepsilon_n(i,j)$ c'est son cardinal mais dans le produit on a que $n$ termes je ne comprends pas le lien entre les deux.
D'après le rapport du jury je ne suis pas le seul à avoir écrit des bêtises, certains ont dit qu'il y avait $n-(d-1)$ coefficients diagonaux.
Il y a $n$ termes à majorer qui sont $|a_{i_1 j_1}| , \cdots, |a_{i_n j_n} |$ je n'ai pas compris le lien avec les termes de la diagonale et ceux hors diagonale.
On a $|(A_{ij}| \leq M^{d-1} \rho(A)^{n-1} \displaystyle\sum_{i_1, \cdots, j_n \in \varepsilon_n (i,j)} = \boxed{ M^{d-1} \rho(A)^{n-1} \binom{n-1+(j-i)}{n-1}}$
Je n'ai pas compris comment tu majores le coefficient binomial.
J'ai écrit $ \binom{n-1+(j-i)}{n-1}= \dfrac{ (n-1+(j-i) )!}{(n-1)! (j-i)!} \leq n \times (n+1) \times \cdots \times (n + (j-i-1) )$
Je bloque ici.