"Il est facile de 2"

@CPL : Je n'ai pas bien compris en quoi 958 [je n'avais pas encore vu ta démo^^, le temps d'écrire ce long post] se ramène à ce que tu dis, mais je n'ai pas poussé l'examen, puisque tu as dit que tu allais détailler :-p, en tous cas le truc sur la matrice inverse et la diagonale à l'air vraiment très joli!

___________________________________________________________________________________________________________

Merci de t’intéresser à la question lexico!! je vais donner des détails mélant l'historique de mes motivations et des généralisation successives.
Au départ le problème n'est pas vraiment un problème d'algèbre linéaire, il s'agit de classer les lignes d'une matrice à coefficient dans un ensemble totalement ordonné (pas un anneau)

On a donc notre "matrice" $M$ mais qui est plus un tableau qu'une matrice et on classe les lignes dans l'ordre lexico puis les colonnes dans l'odre lexico : ça donne $L(M)$. (ça deviendra $L_{Id}(M)$ plus tard) . ça n'est pas très difficile de trouver un cas où $L^2(M):=L(L(M))\ne L(M)$, ou même $L^2(M)\ne L^3(M)$ etc... ce qui répond à la question :

Peux-tu donner un exemple [...] où la périodicité ne se fait qu'à partir d'un certain rang ?

On peut montrer que la période est bien $1$ à partir d'un certain rang, c'est à dire que la suite $(L^k(M))_k$ est stationnaire.

Déjà une motiavtion peut-être le rapport que ça a avec "graphe isomorphisme" qui est un problème ouvert et qui est moins fort (en fait équivalent) que

"peut-on dire en temps polynomial si $M$ et $N$ matrices carrées sont telle qu'il existe $P$ et $Q$ matrices de permutation telle que $PMQ=N$"

On se dit que peut-être ça donne une direction, eh bien poussons là un peu....avec $L_Q$ où $Q$ est une matrice de permutation. Mais avant ça, je vais parler d'un cas particulier : celui où $Q=J:=\begin{pmatrix} 0 & 0 & ... & 0 & 1\\ 0 & 0 &... & 1 & 0\\ ... & ...& ...1^{.\, .\,.\,.} & ...& ... \\ 0 & 1 & ... & 0 & 0 \\ 1 & 0 & ... & 0 & 0\end{pmatrix}$ "l'autre diagonale". $L_J(M)$ correspond à classer dans l'ordre lexico croissant les lignes de $M$ puis les colonnes de la matrice obtenue dans l'ordre lexico décroissant.

Là on remarque une chose intéressante c'est que si $M$ est une matrice de relation d'ordre partiel $\leq_M$ sur $[1,n]\cap \mathbb N$ donné par $M_{ij}=1$ si $i\leq_M j$ et $0$ sinon, alors $L_J(M)$ est trigonale. Une matrice de relation d'ordre n'étant pas forcement trigonale (multiplier à droite la matrice trigonale supérieure avec que des $1$ en haut par une permutation $P$ non triviale et à gauche par $P^t$ on obtiendra toujours une matrice d'ordre (ici total) mais qui ne sera plus trigonale supérieure, et en général pas trigonale du tout)

Mais il y a mieux que $L_J(M)$ est trigonale pour tout $M$ matrice d'ordre : on a aussi $L_J(PMR)$ trigonale pour toute matrice d'ordre et toutes matrices de permutations $P$ et $R$(!!!!!)

On démontre dans la foulée que les itérations successives se stabilise et qu'on a une période 1 ou 2 : c'est à dire qu'il existe $k$ tel que $L^k_J(M)=L_J^{k+2i}(M)$ pour tout $i\in \mathbb N$. Et j'appelle alors ordre cycliquement indéxé associé à $M$ la matrice $M_0:=L_J^k(M)$,
on a alors $L_J(M_0)=:M_1$ puis $L_J(M_1)=M_0$ etc.
Ces matrices qui sont des matrices d'ordre cycliquement indexées ont un aspect très stable dans lesquelles ont voit apparaître des sortes de progression arithmétiques mais passons là dessus, on démontre que lorsqu'on enlève la dernière ligne et la dernière colonne d'une matrice d'ordre cycliquement indexée , on a encore une matrice d'ordre cycliquement indexée. ça permet d'étudier les ordres d'une façon sans doute intéressante, mais je n'ai pas poussé l'investigation plus loin : on pourrait aussi s’intéresser à (aux) matrice(s) de permutations qui fait passer de $M_0$ à $M_1$ mais je ne m'étends pas là dessus, mais qui sait, ça pourrait peut-être donner des infos cruciales pour "graph iso". En tous cas on ne peut DEJA pas dire que ça n'est pas une question motivée ou qui n'ouvre sur rien de spécialement intéressant.

J'arrive à montrer la périodicité à partir d'un certain rang de $L_J$ pour les matrices d'ordre mais pas dans le cas général, mais j'ai fait de nombreux tests tous concluants. Au départ je n'avais pas pensé à écrire $L_J$ je classais juste dans l'ordre lexico croissant les lignes et lexico décroissant les colonnes, mais je me suis dit que si j'obtenais une période de $2$ c'est peut être justement parce que ça revenait à faire "lexico croissant des ligne puis lexico croissant des colonnes ... puis multiplication à droite par $J$ qui est d'ordre $2$... donc j'ai défini $L_Q$ pour toute permutation et j'ai laissé le problème pour passer à autre chose, mais à un moment je me suis quand même demander ce qui se passerait avec des matrices dans $F_2$ si je multipliais à droite après avoir appliqué $L_{Id}$ ...par $Q$ avec $Q^q=Id$, mais pas forcément une matrice de permutation! je me suis dit : "on va quand même pas avoir $q$-périodicité à partir d'un certain rang???!!! Notons que par finitude, on a forcément une période à partir d'un certain rang, mais aucune raison qu'elle soit d'ordre $q$, eh bien il se trouve que toutes les expérimentations python on confirmé cette étrange conjecture...
J'ai alors essayé avec non pas $F_2$ mais $\mathbb Z$ avec l'ordre usuel, avec des $Q$ tel que $Q^2=Id$ et j'ai constaté que pour certains $Q$ ça marchait pour tout $M$, et que pour une autre ça marchait seulement des fois : les fois où on avait une période, elle était de $2$ et les fois où ça ne marchait pas c'est parce qu'on avait pas de période...
Les itérationde $L_Q^k(M)$ dans ce cas semblaient tendre en norme vers l'infini... (en fait peut-être qu'à un moment ça devient périodique mais ça n'est pas ce qui semblait se passer, je n'ai pas poussé plus loin)

