Forum de mathématiques - Bibm@th.net

kaien

Membre

Inscription : 17-07-2020

Messages : 6

Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour,

Voici une question sur l’inversibilité d'une matrice:

Soit $ n \in \mathbb{N}^*$ bins et $ d\in\mathbb{N}^*$ balles. Notons l'ensemble $ B = \{\alpha^1, \ldots, \alpha^m\}$ tous les choix possibles pour mettre $ d $ balles dans $ n $ bins, tel que

$$\alpha^1 = (d,0,\ldots, 0), ~ \alpha^2 = (0,d,\ldots, 0), \ldots$$

Définissons la matrice $ V $:
$$V = \begin{bmatrix}
(\alpha^1)^{\alpha^1} & \cdots & (\alpha^1)^{\alpha^m}\\
(\alpha^2)^{\alpha^1} & \cdots & (\alpha^2)^{\alpha^m}\\
\vdots & \vdots & \vdots\\
(\alpha^m)^{\alpha^1} & \cdots & (\alpha^m)^{\alpha^m}
\end{bmatrix}$$

où la notation $(\alpha^i)^{\alpha^j} = \displaystyle\prod_{k=1}^{n}(\alpha^i_k)^{\alpha^j_k}$ (ici, $0^0=1$ et $\alpha^k$ est une notation d'une liste de nombres naturels qui n'est pas $\alpha$ puissance $k$).

Question: Montrer que $V$ est inversible ou trouver un contre-exemple.

PS: J'ai testé plusieurs exemples, et il semble que $V$ est toujours inversible, mais je ne sais pas comment le démontrer ou trouver un contre-exemple. Merci d'avance pour partager quelque idée!

Dernière modification par kaien (17-07-2020 18:48:16)

LCTD

Membre

Inscription : 21-11-2019

Messages : 85

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour,

Il y a peut-être une piste en calculant le déterminant :

$V = \begin{bmatrix} (\alpha^1)^{\alpha^1} & \cdots & (\alpha^1)^{\alpha^m}\\ (\alpha^2)^{\alpha^1} & \cdots & (\alpha^2)^{\alpha^m}\\ \vdots & \vdots & \vdots\\ (\alpha^m)^{\alpha^1} & \cdots & (\alpha^m)^{\alpha^m} \end{bmatrix}$

$det(V) =(\alpha^1)^{\alpha^1} (\alpha^2)^{\alpha^1}\cdots (\alpha^m)^{\alpha^1}$ $\begin{bmatrix} 1 &(\alpha^1)^{\alpha^1} & \cdots&(\alpha^1)^{\alpha^{m-1}}\\ 1 & (\alpha^2)^{\alpha^1} &\cdots & (\alpha^2)^{\alpha^{m-1}}\\ \vdots & \vdots & \vdots\\ 1 & (\alpha^m)^{\alpha^1} &\cdots & (\alpha^m)^{\alpha^{m-1)}} \end{bmatrix}$

et ainsi de suite
je pense qu'on doit pouvoir trouver une formule.

kaien

Membre

Inscription : 17-07-2020

Messages : 6

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour,

Il y a peut-être une piste en calculant le déterminant :

$V = \begin{bmatrix} (\alpha^1)^{\alpha^1} & \cdots & (\alpha^1)^{\alpha^m}\\ (\alpha^2)^{\alpha^1} & \cdots & (\alpha^2)^{\alpha^m}\\ \vdots & \vdots & \vdots\\ (\alpha^m)^{\alpha^1} & \cdots & (\alpha^m)^{\alpha^m} \end{bmatrix}$

$det(V) =(\alpha^1)^{\alpha^1} (\alpha^2)^{\alpha^1}\cdots (\alpha^m)^{\alpha^1}$ $\begin{bmatrix} 1 &(\alpha^1)^{\alpha^1} & \cdots&(\alpha^1)^{\alpha^{m-1}}\\ 1 & (\alpha^2)^{\alpha^1} &\cdots & (\alpha^2)^{\alpha^{m-1}}\\ \vdots & \vdots & \vdots\\ 1 & (\alpha^m)^{\alpha^1} &\cdots & (\alpha^m)^{\alpha^{m-1)}} \end{bmatrix}$

et ainsi de suite
je pense qu'on doit pouvoir trouver une formule.

Bonjour,
Merci pour les remarques.
Mais, je ne vois pas comment l'on peut extraire $(\alpha^1)^{\alpha^1}$ depuis la première ligne!
En effet, $\alpha^k$ n'est pas $\alpha$ puissance $k$. Donc $(\alpha^1)^{\alpha^2}/(\alpha^1)^{\alpha^1} = (\alpha^1)^{\alpha^2-\alpha^1}\neq (\alpha^1)^{\alpha^1}.$

kaien

Membre

Inscription : 17-07-2020

Messages : 6

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Pour mieux comprendre la question, voici un exemple:
Soit $n=3$ et $d=2$, alors tous les choix possibles pour mettre $2$ balles dans $3$ bins sont:
$$B = \{(2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)\}.$$
Les éléments pour la première ligne de la matrice $V$ sont donc:
$$(\alpha^1)^{\alpha^1} = (2,0,0)^{(2,0,0)} = 2^2\times 0^0\times 0^0 = 4,$$
$$(\alpha^1)^{\alpha^2} = (2,0,0)^{(0,2,0)} = 2^0\times 0^2\times 0^0 = 0,$$
et ainsi de suite.
On a alors la matrice $V$ suivante:
$$V = \begin{bmatrix}
4&0&0&0&0&0\\
    0&4&0&0&0&0\\
    0&0&4&0&0&0\\
    1&1&0&1&0&0\\
    1&0&1&0&1&0\\
    0&1&1&0&0&1\\
