Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
106 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Un exo d'Ulm un peu tordu

Envoyé par YvetteP 
Un exo d'Ulm un peu tordu
il y a trois mois
Bonjour aux algébristes du mardi

`Montrer que si $A\in M(n,\R)$ vérifie $a_{i,i}=1$ et ${\color{red}{|}}a_{i,j}{\color{red}{|}}\leq1/\sqrt n$ pour $i\neq j$, alors son rang est $\geq n/4$.

Toute indication, même naïve, serait pour moi la bienvenue.
Cordialement,
Yvette.

[Correction en rouge, selon le message [www.les-mathematiques.net] AD]



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
JLT
Re: Un exo d'Ulm un peu tordu
il y a trois mois
avatar
On ne peut pas dire que j'ai une indication car je n'ai pas cherché jusqu'au bout, mais voici peut-être une idée.

On peut supposer que $n=4m$, quitte à tronquer la matrice. On essaye de montrer que les $m$ premières lignes sont linéairement indépendantes. Alors on met la matrice sous forme échelonnée. La première étape consiste à remplacer pour tout $i\geqslant 2$ la ligne $L_i$ par $L_i-a_{i1}L_1$. Les coefficients de la matrice $(a_{ij})_{i,j\geqslant 2}$ sont perturbés d'au plus $\frac{1}{4m}$. On continue... Et je ne sais pas si ça marche à la fin.

Edit : en fait je crois que ça ne mène à rien.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par JLT.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Au cas où: $-50000$ est inférieur à $1/\sqrt{5}$.

Je pense que marco et side vont remarquer cette question et qu'ils vont la mitrailler avec leur puissance grinning smiley

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
JLT
Re: Un exo d'Ulm un peu tordu
il y a trois mois
avatar
Ah pardon j'avais cru voir une valeur absolue là où il n'y en a pas. Donc ma tentative ne marche pas.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
bonjour, JLT,

si, si, il y a bien une valeur absolue (je viens de vérifier dans la RMS de janvier 19).

Yvette : si tu as mon livre sur les ev préhilbertiens, j'arrive pour le même prix à minorer le rang par $n/2$. Un tuyau pour aborder l'exo : écris que $AX=0$ ssi $(I-A)X=X$ et ensuite un p'tit coup de Cauchy-Schwarz. Je l'ai sélectionné dans mes exos car le ressort en est vraiment euclidien.

Amitiés à tous, j__j



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par john_john.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Je viens de regarder le corrigé dans la rms 129_3, exo 34 : elle est sans rapport apparent avec la mienne mais est, elle aussi, typiquement euclidienne (quoiqu'elle ne minore le rang que par $n/4$. Fi donc ! winking smiley)



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par john_john.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Oups!
Pardon

oui j'ai oublié de mettre des valeurs absolues autour des $a_{ij}$...

Hélas, je n'ai pas ton bouquin John. Peut-on le télécharger sur un site russe? Ou bien le recevoir en cadeau? grinning smiley

Je crois avoir un idée. Dire que les composantes d'un vecteur unitaire quelconque d'un sev sont majorées en valeur absolue entraîne une majoration de sa dimension.

Cordialement
Yvette
Re: Un exo d'Ulm un peu tordu
il y a trois mois
La dimension d'un vecteur?

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Yvette : pour les cadeaux, envoie un MP à Yannguyen ; il me semble très au courant de ce qui concerne c&m.

Un site russe : on peut toujours tenter... Video meliora proboque, deteriora sequor.

Quant à ta question : oui, tu as bien vu ; si un sev de $\R^n$ est de dimension trop grande (par rapport à $n$), on trouvera facilement une CL de vecteurs d'une BON d'icelui qui soit elle-même de norme $1$ et dont une des composantes dépasse (en valeur absolue) la majoration $1/\sqrt2$ fournie par les Sieurs Cauchy et Schwarz. À toi de conclure à présent.

À propos : en quoi cet énoncé est-il tordu ? Je le trouve joli au contraire.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par john_john.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Le rang est une application "semi-continue inférieurement" (je ne sais jamais entre inf et sup grinning smiley ) autrement dit, il ne peut pas baisser d'un coup. La preuve de ça, échelonne au sens où elle donne des $e_1,e_2,..$ à partir desquels en terme d'éloignement il peut baisser de $1$, de $2$, etc. Evidemment à $n$ fixé.

Je ne dis pas pour autant que ça va donner une preuve, mais JJ en a fourni une.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Un exo d'Ulm un peu tordu
il y a trois mois
La dimension d'un vecteur?

Bonsoir, Christophe,
je pense que notre amie parlait de la dimension du sev ; du moins, c'est ainsi que j'ai compris la question.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
En complément (mais seulement à ce titre), si $A \in M_n(\mathbb{C})$ vérifie $\| A \|_{\textrm{F}} > 0$, alors
$$\textrm{rg} \, (A) \geqslant \frac{\left| \textrm{tr} (A) \right|^2}{\| A \|_{\textrm{F}}^2}$$
où $\| \dotsc \|_{\textrm{F}}$ est la norme de Frobenius. Avec les hypothèses de l'énoncé, on a sauf erreur
$$n \leqslant \| A \|_{\textrm{F}}^2 \leqslant 2n-1$$
de sorte que $\textrm{rg} \, (A) \geqslant \frac{1}{2}n$.

Edit. Correction effectuée après les messages de Lou16 et John_john plus bas, que je remercie.



Edité 3 fois. La dernière correction date de il y a trois mois et a été effectuée par noix de totos.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Bonsoir,


Correction je viens de comprendre la preuve de john_john
Joli !

Mais toujours pas celle de noixdetotos...


Ajout : j'ai supprimé ce que j'avais rédigé car plus "encombrant" que la preuve de john_john
Je signale juste cette preuve plus compliquée : si on sait prouver "facilement" (ce qui ne l'est pas) $\sum_{sp M} |\lambda|^2 \le \sum_{ij} |a_{ij}|^2$ (1), alors en considérant $(tr M)^2$ et en utilisant l'inégalité de Cauchy-Schwarz dans $\C^r, r=rg M$, on prouve l'inégalité $rg M \ge n/2$ (en fait très légèrement mieux).

Ajout 2 : si on sait réduire en b.o.n. hermitienne (ce qui ne se fait pas en prépas), alors le résultat annexe peut se montrer en montrant par récurrence que toute matrice de $M_n(\C)$ est trigonalisable en b.o.n (hermitienne) et l'inégalité (1) en découle.



Edité 5 fois. La dernière correction date de il y a trois mois et a été effectuée par side.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Noix de totos, Side : avec ma méthode, j'arrive aussi à un peu mieux que $n/2$ avec les hypothèses de l'énoncé initial (dans mon calcul, $n/2$ correspond à l'hypothèse un peu plus générale de majoration en valeur absolue des coefficients par $1/\sqrt{n-1}$). En revanche, elle ne conduit pas à $2n/3$. Je vais réfléchir en outre à l'inégalité de NDT à titre d'exo.

Bonne soirée, j__j
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Citation
john_john
Quant à ta question : oui, tu as bien vu ; si un sev de $\R^n$ est de dimension trop grande (par rapport à n), on trouvera facilement une CL de vecteurs d'une BON d'icelui qui soit elle-même de norme 1 et dont une des composantes dépasse (en valeur absolue) la majoration $\dfrac{1}{\sqrt{2}}$.
J'arrive à le montrer par une méthode non constructive, mais je n'ai pas réussi à « trouver facilement » cette combinaison linéaire. J'ai raté une astuce ?
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Bonjour,

L'inégalité (que je ne connaissais pas) de Noix de Totos, est bien adaptée au problème initial mais donne, pour la matrice $A$ de ce dernier:
$$\mathrm {rg}(A)\geqslant \dfrac {n^2}{2n-1}\:\text{ et non }\:\mathrm {rg}(A)\geqslant \dfrac {2n^2}{3n-1}.$$Soit $A \in \mathcal M_n (\C), \:\: r= \mathrm {rg}(A).\:\:$ On a: $\:\: \ker A =\ker A^*A, \:\: r = \mathrm {rg}(A^*A).$
$\exists P \in \mathcal U_n(\C),\:\: A^*A =P \begin{pmatrix}D&0\\0&0 \end{pmatrix}P^*,\:\:\: D\in \mathrm {GL}_r(\C).\:\:\: \ker A =\ker A^*A,\:\:$ donc: $\: A =P \begin{pmatrix}B&0\\C&0 \end{pmatrix}P^*,\:\: B \in \mathrm {GL}_r (\C).$
Ainsi : $ \:\: A^*=P \begin{pmatrix}B^*&C^*\\0&0 \end{pmatrix}P^*, \:\:AA^*=P \begin{pmatrix}BB^*&BC^*\\CB^*&CC^*\end{pmatrix}P^*, \qquad \mathrm {Tr}(AA^*)=\mathrm {Tr} (BB^*)+ \mathrm {Tr}(CC^*) \quad (1).$
$|\mathrm{Tr}(A) |^2=|\mathrm{Tr}(B) |^2=\left|\displaystyle \sum _{i=1}^r b_{ii}\right| ^2\leqslant r \displaystyle \sum _{i=1} ^r |b_{ii}| ^2\leqslant r \mathrm{Tr}(BB^*)\leqslant r\left( \mathrm{Tr}(BB^*)+\mathrm{Tr}(CC^*) \right) \overset {(1)} = r\mathrm{Tr}(AA^*) = r \|A\|_F^2.$
$$\left|\mathrm {Tr}(A) \right| ^2 \leqslant \mathrm {rg}(A)\: \|A\|_F^2.$$



Edité 6 fois. La dernière correction date de il y a trois mois et a été effectuée par LOU16.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Bonjour, Guego,

effectivement, mon indication n'était vraiment pas commode à manipuler ; procédons plutôt par majoration de la dimension en fonction du majorant imposé (et non pas l'inverse). Si $E$ est un sev de $\R^n$ dans lequel tous les vecteurs unitaires ont leurs composantes majorées en valeur absolue par $\alpha\in]0,1[$, alors la dimension $p$ de $E$ est $\leqslant n\alpha^2$.

Tu prends une b.o.n. $(x_1,...,x_p)$ de $E$ et écris $x_1={}^t\!(x_{1,1},...,x_{n,1})$, etc. Pose $\nu_1=\sqrt{x_{1,1}^2+\cdots+x_{1,p}^2}$ (=la norme de la première ligne de la matrice canonique $M$ des $x_\ell$) et considère $\xi_1=(x_{1,1}x_1+\cdots+x_{1,p}x_p)/\nu_1$ ; c'est un vecteur unitaire dans $E$ et cela montre que $\nu_1\leqslant\alpha$ puisque $\nu_1$ est la première composante de $\xi_1$. Fais de m\^eme avec les autres lignes de $M$ puis additionne, ce qui donne $\sum\nu_\ell^2\leqslant n\alpha^2$. Or, cette somme n'est autre que $p$.

Bien cordialement, j__j
Re: Un exo d'Ulm un peu tordu
il y a trois mois
L'inégalité de Noix de Totos s'établit aussi facilement si l'on admet l'existence d'une décomposition polaire : on écrit en effet $A=US$, avec $U$ orthogonale (ou unitaire) et $S$ symétrique (ou hermitienne) positive. En outre, $A$ et $S$ ont la même norme de Frobenius et le même rang, et $|{\rm tr}\,A|$ est majorée par ${\rm tr}\,S$.

Yvette ne nous a toujours pas prouvé la torsion (sic !) de cet exercice !! au contraire, ces échanges sont intéressants, non ? Certes, on me dira que l'un n'empêche pas l'autre.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Lou16 : tu es sûr de ta minoration ?

Quant aux inégalités de ce type, il y a en d'autres, comme par exemple
$$\textrm{rg} \, (A) \geqslant \frac{2 \left\{ \textrm{Re} \left( \textrm{tr}A \right) \right\}^2}{\|A\|_{\textrm{F}}^2 + \textrm{Re} \left( \textrm{tr} (A^2) \right)}
$$ ou
$$\textrm{rg} \, (A) \geqslant \frac{\| A \|_{\textrm{F}}^4}{\textrm{tr} \left( \left( A^\star A\right)^2 \right)}.$$



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Bonjour,

Il y'a aussi la minoration suivante (peu efficace ici car donne une minoration de l'ordre de $\sqrt n$) : $\forall A, rg(A) \ge \sum_j |a_{jj}|/||C_j||_1$ (la sommation se fait donc sur indices pour lesquels la colonne correspondante est non nulle) où les $C_j$ sont les colonnes non nulles de $A$ et $||. ||_1$ la norme $1$ dans $\C^n$.

Pour obtenir une minoration d'une autre façon $\sqrt n$ on peut aussi par multiplication des lignes se ramener à une matrice stochastique $M'$ qui a donc un spectre dans le disque unité et qui donc vérifie $|tr(M')| \le rg M'=rg M$

Toujours en $\sqrt n$ on peut rechercher une majoration uniforme des valeurs propres du spectre en raisonnant sur le système $MX=\lambda X$...

Ces méthodes sont en fait les mêmes et exploitent la connaissance d'une majoration uniforme des valeurs propres de $M$ ou d'une matrice de même rang.


Bref, il y'a beaucoup d'histoires à raconter et ne pas sécher...

La solution que je proposais n'est qu'un raffinement technique de ce qui précéde : on renonce à une majoration uniforme pour une majoration de la moyenne quadratique des modules des valeurs propres...



Edité 2 fois. La dernière correction date de il y a trois mois et a été effectuée par side.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Au coup d’œil, je dirais que $\textrm{rg} \, (A) \geqslant \frac{\| A \|_{\textrm{F}}^4}{\textrm{tr} \left( \left( A^\star A\right)^2 \right)}$ se déduit de la première inégalité de noix de totos grâce à la remarque que $A$ et $A^*A$ ont même rang.



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Re
@Noix de Totos

Il m'a semblé que les conditions sur $A, \:\: a_{ii} = 1, \:\:i\neq j \implies |a_{ij} |\leqslant \dfrac 1{\sqrt n}$ donnaient bien :
$$\mathrm {Tr}(A) = n,\:\: \:\:\|A\|_F^2= \displaystyle \sum_{0\leqslant i,j\leqslant n} a_{ij}^2 \leqslant n +\dfrac {n(n-1)}n =2n-1 ,\:\: \:\:\:\mathrm {rg(A)} \geqslant \dfrac {n^2}{2n-1}.$$



Edité 3 fois. La dernière correction date de il y a trois mois et a été effectuée par LOU16.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Je trouve moi aussi $n^2/(2n-1)$ ! En fait, l'inégalité de noix de totos donne exactement la même estimation que mon calcul, parce que la diagonale de la matrice $A$ est formée de $1$. Sa méthode est donc plus générale.

Dans le corrigé de la RMS, on parvient seulement à $n/4$ parce que l'on applique l'inégalité de NDT à $A+{}^t\!A$, ce qui explique qu'elle est deux fois moins bonne, mais cela suffisait pour répondre à la question posée.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Lou & John_John : OK.

Je ne sais pas ce que j'ai fait l'autre jour...

Side : c'est bon pour toi ?



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par noix de totos.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Bonsoir

J'ai suivi avec des moments de relâchement le fil. Fil dont je me félicite.

J'avais à un moment la même question que Guego, mais John a donné la réponse.

La question qui reste à poser : est-ce que JJ fait partie du jury de la rue d'Ulm ?

Un démenti peut paradoxalement indiquer qu'il en fait en effet partie, mais qu'il cherche à le cacher ! car après tout n'est-il pas curieux qu'il écrive un livre où il y a les exos de la rue d'Ulm ?

j'en suis un peu déboussolée.

Yvette
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Un démenti peut paradoxalement indiquer qu'il en fait en effet partie,

Eh bien, vois-tu, ces énoncés ne sont pas secrets ; ils sont même publiés par la rms, mais seulement depuis 1890. Tiens, justement, Piteux_gore (j'adore ce pseudo) s'est mis en devoir de faire ceux de 1912. En outre, puisqu'il est question de ces incunables, j'ai rédigé à la demande d'un collègue il y a un an un corrigé de l'épreuve de 6 heures d'Ulm 1891, dont l'énoncé fut publié à l'époque par la rms (un sujet sur les coniques, alors que l'épreuve de 4 heures traitait des coniques, mais en 4 heures seulement. Tant pis pour ceux qui avaient bossé trop longtemps les cubiques en spéciales).



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par john_john.
Re: Un exo d'Ulm un peu tordu
il y a trois mois
Je déterre ce fil, car il est intéressant et les intervenants furent de qualité.

Je souhaite évoquer un sujet proche, i.e. les estimations des valeurs singulières d'une telle matrice. Avec les outils dont je dispose, et John_john et Lou16 contrôleront et/ou amélioreront, je trouve
$$\forall k \in \left\{1, \dotsc, \left \lfloor \tfrac{n}{2} \right \rfloor \right\}, \quad \sigma_k < \sqrt{\frac{n-1}{k}} + 1,
$$ où, selon la convention usuelle, je note $\sigma_1 \geqslant \sigma_2 \geqslant \dotsb \geqslant \sigma_n$ les valeurs singulières de la matrice. Pour la plus petite valeur singulière, j'ai
$$\sigma_n \leqslant \sqrt{2-\frac{1}{n}}.$$



Edité 1 fois. La dernière correction date de il y a trois mois et a été effectuée par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 163, Messages: 1 505 829, Utilisateurs: 27 639.
Notre dernier utilisateur inscrit Bordée2.


Ce forum
Discussions: 19 567, Messages: 197 539.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page