Une généralisation possible (et peut-être vraie) est alors : quand $(L^k_Q(M))_k$ est périodique (à partir d'un certain rang) avec $Q^q=1$, alors cette période divise $q$.

Mais j'en ai trouvé une plus intrigante : j'examinais le cas où ça diverge et je me disais que "c'était à cause des entiers négatifs" ...

Parallèlement je pensais non pas forcement à $\mathbb Z$ ou $\mathbb R$ mais à des anneaux de polynômes (même sur un anneau fini) en considérant la matrice génériques .. que se passerait-il dans ce cas ? J'ai pensé à la matrice générique pour essayer de démontrer le résultat dans le cas d'un anneau fini, mais je me suis rendu compte que je pouvais choisir un ordre arbitraire "en live" sur les coefficients apparaissant dans les itérations successive (coefficients qui sont des polynômes dont les indéterminées sont les coef de la matrice générique) et l'idée d'un "bon ordre" m'est venue : j'ai alors repris les cas de $\mathbb Z$ qui n'étaient pas périodique et j'ai mis le bon ordre suivant (où $0$ est minimum ) $a<b$ si $|a|<|b|$ et $-|a|<|a|$ ($a\ne 0$)... et là : tout marchait!

Alors je n'ai peut-être pas fait assez d'essais, mais il faut dire qu'on peut raisonnablement conjecturer qu'il se passe des trucs chouettes, et peut-être le résultat assez stupéfiant lui-même . Peut-être qu'il est en fait trivial sans que je ne m'en rende compte, ou pas si stupéfiant, mais comme ça à première vue, ça à l'air assez bleuffant, si c'est vrai. Et même si ce n'est pas vrai vrai vrai, il ne doit pas y avoir bcp à changer pour que ça le soit...

Les résultats les plus utiles me semblent être ceux qui concernent le cas où $Q$ est une permutation, MAIS le cas général est troublant et il montre, même dans ses formes plus faibles (finitude des anneaux, cas où Q est une permutation, ne regarder que les cas périodique quand l'anneau est infini,etc.) l'extra ordinaire stabilité de l'opération $L$.

D'autre part, si c'est vrai, ce n'est pas des résultats "utiles" qui vont se profiler mais des résultats très profonds à mon avis, mêlant structurellement la théorie de l'ordre et l'algèbre commutative d'une façon sans doute inédite. je ne pense pas faire preuve d'un enthousiasme inapproprié en disant ça... je ne sais pas ce que tu en penses, ou ce qu'en pensent les lecteurs patients, ni même si je t'ai un peu convaincu...^^

CPL a écrit:

Peux-tu donner un exemple où l'ordre classique sur Z ne fonctionne pas

Je vais te trouver ça tout à l'heure.

PS
Je n'ai pas trop compris l'histoire de presque périodique avec $R$ ^^


P;P;S
Je me rends compte qu'emporté par la concentration, j'ai pris bcp de place dans ce fil général, pour un problème un peu particulier et j’espère que cc ou quelqu'un d'autre ne trouvera pas ça inconvenant

Merci lesmathspointclaires, je vais voir si ça me parle.

EDIT : Pour la presque-périodicité avec $\R$, on dit qu'une suite est "$n$-presque-périodique" si les sous-suites de progression arithmétique $n$ convergent vers des constantes. Autrement dit, en pratique, ça va être périodique au bout d'un moment à cause de l'imprécision des ordinateurs.

Je signale que je me suis complètement trompé quand j'ai dit que ça fonctionne pour n'importe quel corps de caractéristique $2$. (Le passage que j'ai loupé à la généralisation est que l'on n'a pas $\langle y, M(y) \rangle = \langle y, d(M) \rangle$ mais $\langle y, M(y) \rangle = \langle F(y), d(M) \rangle$ en général, où $F$ est l'endomorphisme de Frobenius -- inversible lorsque l'ordre est fini --, qui n'est égal à l'identité que si le corps est $\mathbb{F}_2$.)

Un contre-exemple dans $\mathbb{F}_4 = \{0,1,x,y\}$ est la matrice
$$\begin{pmatrix}
x & y\\
y & 1
\end{pmatrix}\text{.}$$

Champ-Pot-Lion a écrit:

Pour la presque-périodicité avec R, on dit qu'une suite est "n-presque-périodique" si les sous-suites de progression arithmétique n convergent vers des constantes. Autrement dit, en pratique, ça va être périodique au bout d'un moment à cause de l'imprécision des ordinateurs.

Et tu as remarqué que ça se produisait [parfois] avec l'ordre usuel de $R$, c'est très intéressant...

$$\newcommand{\inp}[2]{\langle #1 , #2 \rangle}\begin{align*}\inp{y}{M(y)} &= \sum_{1 \leq i,j \leq n} y_i M_{i,j} y_j\\
&= \sum_{i=1}^n {y_i}^2 M_{i,i} + 2 \sum_{1 \leq i < j \leq n} y_i M_{i,j} y_j ~~\text{ (car $M_{i,j} = M_{j,i}$)}\\
&= \sum_{i=1}^n y_i M_{i,j}\\
&= \inp{y}{d(M)}\end{align*}$$

lesmathspointclaires, je dois avoir mal compris. Je fais le calcul pour ton premier exemple, il faut que tu me corriges.

1) On a $L(M) = M$.
2) Ensuite, $M \times Q = \begin{pmatrix}-4&-7\\-9&-16\end{pmatrix}$.
3) Puis $L(M \times Q) = M \times Q$ puisque $(-4,-7) > (-9,-16)$ dans l'ordre lexicographique normal, et $(-4,-9) > (-7,-16)$.
4) Puis $M \times Q \times Q = M$, on a bouclé la boucle.

