Arbres et matrices symétriques
Si je prends une matrice definie positive $$\left[\begin{array}{ccc}3&2&2\\2&3&2\\2&2&3\end{array}\right]$$ remplacer un element par son oppose ainsi $$\left[\begin{array}{rrr}3&-2&2\\-2&3&2\\2&2&3\end{array}\right]$$ lui fait perdre en general son caractere defini positif. Cependant si $M=(m_{ij})$ est symetrique definie positive et si $$E_M=\{(ij);\ i<j,\ m_{ij}\neq 0\}$$ definit les aretes d'un graphe non dirige de sommets $\{1,\ldots,n\}$ qui soit sans cycle=un arbre, ou une foret, alors on peut changer tous les signes des elements non diagonaux de $M$ sans que cette nouvelle matrice cesse d'etre definie positive.
Cela vient facilement du fait que si $M$ est symetrique telle que son graphe associe soit un arbre alors $\det M$ est un polynome par rapport aux $m_{ij}^2$ avec $(ij)\in E_M.$ Comme je ne voudrais pas reinventer la roue, je pose la question d'une reference pour ce dernier resultat. Merci chers forumeurs.
Cela vient facilement du fait que si $M$ est symetrique telle que son graphe associe soit un arbre alors $\det M$ est un polynome par rapport aux $m_{ij}^2$ avec $(ij)\in E_M.$ Comme je ne voudrais pas reinventer la roue, je pose la question d'une reference pour ce dernier resultat. Merci chers forumeurs.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Un titre alléchant. Tu te doutes que ce genre de résultats est susceptible de m'intéresser. Question 1 : dans les deux dernières lignes, tu énonces un résultat, notons le (A), sur les matrices symétriques ...etc... Mais tu l'as bien vu quelque part ce résultat (A) ? Question 2 : tu dis ``cela vient facilement ...etc..'' en parlant du résultat PRECEDENT, disons (B). Mais je ne vois comment de (A), on peut déduire (B).
En un mot : si tu as le temps (et l'envie), peux tu m'en dire plus ?
PS : je suppose que tu as regardé dans le Bapat ?
$$
M = \pmatrix {a & b\cr b & d}, \qquad a,b,d \ne 0
$$
Quel est le graphe associé $E_M$ ? Que dit le résultat (A). Sorry, je dois louper quelque chose.
Envoi de l'article ? Pas en ce moment (trop occupé), peut-être plus tard.
Je n'en suis pas là. Je t'explique ce qui m'arrive. J'ai étudié à une époque donnée les matrices à coefficients $0,1$ dans certains contextes (pas nécessairement liées aux graphes) et j'ai accumulé quelques notes. Mais c'est dans un état brouillon. Pire : ce sont des torchons. Et j'ai eu beaucoup de mal à retrouver ce que je t'ai raconté dans mon dernier post. La preuve : je n'avais pas reconnu que ton problème initial était lié !! Bref, je dois faire du ménage pour m'y retrouver ; et sortir mes affaires d'un autre contexte (graphes bipartis) pour aller droit au but dans le contexte des arbres ou/forêts. Je ne sais pas si c'est bien clair, ce que je raconte.
D'ailleurs pour étudier les permutations zig zag, il a fallu que je m'écrive des outils pas trop inefficaces. Dans les premiers temps, je parcourais les $n!$ permutations de $S_n$ pour ne retenir que celles qui sont zig zag. Si, si. Pas question de dépasser $n = 8$. Et au fur et à mesure, j'ai amélioré la chose.
Si $\sigma(v_1) = v_1$, on considère la restriction de $\sigma$ à $V \setminus \{v_1\}$ et l'arbre induit sur ces sommets. Ici suppression d'un sommet pendant et récurrence.
Sinon, on a $\sigma(v_1) = v_2$ où $v_2$ est l'unique sommet de $V$ relié à $v_1$ (cf la pauvre figure). Mais il doit exister un $v$ tel que $\sigma(v) = v_1$ ; qui vérifie $\sigma(v) \sim_G v$ i.e. $v_1 \sim_G v$. Bilan : $v = v_2$ et $\sigma$ permute $v_1,v_2$. On termine par récurrence en supprimant l'arête pendante $v_1v_2$.
$$
\def\dp{\displaystyle}
\xymatrix {
&& \bullet \\
\bullet_{\dp{v_1}}\ar@{-}[r] &\bullet_{\dp{v_2}} \ar@{-}[ur] \ar@{-}[dr] \\
&&\bullet \\
}
$$
Je crois me souvenir que ces permutations engendrent le groupe des permutations de $V$ mais je n'arrive pas à retrouver mes billes.
Autre chose : dans l'avant dernier post, j'ai introduit la matrice $M = I_n + \text{Adj}(G)$ et annoncé que les permutations zig-zag de $M$ étaient des involutions. L'effet de $M$ est d'introduire des 1 sur la diagonale de la matrice d'adjacence du graphe $G$. Mais on peut mettre sur la diagonale un $0$ ou $1$ où l'on veut. Car toute matrice $N$ couverte par $M$ ($N \preceq M$ au sens des matrices $0,1$ i.e. composante à composante) a la même propriété que $M$ puisque toute permutation zig-zag de $N$ est une permutation zig-zag de $M$.
Je t'emprunte ton fil quelques instants. Je te le rendrai, promis, juré. C'est la semaine des arbres et des matrices symétriques, c'est toi qui l'as dit. Et celle ci va se terminer bientôt. Je considère comme arbre le ``line graph'' à $n$ sommets :
$$
\xymatrix {
\bullet \ar@{-}[r] & \bullet \ar@{-}[r] &\bullet \ar@{-}[r] &\qquad \cdots & \bullet \ar@{-}[r] &\bullet \\
}
$$
Et sa matrice d'adjacence. Par exemple pour $n=5$ : Je lui colle de la diagonale Et son déterminant, au signe près, ce signe étant $(-1)^{n(n+1)/2}$, ici $-1$ Et enfin, j'évalue ce déterminant signé en $x_i = 1$ pour tout $i$ : Je recommence avec $n = 6$ mais je ne montre pas tout. Quelle est la question ? Les questions ?
Il y a aussi la reciproque: Soit l'ensemble $E$ des matrices definies positives gouvernees par le graphe $G$ qui comprend au moins un cycle. Alors il existe $M$ dans $E$ et une arete $(ij)$ du cycle telle que $M'$ obtenue en changeant $m_{ij}$ en $-m_ij$ n'est plus dans $E.$ Cette reciproque est un peu le sujet du fil: le paresseux et le determinant.
1. Mon post http://www.les-mathematiques.net/phorum/read.php?3,1708680,1709782#msg-1709782 se termine par ``quelle est la question ..etc''. Mais ce n'était pas lié à ta question initiale. C'est juste que je ne pose jamais de colle dans mes posts et je me voyais mal terminer par ``Quel est ce déterminant ?...etc..''. Pour dire vrai, ce post a fait flop et n'a amusé personne (sauf moi, ce qui n'est déjà pas si mal). Bien sûr, au signe près, le déterminant en question est le polynôme continuant de $(x_1, \cdots, x_n)$ et son évaluation en $x_i := 1$ pour tout $i$ est le nombre de Fibonacci $F_{n+1}$. Bon, ok, on s'en fiche.
2. J'ai bien compris que tu cherchais une référence pour un certain résultat. Mais moi, ton résultat je le trouve trop faible, trop particularisé. Peut-être que je n'ai pas été assez clair. C'est d'abord une histoire de FORME au sens des matrices $0,1$. Je considère la forme $I_n + \Adj(G)$ où $G$ est un arbre à $n$ sommets. Quelles sont les permutations $\sigma$ de cette forme ? Réponse : celles vérifiant ou bien $\sigma(i) = i$ ou bien $\sigma(i) \sim_G i$. Or j'ai prouvé que ces permutations sont des involutions.
Bilan : lorsque l'on monte une matrice $A$ sur cette forme, alors $\det(A)$ est une somme de termes, $\det(A) = \sum\limits_{\sigma\ \rm zig-zag}\varepsilon(\sigma)\ a_{\sigma(1)) 1} \cdots a_{\sigma(n)n}$. Comme chaque $\sigma$ qui figure est une involution, s'il y a $a_{ij}$ dans le terme, alors il y a $a_{j,i}$ pour $i=j$, ce n'est pas un scoop. En particulier, si $A$ est symétrique, chaque terme zig-zag contient $a_{ij}^2$ pour $i < j$, a fortiori est invariant par $a_{ij} \mapsto -a_{i,j}$.
En résumé, pour trouver des références, peut-être faut-il ne pas se limiter à tes histoires de matrices symétriques définies positives ? Mais plutôt chercher dans la combinatoire des matrices $0,1$ ? Tu me diras, la combinatoire des matrices 0,1, c'est vaste. Pas faux. Au fait, pourquoi ne pas donner toi-même une preuve ? Ca te fait ch.er ?
Une dernière remarque : dans Bapat, dans lequel on trouve beaucoup de choses, je n'ai pas vu le résultat suivant : dans la forme $\Adj(G)$, $G$ arbre, il y a au plus UNE permutation zig-zag. Et il y en a une si et seulement l'abre admet un couplage parfait. Il se bat au niveau du déterminant tandis que moi, je me bats au niveau des termes. Ainsi, quand le déterminant est nul, c'est que chaque terme qui intervient dans le déterminant est nul (pas de compensation). Enfin, une matrice carrée $n \times n$ est sans zig-zag si et seulement si il existe $I, J \subset \{1..n\}$ vérifiant $\#I + \#J > n$ et $A_{I \times J} =0$ (sous-matrice nulle). Par exemple, une matrice avec une ligne nulle. C'est assez subtil. Dans le sens difficile, cela utilise la théorie du couplage dans les graphes bipartis, le théorème de König-Hall. Autrefois, cela figurait dans le ``vieux Berge'' (Théorie des graphes et ses applications, 1958, Th 9. p. 103). Pas vu dans ``Graphes et Hypergraphes''.
Tu n'as pas répondu à mon dernier post concernant un résultat trivial ...etc... Un résultat trivial énoncé par Berge ? Bizarre, non ? Surtout que l'on en déduit le théorème de Birkhoff & Von Neumann au dessus d'un sous-corps quelconque $K \subset \mathbb R$ : toute matrice bi-stochastique à coefficients dans $K$ est barycentre (à coefficients dans $K$) de matrices de permutations. Preuve algébrique et effective donc (confidence : j'aime bien $K = \Q$).
Mais c'est surtout pour revenir sur Bapat et m'excuser auprès de lui : il y a une analyse fine des permutations zig-zag de la matrice d'adjacence de n'importe quel graphe. C'est le théorème 3.8 page 28 ; il faut surtout regarder la preuve (un peu concentrée, j'ai du prendre un stylo mais il accompagne la chose d'un exemple). Peut-être que cela pourrait t'intéresser ? Et quitte à être lourd, je redonne un exemple dans le cas d'un arbre pour voir que symétrique n'est pas essentiel.
Je tire une forme d''abre au hasard sur le quel je monte une matrice $A$ au hasard : Et là, je vais faire les choses de la vie : pour $i < j$, je vais remplacer $a_{ij}$ et $a_{ji}$ par $sa_{ij}$ et $sa_{ji}$ où $s$ est un signe tiré au hasard, variable avec $(i,j)$ Enfin, je tire une matrice diagonale $D$ au hasard et je compare, non pas $\det(D + A)$ et $\det(D + $ comme on pourrait s'y attendre, mais les polynômes caractéristiques de $D + A$ et $D + B$. Qui sont égaux comme il se doit.
Rien à voir. Je suis content car j'ai enfin trouvé la matrice qui donne le polynôme continuant sans ces vilains signes alternés sur la diagonale et sans l'horrible correction finale $(-1)^{n(n+1)/2}$. Dans mes outils, je lui ai donné le joli nom de ContinuantMatrix Un inconvénient par rapport au fil : elle n'est PAS symétrique. Et je risque gros en faisant ainsi un hors-sujet dans ce fil (dont je n'ai pas oublié le nom)
Le polynôme continuant, c'est celui qui intervient au numérateur (ici pour $x_1, x_2, x_3, x_4$ seulement) de la fraction continue :
$$
x_1 + {1\over {x_2+\displaystyle {1\over {x_3 + \displaystyle {1 \over x_4}}}}}
$$
Retour à $n=5$ :
Birkhoff
Von Neuman
mais tes matrices sont unitairement équivalent. Il y a un résultat générale sur ce type de matrices : vous les appelez ' arbre ' moi non, ce n'est pas archivé comme P. pense.
Cordialement.
Ce n'est pas à toi que le post s'adressait mais à P. J'ai négligé ton premier post car je ne le trouvais pas clair. Et j'ai FAILLI négliger ton dernier post, celui qui vient juste avant. Mais j'ai réfléchi et je me suis dit que la seule façon raisonnable que deux matrices aient même polynôme caractéristique c'est qu'elle soient semblables. Et de manière ultra-simple, tant qu'à faire. Et c'est probablement ce que tu voulais signifier.
Eh bien, je dis BRAVO Je fais le même cinéma que dans mon dernier post. Mais cette fois ci, je cherche des matrices $P = \Diag(\pm 1, \cdots, \pm 1)$ voulant bien vérifier $P(D+A) = (D+B)P$. BINGO, j'en trouve deux ($P$ et $-P$).
Mais maintenant, si tu veux bien et si tu le sais, peux tu nous dire (me dire) où coller le signe $-$ sur la diagonale de $P$ en fonction de la structure de l'arbre $G$ ou de sa matrice d'adjacence, notée AG ci-dessus.
Où est ce que tu as appris cela si ce n'est pas indiscret ?
Encore CHAPEAU et merci.
On a posté en même temps. Je ne répondais pas à ton dernier POST http://www.les-mathematiques.net/phorum/read.php?3,1708680,1710622#msg-1710622 mais à ton AVANT dernier post http://www.les-mathematiques.net/phorum/read.php?3,1708680,1710588#msg-1710588
Où sont les $-1$ sur la diagonale de ma matrice $P$ (de ta matrice $U$) ? Merci. Récompense assurée (une tablette de chocolat ...etc....)
A plus tard, c'est quoi cette tablette!
Cordialement.
Dans ton dernier post première version (tu as modifié depuis), tu n'étais pas très causant. Mais comme j'ai fait un peu de théorie des graphes, j'ai compris assez vite que la donnée était un arbre dont les arêtes sont décorées par des signes (l'arête $(i,j)$ a le signe $s$ lorsque l'on change $a_{i,j}$ et $a_{j,i}$ en $sa_{i,j}$ et $sa_{j,i}$).
Eh bien, il suffit de choisir un sommet quelconque $v_1$, de lui coller le signe $+1$. Et pour tout sommet $v$, lui coller comme signe le produit des signes le long de l'unique chemin joignant $v_1$ à $v$ (ce qui donne $+1$ à $v_1$, de toutes manières).
Pas causant, causant, mais tu m'as vraiment aidé. J'ai donc décidé de nommer TonmDiagonalConjugation la fonction que j'ajoute en ce jour à ma boîte à outils. Quant à la récompense ``tablette de chocolat ..etc..'', je te propose autre chose. Est ce que tu connais la version discrète de Birkhoff & Von Neumann ? Je parle bien de la version discrète pour un sous-corps $K$ de $\R$. Je la fait même sur $\N$ de la manière suivante : étant donnée une matrice carrée $M$ à coefficients dans $\N$ telle que chaque ligne et chaque colonne ait la même somme, alors $M$ s'écrit (de manière effective) comme une combinaison de matrices de permutation, avec des coefficients entiers $\ge 0$.
Le magnifique cadeau que je te propose : je te dédie un post consacré à cela avec des exercices corrigés. Que je suis susceptible d'agrémenter de traces d'exécution sur le forum. Il faut juste être un peu à l'aise avec la théorie des graphes et le théorème de König-Hall sur les couplages dans les graphes bipartis. Je crois qu'il y a beaucoup de personnes qui pensent que Birkhoff & Von Neumann est un théorème d'Analyse Convexe. Je me demande d'ailleurs si on ne peut pas le monter sur un groupe commutatif ordonné réticulé.
Bien sûr, libre à toi de préférer la tablette de chocolat. Mais l'acheminement risque d'être compliqué : il fait chaud ...etc..
Encore merci à toi.
La version que j'ai: Soit $M=[x_{i,j}]$ une $n$ matrice carrée hermitienne complexe; si pour chaque ligne ou pour chaque colonne il existe au plus un seul coefficiant au-dessus de la diagonal qui est non nul alors la matrice hermitienne $M_1:=[y_{i,j}]=\{y_{i,j}=z_lx_{i,j}, i<j\}$ (avec $z_l$ complexe unitaire pour $l=1,\cdots, \frac{n(n-1)}{2}$) et ayant la même diagonale que $M$ est unitairement équivalente à $M$ par une matrice diagonale unitaire.
J'estime que nous avons répondu largement à ton post initial, et ce de manière totalement inattendue (enfin je parle pour moi), via la conjugaison diagonale de Tonm (alias --- mais je ne peux plus citer son nom réel vu qu'il l'a effacé, je ne comprends pas bien à quel jeu il joue).
Au cas où tu utiliserais des éléments de ce fil pour ton article, je pense que cela serait une bonne chose de citer Tonm alias anonyme car à la fin il y a contribué, certes de manière indirecte, mais tout de même essentielle (ce n'est pas contradictoire). Après tout, cela pourrait servir à son avenir (?), en tout cas, cela ne peut pas lui faire de mal. Je ne parle pas de mézigue, car ma carrière (sic), elle est dans mon dos, et ceci depuis belle lurette.
En tout cas, et c'est le principal pour moi, j'ai appris beaucoup de choses. Je pensais connaître 2 ou 3 bricoles sur la combinatoire des matrices 0,1 et les arbres. Mais force est de constater que je n'avais même pas lu de manière profonde des passages du Bapat dont je dispose pourtant depuis des années.
Voilà, voilà.
Bon courage.
Cette reciproque dit donc: soit $G$ un graphe connexe non dirige de sommets $1,\ldots,n$ et $E$ l'ensemble des matrices $M$ definies positives gouvernees par $G.$ Alors si $G$ n'est pas un arbre on peut trouver $M=(m_{ij})$ dans $E$ et une arete $e$ de $G$ telle que la matrice symetrique $M'=(m'_{ij})$ definie par $m'_{ij}=m_{ij}$ si $(ij)\neq e$ et $m'_{e}=-m_e$ ne soit plus definie positive.
Demonstration: je considere la matrice $ M_n(a)$ du fil 'le paresseux et le determinant' et je calcule
$$\det(2I_n+M_n(a))=n+1-(-1)^n2a-(n-1)a^2.$$ dont les racines sont $(-1)^n$ et $(-1)^{n+1}\frac{n+1}{n-1}$ Si $a$ est entre ces deux racines mais de module $ >1$ alors $2I_n+M_n(a)$ est definie positive mais $\det(2I_n+M_n(-a)$ ne l'est pas. A partir de cela il est facile de passer au cas general d'un graphe connexe avec cycle.
1. Evident mais il faut le dire. On a $P^2 = I_n$ et pour une matrice $A$ $n\times n$, en posant $B = PAP^{-1}$, on a $b_{ij} = \vep_i\vep_j a_{ij}$ ; en particulier $b_{ii} = a_{ii}$.
Morale en passant : diagonale pas touchée.
2. Dans l'autre sens, en quelque sorte. On se donne, d'une part une collection de signes $(s_{ij})_{1 \le i, j\le n}$ avec $s_{ii} = 1$ et $s_{ij} = s_{ij}$ et d'autre part une matrice $A$ $n \times n$. Et on définit $B$ par $b_{ij} = s_{ij} a_{ij}$. Encore une fois, on se fiche de la diagonale. On se pose la question de l'existence d'une matrice $P$, diagonale à coefficients diagonaux $\pm1$, vérifiant $B = PAP^{-1}$.
Réponse : on définit le graphe simple (sans boucle) non orienté de la manière suivante : pour $i \ne j$, on met une arête entre $i$ et $j$ si $a_{ij} \ne 0$ ou $a_{ji} \ne 0$. De sorte que si $ij$ n'est pas une arête ($i \ne j$), alors $a_{ij} = a_{ji} = 0$. Alors $P$ existe si et seulement si, pour tout cycle de $G$, le produit des signes $s_{ij}$ sur les arêtes est 1. Evidemment pour un arbre, il n'y a pas de cycle et la réponse est toujours positive.
$$
\vep_i \vep_j = s_{ij} \quad \hbox {pour toute arête $ij$} \qquad\qquad (\star)
$$
Je vais la construire sur chaque composante connexe. J'en prends une et je fixe $i_0$ dans cette composante connexe ; soit $i$ un autre sommet de cette composante connexe. Je considère un chemin allant de $i$ à $i_0$ et je pose $\vep_i$ le produit des $s_{k\ell}$ le long des arêtes de ce chemin. La valeur que j'obtiens est indépendante du chemin car le produit des signes des arêtes sur tout cycle vaut 1.
Et par construction, $\vep$ vérifie $(\star)$.
J'aime bien implémenter ce que je raconte. Mais en fait, je n'ai rien eu à faire car la fonction que j'ai donnée en http://www.les-mathematiques.net/phorum/read.php?3,1708680,1710670#msg-1710670 réalise le job. Sauf que je l'appliquais autrefois au contexte arbre. Et maintenant, je l'utilise dans le contexte du jour. C'est tout.
$$p_j=\frac{s_{e_2}s_{e_4}\ldots s_{e_{2p}}} {s_{e_1}s_{e_3}\ldots s_{e_{2p-1}}},\ \ p_j=\frac{s_{e_1}s_{e_3}\ldots s_{e_{2p+1}}}{s_{e_2}s_{e_4}\ldots s_{e_{2p}}}$$