\end{bmatrix}.
$$
Clairement, cet matrice est inversible.
Bien noté que la matrice $V$ n'est pas toujours triangulaire comme ci-dessus, car pour certain $n$ et $d$, il existe des éléments $(\alpha^i)^{\alpha^j}$ et $(\alpha^j)^{\alpha^i}$ (avec $i\neq j$) tous non-nuls. Par exemple: n=3, d=3, alors les éléments $$(2,1,0)^{(1,2,0)} = 2^1\times 1^2 \times 0^0 = 2,$$ et $$(1,2,0)^{(2,1,0)} = 1^2\times 2^1 \times 0^0 = 2$$
sont tous non-nuls.
De plus, quand $(\alpha^i)^{\alpha^j}$ et $(\alpha^j)^{\alpha^i}$  (avec $i\neq j$) sont tous non-nuls, ils ne sont pas toujours égaux.
E.g., n=4, d=8, on a
$$(1,1,2,4)^{(2,2,2,2)} = 64$$
mais
$$(2,2,2,2)^{(1,1,2,4)} = 256.$$

Donc on peut conclure que: "la matrice $V$ est ni triangulaire ni symétrique en général."

Dernière modification par kaien (17-07-2020 20:07:15)

LCTD

Membre

Inscription : 21-11-2019

Messages : 85

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour,

Sorry, effectivement vous avez raison. Je continue de regarder et reviens vers vous si j'ai une idée.

kaien

Membre

Inscription : 17-07-2020

Messages : 6

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour,

Sorry, effectivement vous avez raison. Je continue de regarder et reviens vers vous si j'ai une idée.

Bonjour LCTD,
Merci d'avance! En espérant d'avoir des nouvelles idées.

Maenwe

Membre confirmé

Inscription : 06-09-2019

Messages : 409

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour,
avant de t'aider, j'ai besoin de plusieurs précisions :
* est-ce que $m=n$ ?
* Comment ordonnes tu ton ensemble $B$ ?
* Qu'entends tu par bins ? (des poubelles/pots en anglais ?)

Dernière modification par Maenwe (21-07-2020 12:23:09)

kaien

Membre

Inscription : 17-07-2020

Messages : 6

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour,
avant de t'aider, j'ai besoin de plusieurs précisions :
* est-ce que $m=n$ ?
* Comment ordonne tu ton ensemble $B$ ?
* Qu'entends tu par bins ? (des poubelles/pots en anglais ?)

Bonjour,
Merci pour les remarques. Voici les réponses:
1. Non! Le nombre $m$ pourra être calculé par le nombre des choix possibles pour mettre $d$ balles dans $n$ bins (bin vide autorisé). On peut donc le calculer en fonction de $n$ et $d$ par: $m = {d+n-1 \choose d}$ (voir par exemple, https://en.wikipedia.org/wiki/Stars_and … inatorics) pour avoir des idées sur le calcul).
2. L'ordre des éléments dans $B$ n'est pas important, en effet, si vous permuter deux éléments quelconques $\alpha^i$ et $\alpha^j$ de $B$, vous aurez une permutation des lignes et des colonnes de la matrice $V$ qui n'a rien changé l'inversibilité de $V$. 
3. Le mot “Bins” est plutôt en anglais, vous pouvez le remplacer par le mot "Boites" ou "Sacs" en française (même les mots poubelles/pots si vous voulez ;-) n'ont rien changé le problème). Mais une chose plus importante à préciser est que l'on ne suppose pas un volume maximum au bin, c'est-à-dire que chaque bin pourra contenir un nombre infini de balles.

Dernière modification par kaien (19-07-2020 06:00:58)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Salut,

ton sujet est amusant, pas sûr qu'on arrive à y répondre, car il a l'air assez compliqué. Possible que la réponse passe par un examen très attentif de la manière de fabriquer les coefficients de la matrice selon le procédé indiqué pour voir si des colonnes (ou lignes) sont susceptibles d'être liées entre elles.

Petite question : d'où vient ce sujet ? Dans quels cadre et contexte se pose t-il ? Merci de tes réponses.

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

kaien

Membre

Inscription : 17-07-2020

Messages : 6

Re : Démontrer que la matrice V est inversible ou trouver un contre-exemple

Bonjour Freddy,

Merci de votre intérêt et de commentaires sur mon problème.

En effet, j'ai trouvé cette matrice par accident! Je me réfléchi comment construire une base des polynômes homogènes et convexes avec $n$ variables et de degré $d$, c-à-d, chercher une famille libre des polynômes "homogènes" et "convexes" avec $n$ variables de degré $d$ qui nous permet d'engendrer tous les polynômes homogènes de degré $d$. Enfin, je me permet de démontrer l'existence de telle famille, et il me semble aussi réussir à construire une telle base. Pour la justification, j'arrive à démontrer que la famille j'ai construit est une base demandée si et seulement si la matrice de la forme $V$ est inversible. Ensuite, j'ai testé plusieurs exemples avec différents $n$ et $d$, et constaté que $V$ ressemble toujours inversible (au moins je n'ai pas trouvé un exemple contraire avec l'ordinateur en ce moment). Alors, il me reste à démontrer le résultat théorique qui me bloque depuis quelques jours. Enfin, j'ai une idée de partager la question en ligne pour avoir plus de discussions. :-)

En espérant d'avoir quelque idée. Merci pour toutes et tous qui ont participé ou qui vont participer à la discussion.

Dernière modification par kaien (19-07-2020 11:36:15)