Non ? J'ai aussi testé pour $Q \times M$ au lieu de $M \times Q$, ça fonctionne aussi.

@CPL : en fait certains exemples ne marchent plus dans le cas de $\mathbb Z$, avec ou sans bon ordre, par contre ça semble marcher asymptotiquement et à une multiplication par un scalaire près ("projectivement" dirons nous) (c'est à dire qu'après normalisation du prier coef = 1, on a ce que tu appelais une presque-période, dans les contrexemples.je vais fouiller un peu plus, pour voir si on peut pas dénicher une période assymptique qui ne divise pas $q$) En tous cas lee pb reste ouvert pour les anneaux finis ou la période existe forcément

Ta propriété avec le tri de "matrices d'ordres" est marrante. En fait on commence par trier les éléments linéairement, avec un tri topologique. Puis le deuxième tri a pour effet de trier dans le même ordre que le premier.

@cc Est-ce que tu comptes détailler comment tu es parvenu à ton énoncé sur les matrices symétriques sur $\mathbb{F}_2$ qui ont leur diagonale dans leurs images (question 958(bis)) ? En particulier, c'est quoi cette histoire de logique dans laquelle on prouve qu'un nombre est impair pour prouver qu'il est non nul ?

Pour ta question 1001, il y a le contre-exemple suivant dans $\mathbb{F}_3$ :
$$\begin{pmatrix}1&0&0&1\\0&0&1&1\\0&1&0&1\\1&1&1&0\end{pmatrix}\text{.}$$
Mais c'est peut-être vrai sur $\mathbb{R}$ pour les matrices dont la signature ne contient que des termes du même signe.

Oui, j'avais des raisons de le penser car en reprenant la preuve que j'avais faite pour $\mathbb{F}_2$ il y a un truc qui bloque. C'est en me basant sur ça que j'ai trouvé le contre-exemple ci-dessus, et la même chose peut bloquer sur $\mathbb{R}$. Voici une matrice qui donne un contre-exemple sur $\mathbb{R}$ :

