Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 17-07-2020 05:03:53

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 16:48:16)

Hors ligne

#2 17-07-2020 13:12:41

LCTD
Membre
Inscription : 21-11-2019
Messages : 39

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.

Hors ligne

#3 17-07-2020 16:20:12

kaien
Membre
Inscription : 17-07-2020
Messages : 6

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

LCTD a écrit :

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

Hors ligne

#4 17-07-2020 17:40:02

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 18:07:15)

Hors ligne

#5 17-07-2020 19:38:02

LCTD
Membre
Inscription : 21-11-2019
Messages : 39

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.

Hors ligne

#6 18-07-2020 02:44:02

kaien
Membre
Inscription : 17-07-2020
Messages : 6

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

LCTD a écrit :

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.

Hors ligne

#7 18-07-2020 11:19:38

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 10:23:09)

Hors ligne

#8 19-07-2020 03:13:42

kaien
Membre
Inscription : 17-07-2020
Messages : 6

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

Maenwe a écrit :

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 04:00:58)

Hors ligne

#9 19-07-2020 07:37:18

freddy
Membre chevronné
Lieu : Paris
Inscription : 27-03-2009
Messages : 7 451

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.

Hors ligne

#10 19-07-2020 09:10:09

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 09:36:15)

Hors ligne

Pied de page des forums