Un déterminant et une trace

gebrane

Bonjour

On vient de me proposer cet exercice que je partage.

Soit A une matrice d'ordre $n$ [de taille $n\times n$ ?], à coefficients $(a_{i,j})$ vérifiant :

$a_{i,1}=a_{1,j}=1,\quad  \forall 1\leq i,j\leq n,\quad a_{i,j}=a_{i-1,j}+a_{i,j-1}+n, \quad   \forall 1< i,j\leq n$.
Calculer la trace de $A$ et son déterminant.

GaBuZoMeu

Bonjour,

On a donc $a_{i,j}= C_{i+j-2}^{i-1}(1+n) - n$.

gebrane

Merci, je vais essayer de retrouver ce calcul, donc le calcul de la trace est pliée.  Il reste le déterminant. 

Positif

Rien d’évident n’apparaît quand je fais tourner mon ordi . Excepté que $\det M_9 = 100000000$

GaBuZoMeu

ce qui colle bien avec $(1+n)^{n-1}$.

Epsilon maths

Numériquement, les premières valeurs sont : 1, 3, 16, 125, 1296, 16807, 262144, 4782969, 100000000, 2357947691, 61917364224
Ce qui donne la suite A000272 de lOEIS....
(Ce que l'on ne fait pas pour laisser les copies de côté).

GaBuZoMeu

Pas besoin d'ordinateur ni d'OEIS : Pascal suffit !

bd2017

Bonjour

Le déterminant vaux  $(n+1)^{n-1}$

GaBuZoMeu

Copieur !

gebrane

Ce que je sais, c'est seulement que la matrice définie par 
$$a_{i,1}=a_{1,j}=1,\quad  \forall 1\leq i,j\leq n,\quad a_{i,j}=a_{i-1,j}+a_{i,j-1}, \quad   \forall 1< i,j\leq n$$ est la matrice de Pascal.
Pour s'y ramener, je ne sais pas pour le moment !

GaBuZoMeu

Tu n'arrives pas à la formule de mon premier message ?
C'est pourtant une récurrence simple.

gebrane

Je suis dans un café avec mes amis, Le soir,  j'aurais le temps, la tranquillité et papier crayon. Ce qui me fait plus de peur c'est le calcul de ce déterminant monstrueux.

GaBuZoMeu

Bah, ce monstre se dégonfle vite.

gebrane

Rassure moi, pour ce déterminant, vous n'utilisez pas un truc de genre A=L.U ( A comme produit de deux matrices comme pour la matrice de Pascal)

GaBuZoMeu

Bah, retirer à une colonne la colonne précédente, puis retirer à une ligne la ligne précédente, ça ne devrait pas te faire peur. Si ?

gebrane

On verra quand je serai chez moi .

gebrane

Oui ça se dégonfle si on a l'idée de ta première opération sur les colonnes qui donne $\det(A)=\det (B)$ avec $B=b_{i,j}$ d'ordre $n$ définie par
$a_{i,1}=1,\ \forall i\ge 1$, $\ b_{1,j}=0,\ \forall j\geq 2$

$b_{i,j}=(n+1) C^{i-2}_{i+j-3} ,\ \forall i,j\ge 2$

Et on développe par rapport à la première ligne en factorisant par ce fameux $(n+1)$ qui sort du déterminant en $(n+1)^{n-1}$ que je ne voyais pas de tête.

gebrane

J'invente cette matrice diabolique $$a_{i,1}=a_{1,j}=1,\quad  \forall 1\leq i,j\leq n,\quad a_{i,j}=a_{i-1,j}+a_{i,j-1}+i-j, \quad   \forall 1< i,j\leq n$$
Calculer son déterminant. Je ne garantis rien 
Est ce que quelqu'un peut entrer ce code dans marhematica 

RSolve[{a[n,k]==a[n-1,k]+a[n-1,k-1]+n-k ,a[n,1]==1,a[1,n]==1},a[n,k],{n,k}]

jandri

Il me semble que $\det(A_n)=F_n$ (suite de Fibonacci), je l'ai vérifié jusqu'à $n=12$.

gebrane

Merci, ca devient intéressant.

@Boécien Mon compagnon, toi qui aime les suites de Fibonacci, vient dans ce fil, c'est un ordre .

jandri

Il me semble que la trace de $A_n$ est égale à $\displaystyle\sum_{k=0}^{n-1}{\binom {2k} k}$.

gebrane

Bonjour @Jandri tu as trouvé quoi pour les coefficients de la matrice $a_{i,j}$

jandri

Ce n'est pas simple : $a_{i,j}=\displaystyle{\binom{i+j-1}{j}}-{\binom{i+j-2}{i}}-i+j$.

gebrane

Merci Jandri, Tu me refroidis les os. Ne perd pas ton brouillon stp. Je vais essayer mais je sens que je n'y arriverais jamais 

gebrane

@Jandri  je trouve $$a_{i,j}=\binom{i+j}{i}+j-i,\quad \forall 2\leq i,j\leq n$$avec  bien sûre $a_{i,1}=a_{1,j}=1,\quad  \forall 1\leq i,j\leq n$

Math Coss

Les calculs numériques sur des petites valeurs semblent donner raison à @jandri mais pas à @gebrane.

sage: def a(i,j):
....:    """ récurrence initiale """
....:     if i==0 or j==0:
....:         return 1
....:     return a(i-1,j)+a(i,j-1)+i-j
....: 
sage: def b(i,j):
....:    """ version de jandri """
....:     i, j = i+1, j+1
....:     return binomial(i+j-1,j)-binomial(i+j-2,i)-i+j
....: 
sage: def c(i,j):
....:    """ version de gebrane """
....:     if i==0 or j==0:
....:         return 1
....:     i, j = j+1, j+1
....:     return binomial(i+j,i)+j-i
....: 
sage: Matrix(8,8,a)-Matrix(8,8,b)
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0]
sage: Matrix(8,8,a)-Matrix(8,8,c)
[     0      0      0      0      0      0      0      0]
[     0     -4    -18    -69   -253   -928  -3440 -12883]
[     0     -2    -14    -64   -249   -928  -3448 -12904]
[     0      1     -6    -50   -230   -908  -3435 -12911]
[     0      5      7    -22   -182   -839  -3352 -12834]
[     0     10     26     26    -85   -672  -3101 -12505]
[     0     16     52    101     88   -331  -2508 -11582]
[     0     23     86    211    372    295  -1288  -9438]