$$\begin{pmatrix}1&0&0&1\\0&0&1&-1\\0&1&0&1/2\\1&-1&1/2&0\end{pmatrix}\text{.}$$

Le truc qui bloque est que lorsqu'on fait la récurrence, on a besoin que si $y$ n'est pas dans le noyau de $M$, alors $\langle M(y), y \rangle$ n'est pas nul.

Bonsoir,

dans la même veine, je suppose que la question 915+4 n'est pas la question 919.

@CC : Je vais quand même écrire la démo :

Il s'agit de montrer que si il existe $f=(f_1,f_2...,f_n)$ matrice ligne à coef dans $K$ et $(u_1,....,u_n)$ matrice colonne telle que pour toute permutation $P$ on a $fPu=0$ alors $f$ ou* $g$ a des coefficients tous identiques (ce qui force $g$ ou* $f$ a avoir des coef de somme nulle )(je viens d'inventer ou* := la disjonction non commutative (:D )

Pour faciliter la "récurrence facile" dont je parlais dans le post du dessus, on va montrer un poil plus fort qu'on appellera $Hyp(n)$, la même chose sauf qu'on ne demande pas spécialement $fPu=0$ mais $fPu=fQu$ pour tout couple $(P,Q)$ de permutations. On remarque qu'on peut aussi remplacer $K$ corps par $A$ anneau intègre. Ca donne donc

Soit $A$ intègre et $n$ un entier, s'il existe $f=(f_1,f_2...,f_n)$ matrice ligne à coef dans $A$ et $(u_1,....,u_n)$ matrice colonne à coef dans $A$, tel que pour tous $P$ et $Q$ matrices de permutation, on a $fPu=fQu$, alors $(\forall i\in [1,n] \,f_i=f_j$ ou $\forall i\in [1,n] \,u_i=u_j)$


Si $n=1$ c'est clair.
Si $n=2$ , que la matrice de $f=(f_1,f_2)$ et celle de $u=(u_1,u_2)$ on a $f_1u_1+f_2u_2=f_1u_2+f_2u_1$ ce qui équivaut à $f_1(u_1-u_2)=f_2(u_1-u_2)$, qui équivaut encore à $(f_1-f_2)(u_1-u_2)=0$, comme $A$ est intègre, on en déduit $Hyp(2)$


Soit $n\geq 3$ entier. Supposons : $f_i\ne f_j$ pour au moins un couple d'entiers $(i,j)\in [1,n]$, disons, sans perte de généralité, $f_1\ne f_2$.

Soit $\sigma(k)$ l'ensemble des permutations qui envoient $n\geq 3$ sur l'entier $k\in \left\{n-1,n\right\}$. Il est clair, par $Hyp(n-1)$, et puisque $f_1\ne f_2$ et que $n\geq 3$, qu'on a $u_i=u_j$ pour tout $i,j\in [1,n]-\left\{k\right\}$, mais comme c'est vrai pour tout entier $k\in \left\{n-1,n\right\}$, on a bien $u_{n-1}=u_1=u_2...=u_{n}$ pour tout $i,j\leq n$. cqfd

Pour t'éviter de lire bcp de symboles pour pas grand chose, je vais résumer : il y a des solutions triviales quand $f$ est multiple de $(1,1,1,1...,1)^*$ ou $u$ multiple de $(1,1,1,1,1...1)$, et on montre qu'il n'y a qu'elles, par récurrence.

Comme souvent on doit renforcer les hypothèses pour que la récurrence fonctionne et on montre qu'on a le même résultat en remplaçant $f(p(u))=0$ par $ f(p(u))=cste$

Là c'est immédiat il suffit de considérer toutes les permutations qui fixent un $i$ donné sur un $j$ donné, et d'appliquer la récurrence (et de vérifier que ça s'initialise bien pour n=1 et 2)

On suppose que $P$ est croissant et qu'on a une valeur de départ assez grande (sinon la suite peut stagner). Lorsque la valeur courante est entre $P(n-1)$ et $P(n)$, on n'est intéressé que par sa valeur modulo $n-1$. Imaginons qu'on ait la valeur $P(n)-\alpha$ avec $\alpha$ compris entre $0$ et $n$ strictement. Alors la valeur qui va être atteinte juste en dessous de $P(n+1)$ est à une distance de $P(n+1)$ congrue à $P(1)-P(0)+1+\alpha$ modulo $n$. En posant $k := P(1)-P(0)+1$, il faut donc étudier la suite $u_{n+1} = (u_n + k) \% n$ (avec $a\% b$ dénotant le reste de la division euclidienne de $a$ par $b$).

Lorsque $P(1)-P(0) = 1$ (par exemple $P(x) = x^m$), on est dans un cas particulier qui facilite les choses.