Arbres et matrices symétriques

Bonjour P.
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 ?

En fait, je ne comprends pas du tout ton énoncé (A) les deux dernières lignes. Quelque chose doit m'échapper en ce qui concerne la diagonale. Faisons simple :
$$
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.

Inutile de formaliser plus. J'ai pigé ce que tu voulais dire. Je ne sais pas encore prouver la chose et je n'ai pas de référence. J'ai fait la petite expérience suivante vite fait. Je tire un arbre au hasard (j'aurais pu prendre une forêt) et je construis les matrices symétriques $M_1, M_2$ associées à cet arbre comme tu vois

[color=#000000]
> n := 6 ;
> G := RandomTree(n) ;
> M1, M2 := Matrices(G) ;
> M1 ;
[m11   0 m31   0   0   0]
[  0 m22 m32   0   0   0]
[m31 m32 m33   0 m53   0]
[  0   0   0 m44 m54   0]
[  0   0 m53 m54 m55 m65]
[  0   0   0   0 m65 m66]
> M2 ;
[ m11    0 -m31    0    0    0]
[   0  m22 -m32    0    0    0]
[-m31 -m32  m33    0 -m53    0]
[   0    0    0  m44 -m54    0]
[   0    0 -m53 -m54  m55 -m65]
[   0    0    0    0 -m65  m66]
[/color]

Sécurité de programmation oblige : je fais vérifier que le graphe des matrices est bien une forêt.

[color=#000000]
> Graphe(M1) ;    
Graph
Vertex  Neighbours

1       3 ;
2       3 ;
3       1 2 5 ;
4       5 ;
5       3 4 6 ;
6       5 ;

> IsForest(Graphe(M1)) ;
true
[/color]

Comparaison des déterminants et deux mineurs principaux pris au pif

[color=#000000]
> Det(M1) eq Det(M2) ;
true
> d := 4 ;
> I := SetToSequence(RandomSubset({1..n},d)) ;
> I ;
[ 1, 2, 4, 6 ]
> Minor(M1,I,I) eq Minor(M2,I,I) ;
true
[/color]

Mais en fait c'est plus rigide que cela : c'est ce que tu as dit i.e. les $m_{ij}$ avec $i\ne j$ qui interviennent dans les déterminants y figurent au carré.

Vu. Pour ma part, je préfère énoncer le résultat sous une forme plus combinatoire, indépendante des coefficients, des $m_{ij}^2$ ..etc.. Soit $G$ un arbre à $n$ sommets et $M = I_n + \text{Adj}(G)$ où $\text{Adj}(G)$ est la matrice d'adjacence de $G$. Alors les permutations zig-zag de $M$ sont des involutions. Note : une permutation $\sigma \in S_n$ est dite zig-zag d'une matrice $n\times n$ $M$ si le produit $a_{\sigma(1)1} a_{\sigma(2)2} \cdots a_{\sigma(n)n}$ est non nul (c'est un terme qui intervient au signe près dans le déterminant de $M$). C'est une terminologie de mézigue (j'ai rencontré cette notion plusieurs fois dans mes affaires).

[color=#000000]
> n := 6 ;
> G := RandomTree(n) ;
> G ;
Graph
Vertex  Neighbours

1       3 5 6 ;
2       4 5 ;
3       1 ;
4       2 ;
5       1 2 ;
6       1 ;

> M := 1 + AdjacencyMatrix(G) ; 
> M ;
[1 0 1 0 1 1]
[0 1 0 1 1 0]
[1 0 1 0 0 0]
[0 1 0 1 0 0]
[1 1 0 0 1 0]
[1 0 0 0 0 1]
> Tau := ZigZagPermutations(M) ;
> Tau ;
[
    Id($),
    (2, 4),
    (2, 5),
    (1, 3),
    (1, 3)(2, 4),
    (1, 3)(2, 5),
    (1, 5),
    (1, 5)(2, 4),
    (1, 6),
    (1, 6)(2, 4),
    (1, 6)(2, 5)
]
[/color]

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

[color=#000000]
> n := 15 ;                          
> G := RandomTree(n) ;
> M := 1 + AdjacencyMatrix(G) ;
> time Tau := ZigZagPermutations(M) ;
Time: 0.190
[/color]

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

[color=#000000]
> AG ;
[0 1 0 0 0]
[1 0 1 0 0]
[0 1 0 1 0]
[0 0 1 0 1]
[0 0 0 1 0]
[/color]

Je lui colle de la diagonale

[color=#000000]
> M ;
[-x1   1   0   0   0]
[  1  x2   1   0   0]
[  0   1 -x3   1   0]
[  0   0   1  x4   1]
[  0   0   0   1 -x5]
[/color]

Et son déterminant, au signe près, ce signe étant $(-1)^{n(n+1)/2}$, ici $-1$

[color=#000000]
> -Det(M) ;
x1*x2*x3*x4*x5 + x1*x2*x3 + x1*x2*x5 + x1*x4*x5 + x1 + x3*x4*x5 + x3 + x5
[/color]

Et enfin, j'évalue ce déterminant signé en $x_i = 1$ pour tout $i$ :

[color=#000000]
> DetM := Det(M) ;
> (-1)^ExactQuotient(n*(n+1),2) * Evaluate(DetM, [1^^n]) ;
8
[/color]

Je recommence avec $n = 6$ mais je ne montre pas tout.

[color=#000000]
> n ;
6
> DetM := Det(M) ;
> (-1)^ExactQuotient(n*(n+1),2) * DetM ;
x1*x2*x3*x4*x5*x6 + x1*x2*x3*x4 + x1*x2*x3*x6 + x1*x2*x5*x6 + x1*x2 + x1*x4*x5*x6 + x1*x4 + x1*x6 + x3*x4*x5*x6
    + x3*x4 + x3*x6 + x5*x6 + 1
> (-1)^ExactQuotient(n*(n+1),2) * Evaluate(DetM, [1^^n]) ;
13
[/color]

Quelle est la question ? Les questions ?

$\def\Adj{\text{Adj}}$ Quelques précisions

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

Dans ``ça parait trivial puisque le graphe n'est pas connexe'', de quel résultat parles tu ? D'une matrice $0,1$ sans permutation zig-zag ? Il n'est point question de graphe dans cet énoncé. Alors quel énoncé ?

P.
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 :

[color=#000000]
> n := Random(7,9) ;
> G := RandomTree(n) ;
> AG := AdjacencyMatrix(G) ;
> AG ;
[0 0 0 0 0 0 0 1]
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 1]
[0 1 0 0 0 1 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 1 0]
[0 0 0 0 0 1 0 1]
[1 0 1 0 0 0 1 0]
> A := Matrix(n,n, [Random(-9,9)*AG[i,j] : i,j in [1..n]]) ;
> A ;
[ 0  0  0  0  0  0  0 -9]
[ 0  0  0  9  0  0  0  0]
[ 0  0  0  0 -2  0  0  2]
[ 0 -6  0  0  0  0  0  0]
[ 0  0  9  0  0  0  0  0]
[ 0  0  0 -4  0  0 -7  0]
[ 0  0  0  0  0 -2  0 -1]
[ 4  0 -3  0  0  0 -6  0]
[/color]

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

[color=#000000]
> B := A ; 
> for i := 1 to n do for j := 1 to i-1 do 
for|for>   s := Random({-1,+1}) ;
for|for>   B[i,j] := s*B[i,j] ;  B[j,i] := s*B[j,i] ;
for|for> end for ; end for ;
> B ;
[ 0  0  0  0  0  0  0  9]
[ 0  0  0 -9  0  0  0  0]
[ 0  0  0  0 -2  0  0 -2]
[ 0  6  0  0  0  0  0  0]
[ 0  0  9  0  0  0  0  0]
[ 0  0  0 -4  0  0 -7  0]
[ 0  0  0  0  0 -2  0 -1]
[-4  0  3  0  0  0 -6  0]
[/color]

Enfin, je tire une matrice diagonale $D$ au hasard

[color=#000000]
> D := DiagonalMatrix([Random(-20,20) : i in [1..n]]) ;
> D ;
[-14   0   0   0   0   0   0   0]
[  0  -6   0   0   0   0   0   0]
[  0   0 -17   0   0   0   0   0]
[  0   0   0 -19   0   0   0   0]
[  0   0   0   0  15   0   0   0]
[  0   0   0   0   0  17   0   0]
[  0   0   0   0   0   0  -2   0]
[  0   0   0   0   0   0   0  16]
[/color]

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

[color=#000000]
> ChiA<X> := CharacteristicPolynomial(D + A) ;
> ChiA ;
X^8 + 10*X^7 - 684*X^6 - 8002*X^5 + 146045*X^4 + 2054808*X^3 - 7860486*X^2 - 170500788*X - 405996192
> ChiB<X> := CharacteristicPolynomial(D + B) ;
> ChiB ;
X^8 + 10*X^7 - 684*X^6 - 8002*X^5 + 146045*X^4 + 2054808*X^3 - 7860486*X^2 - 170500788*X - 405996192
> assert ChiB eq ChiA ;
[/color]

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

[color=#000000]
> n := 5 ;
> C  := ContinuantMatrix(n) ;
> C ;
[x1 -1  0  0  0]
[ 1 x2 -1  0  0]
[ 0  1 x3 -1  0]
[ 0  0  1 x4 -1]
[ 0  0  0  1 x5]
> DetC<x1,x2,x3,x4,x5> := Det(C) ;
> DetC ;
x1*x2*x3*x4*x5 + x1*x2*x3 + x1*x2*x5 + x1*x4*x5 + x1 + x3*x4*x5 + x3 + x5
[/color]

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

[color=#000000]
> fraction := x1 + 1 / (x2 + 1 / (x3 + 1 / (x4 + 1/x5))) ;  
> Numerator(fraction) ;
x1*x2*x3*x4*x5 + x1*x2*x3 + x1*x2*x5 + x1*x4*x5 + x1 + x3*x4*x5 + x3 + x5
> Numerator(fraction) eq DetC ;
true
> Denominator(fraction) ; 
x2*x3*x4*x5 + x2*x3 + x2*x5 + x4*x5 + 1
> Evaluate(DetC, [1^^n]) = Fibonacci(n+1) ;
8 = 8
[/color]

C'est assez simple si vous prenez $U=\text{diag}(z_1,\cdots,z_n)$ unitaire et la matrice $U^*AU$ vous voyez l'analogie. $A$ matrice que vous appelez sans cycle (c'est des conditions sur les entrées nul ou pas)

Cordialement.

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

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

[color=#000000]
TonmDiagonalConjugation := function(G, S)
  // G est un arbre et S une {-1,0,1}-matrice symétrique de même forme que Adj(G)
  VG := Vertices(G) ;
  n := #VG ;
  assert NumberOfRows(S) eq n  and  IsSymmetric(S) ;
  AdjG := AdjacencyMatrix(G) ;
  assert &and [Abs(S[i,j]) eq AdjG[i,j] : i,j in [1..n]] ;
  v1 := VG[1] ;
  Diagonale := [] ;
  for v in VG do
    // p = chemin de v1 à v sous forme d'une séquence de sommets reliant v1 à v
    p := Geodesic(v1, v) ;
    // Signe(v) =  produit des	signes le long du chemin de v1 à v
    vSign := &*[Z| S[Index(p[k]),Index(p[k+1])] : k in [1..#p-1]] ;
    Append(~Diagonale,vSign) ;
  end for ;
  return DiagonalMatrix(Diagonale) ;
end function ;

.....
.....
Dans le contexte évoqué dans mes posts précédents

P := TonmDiagonalConjugation(G, Signes) ;
assert P*(D+A) eq (D+B)*P ;
[/color]

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.

Merci pour le merci.

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.