gebrane

Merci @Math Coss   C'est un calcul flippant 
Peux-tu expliquer tes calculs stp @Jandri et si possible avec les détails qu'il faut.
(J'ai posé cette question sur un autre forum et ils ont trouvé que ma formule est fausse, je vais leur proposer celle de Jandri).

jandri

Pour trouver la formule je suis passé par $b_{i,j}=a_{i,j}+i-j$ qui vérifie $b_{i,j}=b_{i-1,j}+b_{i,j-1}$.

Mais une fois qu'on a la formule pour $a_{i,j}$ elle se démontre très facilement par récurrence (il suffit d'utiliser la relation de Pascal).

gebrane

Merci, le calcul de ce déterminant relève de la sorcellerie mathématiques.
J'abandonne. 

Boécien

Juste une remarque sans intérêt. Si $a_{i,j}={j \choose i+j-1}-{i \choose i+j-2}-i+j$ alors le déterminant de la matrice de terme $b_{i,j}=a_{i,j}+a_{j,i}=2{i-1 \choose i+j-2}$ vaut $2^{n}$.

gebrane

Cette question est intouchable  comme la tienne

Boécien

Je pense que c'est jouable pour un "combinatoriste" car il y a plein de sommes avec les binomiaux liées aux Fibonacci. Si on prend $a_{i,j}={j\choose i+j-1}-{i \choose i+j-2}-x+y$ il semble que le déterminant vaut $F_{n+1}+\left(y-x\right)F_{n}$. Donc on peut essayer de montrer le cas $x=y$.

Boécien

Je signale cet article sur le calcul de déterminants mais pour l'instant je n'arrive pas à appliquer. On y trouve des cas avec les binomiaux mais pas directement celui là comme le (2.19), (3.30), (3.31)....
Dans les références on a aussi celui-ci .

gebrane

Ok, je vais reprendre la question en s'inspirant de tes liens

gebrane

Je pense que la méthode de Gabu s'applique retirer à une colonne la colonne précédente, puis retirer à une ligne la ligne précédente. 

Boécien

Oui c'est pourquoi il suffit de s'intéresser au déterminant de la matrice $M_n$ de terme $a_{i,j}={j \choose i+j-1}-{i \choose i+j-2}$ qui semble valoir $F_{n+1}$.  Cela suggère de montrer que ce déterminant vérifie la même relation de récurrence que les nombres de Fibonacci.

gebrane

Il faut quelqu'un qui connait bien ces $\binom{}{}$

jandri

J'ai réussi à démontrer que $\det(A_n)=F_n$ où $A_n$ est la matrice d'ordre $n$ de gebrane définie par : 
$a_{i,1}=a_{1,j}=1$ pour $1\leq i,j\leq n$ et $a_{i,j}=a_{i-1,j}+a_{i,j-1}+i-j$ pour $1< i,j\leq n$.

On introduit la matrice $B_n$ dont le terme général est défini par $b_{i,j}=a_{i,j}+i-j$.
Elle vérifie $b_{i,1}=i$, $b_{1,j}=2-j$ et pour $i,j\geq2$ : $b_{i,j}=b_{i-1,j}+b_{i,j-1}$.

