semi-définie positive, termes rectangles <0
Soit $A=(a_{ij})_{1\leq i,j\leq n}$ une matrice semi-définie positive de déterminant nul telle que
1) $a_{ij}\leq 0$ si $i\neq j ;$
2) si $E=\{\{i,j\}\mid a_{ij}<0\}$ alors le graphe non orienté d'ensemble de sommets $\{1,\ldots,n\}$ et d'ensemble d’arêtes $E$ est connexe.
Voilà plusieurs jours que je cherche à montrer qu'alors $A$ est de rang $n-1,$ comme le montrent les nombreux exemples. Quelqu'un connaît il la littérature, ou a-t-il une preuve ?
1) $a_{ij}\leq 0$ si $i\neq j ;$
2) si $E=\{\{i,j\}\mid a_{ij}<0\}$ alors le graphe non orienté d'ensemble de sommets $\{1,\ldots,n\}$ et d'ensemble d’arêtes $E$ est connexe.
Voilà plusieurs jours que je cherche à montrer qu'alors $A$ est de rang $n-1,$ comme le montrent les nombreux exemples. Quelqu'un connaît il la littérature, ou a-t-il une preuve ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Peut être on rédige après. c'est assez compliqué.
Edit
Ton histoire me fait penser à la matrice Laplacienne d'un graphe. Il y a un lien ? Ou encore est ce que ta matrice provient de la théorie des graphes ? Mais peut-être est ce une question indiscrète.
$A1=0$ et sauf erreur tous les cofacteurs sont egaux (mais pourquoi non nuls?) Dans mon cas plus general on pourrait remplacer le vecteur 1 par in vecteur $w$ tel que $Aw=0$ mais il me semble qu'il faudrait montrer que $w$ est a coefficients positifs pour tenter une generalisation du Laplacien de graphe.
Je vais probablement enfoncer des portes ouvertes mais comme tu utilises ``sauf erreur'' ..etc.. Oui, les cofacteurs sont vraiment égaux, lorsque l'on tient compte du signe $(-1)^{i+j}$. Et c'est dû à un lemme d'une simplicité désarmante (Bapat, Lemma 4.2, p. 46).
Soit de manière générale une matrice $n \times n$ telle que la somme des lignes est nulle ET la somme des colonnes est nulle. Alors tous les cofacteurs sont égaux.
Note : comme j'aime pas les signes, au lieu de supprimer la ligne $i$ et la colonne $j$, je les mets à $0$ et colle un $1$ en position $(i,j)$. C'est cela le cofacteur d'indice $(i,j)$ dans ma tête.
Et dans le cas des graphes, si $\varphi$ est une fonction sur les sommets d'un graphe $G$ d'ordre $n$, et $Q$ la matrice Laplacienne, on a l'expression suivante :
$$
^t{} \varphi \cdot Q \cdot \varphi = \sum_{(x,y) \in G} \big(\varphi(x) - \varphi(y)\big)^2
$$
Cette expression prouve la semi-positivité d'une part et d'autre part que le noyau du Laplacien de $G$, supposé CONNEXE, sont les fonctions constantes. D'où le rang $n-1$ pour la matrice Laplacienne. Bilan : tous les cofacteurs sont égaux, non nuls, et même (strictement) positifs. Et de plus, on a le matrix tree theorem : la valeur commune des cofacteurs est le nombre d'arbres recouvrants.
Mais je suppose que tu connais tout cela. Et au fait, es tu sûr de ta généralisation ? As tu fait suffisamment de tests ? Tu l'as vu écrit quelque part ?
Cordialement.
1) Non, mais ca m'arrangerait
2) Non surement, mais que signifie" suffisamment"?
3) Non (voir 1)
Cher Claude, je connais mon Bapat grace a toi. Mais pour passer du Laplacien pondere $\sum_{ij}w_{ij}(x_i-x_j)^2$ a mon cas je n'arrive pas a franchir le pas.
Je suppose $\sum_{i,j} w_{i,j} (x_i - x_j)^2 =0$ et je vais montrer, sous l'hypothèse de connexité du post 1, que :
$$
x_1 = x_2 = \cdots = x_n
$$
Cela fera un noyau de dimension 1 donc une matrice de rang $n-1$. Je peux évidemment limiter la somme à $i \ne j$. Et comme $w_{i,j} \le 0$ pour $i \ne j$, on obtient
$$
w_{i,j} (x_i-x_j)^2 = 0 \qquad \forall i \ne j
$$
Je note comme toi $E$ l'ensemble des $(i,j)$ tels que $w_{i,j} < 0$. Donc :
$$
x_i-x_j = 0 \qquad \forall (i,j) \in E
$$
Mais une telle fonction $i \mapsto x_i$ sur un graphe connexe est constante.
Je suis à côté de mes pompes ? Ou bien fatigué ? Ou les deux ?
Donc vous trouvez quoi le vecteur associé à $0$ c'est pas le vecteur ( $1$ ). (analogue à la Laplacienne)?
Et bien oui, ce qui m'étonne un peu. Ceci veut dire que soit il y a une erreur dans mes affaires, soit les hypothèses de P. font que $\bf 1$ est dans le noyau (noyau qui n'est pas réduit à $0$, vu que le déterminant est nul). Je m'interroge.
Edit.
(Vous plaisantez?)
Je soupconne meme que tous les mineurs principaux d'ordre $n-1$ sont non nuls....
Edit.
J'ai vu que vous mettiez exposant $-m$ en fait, $m$ peut être pris $m=1$ résultat sur $M-matrices$...
A part ça jolie manipulation.
saut erreur de ma part, la preuve qui suit est élémentaire, en ceci qu'elle laisse tranquilles MM. Perron et Frobenius, quoiqu'elle repose tout de même un peu sur les mêmes principes.
Puisque $A$ est symétrique positive, il existe des colonnes $X_1,...,X_n$ telles que $a_{i,\,j}=X_i.X_j$ (produit scalaire canonique) pour $i\neq j$ ; dans les conditions de l'exercice, il suffit de montrer que le rang de cette famille est $\geqslant n-1$. Or, supposons une relation linéaire non triviale $\sum t_iX_i=0$ ; spdg (sans perte de généralité) on peut supposer que l'un des $t_i$ est $>0$ : nous écrivons alors cela sous la forme $S=-T$, où $S$ et $T$ sont les sommes des $t_iX_i$ étendues aux $t_i$ strictement positifs, resp. $\leqslant0$.
En écrivant $S.S=-S.T$, ces deux membres étant resp. $\geqslant0$ et $\leqslant0$, on en déduit que $S=0$. Si nous appelons $I$, resp. $J$, l'ensemble des indices $i$ de la première, resp. de la seconde somme, nous voyons que $X_i.X_j=0$ si $i\in I$, $j\in J$ ; en effet, avec ces notations, on a $0\geqslant t_i X_i.X_j\geqslant S.X_j=0.$
Or, l'hypothèse $G$ connexe, sachant que $I\neq\emptyset$, entraîne que $J=\emptyset$ ; toute relation linéaire non triviale $\sum t_\ell X_\ell=0$ est donc à coefficients tous de même signe strict. De cela s'ensuivent deux choses :
- Le rang de toute sous-famille à $n-1$ éléments extraite des $X_i$ est libre : sinon, on aurait une relation linéaire non triviale $\sum t_iX_i=0$, avec spdg $t_n=0$, et cela contredirait ce qui précède. En particulier, les déterminants mineurs principaux de $A$ sont $>0$.
- Le rang de $A$ est effectivement $\geqslant n-1$.
Cordialement j__j
Cordialement, j__j
post scriptum : effectivement comme tu le pressentais, les mineurs principaux sont $>0$ (et les matrices mineures principales sont définies positives,
On continue alors le raisonnement mutatis mutandis...
Cordialement, j__j, qui vient à résipiscence