On effectue sur la matrice $A_n$ les opérations $C_j\leftarrow C_j-C_{j-1}$ pour $j$ de $n$ à $2$ puis les opérations $L_i\leftarrow L_i-L_{i-1}$ pour $i$ de $n$ à $2$. Cela donne une matrice qui a des $0$ en ligne $1$ et colonne $1$ (à l'exception du premier terme qui vaut $1$) et le reste est la matrice $B_{n-1}$, donc $\det(A_n)=\det(B_{n-1})$.

Ensuite on effectue les mêmes opérations sur la matrice $B_n+xJ_n$ où $J_n$ est la matrice d'ordre $n$ dont tous les termes valent $1$.
On obtient la matrice écrite en 4 blocs : $\left (\begin{array}{c|c} 1+x & L \\ \hline  C&  B_{n-1} \end{array}\right)$ où $L$ est la ligne dont tous les termes valent $-1$ et $C$ la colonne dont tous les termes valent $1$. On en déduit $\det(B_n+xJ_n)=(1+x)\det(B_{n-1}+\frac1{x+1}J_{n-1})$

On obtient alors par récurrence sur $n$ que $\det(B_n+xJ_n)=F_{n+1}+xF_n$ d'où $\det(B_n)=F_{n+1}$ puis $\det(A_n)=F_n$.

gebrane

Bravo @Jandri, 

gebrane

Il faut rendre à César ce qui appartient à César .  Chaque acte,  doit être attribuée à son auteur. Chacun doit être reconnu pour ce qu'il a fait, pas pour  ce qu'il a copié.  https://mathoverflow.net/questions/430944/hard-determinant-equal-to-fibonacci-sequence?noredirect=1#comment1110110_430944

jandri

gebrane
Merci d'avoir traduit ma démonstration en anglais (avec mon pseudo).

On peut faire la même démonstration pour ta matrice généralisée, $A_n(x)$, vérifiant $a_{i,1}=a_{1,j}=1$ et $a_{i,j}=a_{i-1,j}+a_{i,j-1}+x(i-j)$.

 En introduisant $B_n$ dont le terme général est défini par $b_{i,j}=a_{i,j}+x(i-j)$ on obtient $\det(A_n(x))=\det(B_{n-1}(x))$ puis $\det(B_n(x)+yJ_n)=(1+y)\det(B_{n-1}(x)+\frac{x^2}{y+1}J_{n-1})$.

On en déduit $\det(B_n(x)+yJ_n)=a_n(x)+y\;a_{n-1}(x)$ où la suite $a_n(x)$ vérifie $a_0=a_1=1$ et $a_{n+1}(x)=a_n(x)+x^2\;a_{n-1}(x)$.

Par suite $\det(A_n(x))=a_{n-1}(x)$. Pour $x=0$ on retrouve la matrice de Pascal, pour $x=1$ celle de gebrane.

On peut montrer par récurrence que $a_n(x)=\displaystyle \sum_{k=0}^{\lfloor n/2\rfloor}{\binom{n-k}k}x^{2k}$.

gebrane

Aussi, l'intervenant  JC propose le problème $a_{i,j}=x(\binom{i+j-1}{j}+j-i)-y \binom{i+j-2}{i}.$ et il conjecture que $\Delta_n=x \Delta_{n-1}+ x y\Delta_{n-2}, \forall n\ge 3.$

jandri

Cette dernière matrice ressemble beaucoup à celle que j'ai considérée juste au-dessus, elle vérifie aussi $a_{i,j}=a_{i-1,j}+a_{i,j-1}+x(i-j)$. La seule différence est que $a_{i,1}=x$ et $a_{1,j}=jx-(j-1)y$.

Elle se traite exactement de la même façon en introduisant la matrice $B_n$ de terme général $b_{i,j}=a_{i,j}+x(i-j)$.

On obtient $\det(A_n)=x\;\det(B_{n-1})$ puis $\det(B_n+zJ_n)=(x+z)\det(B_{n-1}+\frac{xy}{x+z}J_{n-1})$.

On en déduit $\det(B_n+zJ_n)=a_n+z\;a_{n-1}$ avec $a_0=1$, $a_1=x$ et $a_{n+1}=x\;a_n+xy\;a_{n-1}$ et par suite $\det(A_n)=x\;a_{n-1}$.

La suite $\det(A_n)$ suit donc la même relation de récurrence que la suite $a_n$.

gebrane

Je vais inscrire aussi ces deux solutions. Le site Mo regroupe les plus grands chercheurs au monde
. Quelqu'un m' a demandé d'où vient ce genre de récurrence. Je réfléchis si on tombe sur ce genre de problème via un problème de proba, dénombrement ou autres
Merci beaucoup Jandri