El determinante de una generalizada de la matriz de Pascal

Question

Deje $M$ denotar el infinito de la matriz definida recursivamente por

$$ M_{ij} = \begin{cases} 1, & \text{if } i=1 \text{ and } j=1; \\ aM_{i-1,j}+bM_{i,j-1}+cM_{i-1,j-1}, & \mbox{otherwise}.\\ \end{casos} $$ ($M_{i,0}$$M_{0,j}$ se definen a ser $0$.)

(Añadido: acabo de descubrir que los números de la $M$ matriz se llama ponderado Delannoy números.)

Deje $M_n$ el valor del $n \times n$ superior izquierda submatriz de a $M$.

Por ejemplo, con $a = b = c = 1$,

$M_1 = \begin{bmatrix} 1 \end{bmatrix}$, $M_2= \begin{bmatrix} 1 & 1 \\ 1 & 3 \end{bmatrix}$, y $M_3 = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 3 & 5 \\ 1 & 5 & 13 \end{bmatrix}$, y $M_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 3 & 5 & 7 \\ 1 & 5 & 13 & 25 \\ 1 & 7 & 25 & 63 \end{bmatrix}.$

Hace un par de años uno de mis estudiantes demostrado, por inducción, que $$\det M_n = (ab+c)^{n(n-1)/2}.$$
Mi pregunta es

Hay un noninductive prueba de que $\det M_n = (ab+c)^{n(n-1)/2}$ que ofrece una visión más clara de por qué el determinante funciona tan bien?

Por ejemplo, cuando $a = b = 1$, $c = 0$, $M$ es la simétrica de la matriz de Pascal. He visto más de una manera de demostrar que $\det M_n = 1$ en este caso. Por ejemplo, Edelman y Strang dar cuatro pruebas de un LU-descomposición que hace. Yo también vi una vez, en una conferencia, una combinatoria de la prueba mediante la interpretación de la determinante en términos de nonintersecting caminos en un grafo dirigido. (Creo que la charla fue dada por el Art Benjamin, pero fue hace varios años, y yo podría ser misremembering.) Así que sé que hay algunas buenas pruebas en el caso especial de la matriz de Pascal. Pero, ¿y el caso general?

Answer 1

Inspirado por la solución de Sivaram Ambikasaran, me gustaría proporcionar algunos concisión. Dado $$ M_{i,j} = \begin{cases} a^{i-1}b^{j-1} & \text{if } i=1 \text{ or } j=1, \\ aM_{i-1,j}+bM_{i,j-1}+cM_{i-1,j-1} & \mbox{if }i>1 \text{ and } j>1,\\ \end{casos} $$ uno puede (inspirado por lo que se dice en la Edelman-Strang papel) empezar a restar de cada fila (excepto la primera) $a$ veces la fila anterior. Esto se debe hacer de forma simultánea, o trabajando de abajo hacia arriba, de modo que es el original, el valor de la fila en la que se resta. Esto equivale a la izquierda-multiplicando por la eliminación de la matriz $E_{-a}$ diagonal con entradas de $1$ y subdiagonal entradas de $-a$. Se obtiene una matriz de $M'$ dada por $$ M'_{i,j} = \begin{cases} b^{j-1} & \text{if } i=1, \\ M_{i,j}-aM_{i-1,j} & \mbox{if }i>1.\\ \end{casos} $$ La última expresión es $0$ si $j=1$, y de lo contrario $$ M'_{i,j} = bM_{i,j-1}+cM_{i-1,j-1}\qquad\text{si }i,j>1 $$ el uso de la recursividad de la definición de $M$. Ahora se procederá de manera similar por columnas, a la derecha-multiplicando por la transposición $E_{-b}^\top$$E_{-b}$, dando una nueva matriz $M''$ dada por $$ M"_{i,j} = \begin{cases} \delta_{i,j} & \text{if } j=1, \\ M'_{i,j}-bM'_{i,j-1} & \mbox{if }j>1.\\ \end{casos} $$ La última expresión es $0$ si $i=1$, y de lo contrario $$\begin{align} M''_{i,j} &= bM_{i,j-1}+cM_{i-1,j-1}-b(M_{i,j-1}-aM_{i-1,j-1})\\ & =(ab+c)M_{i-1,j-1} \end{align}\qquad\text{si }i,j>1, $$ el uso de las dos expresiones para $M'_{i,j}$ dado anteriormente. En otras palabras, se tiene en forma de bloque $$ M"=\begin{pmatrix}1&0\\ 0&(ab+c)M_{(n-1)}\end{pmatrix} $$ donde $M_{(n-1)}$ $(n-1)\times(n-1)$ superior izquierda submatriz de a $M$, que es su contraparte de tamaño uno menos. Por lo tanto $$ \det M_{(n)} = \det M = \det M"= (ab+c)^{n-1} \det M_{(n-1)} $$ a partir de la cual se deduce por inducción que $\det M=(ab+c)^{\tbinom{n}2}$.

El escalar multplication de $M_{(n-1)}$ $ab+c$ puede, por supuesto, se dio cuenta de como la multiplicación por un múltiplo de la matriz identidad, que conmuta con las matrices obtenidas en una descomposición recursiva de $M_{(n-1)}$. A continuación, es fácil llegar a la conclusión de que uno tiene una descomposición $$ M_{(n)} = L_{(n)} D_{(n)} U_{(n)} $$ donde $D_{(n)}$ es diagonal con entradas de $(D_{(n)})_{i,i}=(ab+c)^{i-1}$ $L_{(n)}$ $U_{(n)}$ son unitriangular y por lo tanto tienen determinante $1$. Su forma explícita puede ser obtenido a partir de las recurrencias $$ L_{(n)} = (E_{-a})^{-1}\cdot \begin{pmatrix}1&0\\ 0&L_{(n-1)}\end{pmatrix}, \qquad U_{(n)} = \begin{pmatrix}1&0\\ 0&U_{(n-1)}\end{pmatrix}\cdot(E_ {b}^\la parte superior)^{-1}, $$ que se puede encontrar fácilmente para ser resueltos por $(L_{(n)})_{i,j}=\binom{i-1}{j-1}a^{i-j}$$(U_{(n)})_{i,j}=\binom{j-1}{i-1}b^{j-i}$, o $((E_{-a})^{-1})_{i,j}=a^{i-j}$ o mediante la resolución de primera $((L_{(n)})^{-1})_{i,j}=\binom{i-1}{j-1}(-a)^{i-j}$.

Answer 2

Esto no es una respuesta, sino más bien un comentario de Sivaram la respuesta.
[actualización] he de corregir los ejemplos numéricos debido a que utiliza un poco distorsionada versión de M. Pero esto no afecta a la idea básica de la utilización de la LDU-decompostion en lugar de la LU-de la descomposición. Por último, esto no es ahora mucho más que una ligera optimización de Sivaram del ansatz

Si me descomponen en $\small L \cdot D \cdot U $ en lugar, donde D es diagonal, entonces el patrón de la construcción de los factores L y U es más "sencillo"(contiene sólo una resp. b) pero sus diagonales son 1 y por lo tanto puede ser ignorada por el determinante. Tan sólo necesitamos el factor determinante de la D. A continuación nos encontramos, que D puede ser descrito por
$\qquad \small D=[1,c+ab, (c+ab)^2, (c+ab)^3,\ldots ,(c+ab)^{n-1} ] = dV(c+ab,n) $

y el determinante de la matriz de tamaño n x n es entonces el producto de estos términos hasta n-1 por una evidente expresión simple. De nuevo el patrón encontrado en el LDU-descomposición debe ser probado, pero el enfoque que podría permitir una ruta más corta...

[añadido] : El real LDU-la descomposición puede ser escrito como

$\qquad \small M = P^{\quad a} \cdot \quad dV(c+ab) \cdot (P^{\quad b} \sim )$

donde P es el menor triangular Pascalmatrix, "~" significa el transporte y dV(x) es la diagonalmatrix que contiene las sucesivas potencias de su argumento x , comenzando a $\small x^0 $

(nota: yo también prefiero este LDU a menudo debido a que evita la introducción de sqaures y/o squareroots, como por ejemplo hace el cholesky-descomposición para la simétrica caso)

---

en caso de que su software tiene un LDU-descomposición no disponible, aquí está el código utilizable para Pari/GP

 LDU(Y) = local(dim=#Y, D, MR, ML, dx); \\ Y must be square, 
       \\ no errorchecks in     demo-documentation
 D=matrix(dim,dim); MR=matid(dim); ML=matid(dim);
 for(p=1,dim, 
   D[p,p]=(dx=Y[p,p]);
   for(c=p+1,dim,
        MR[p,c]=if(dx==0,0,Y[p,c]/dx)
       );
   for(r=p+1,dim, 
        ML[r,p]=if(dx==0,0,Y[r,p]/dx)
      );
   for(r=p+1,dim,
      for(c=p+1,dim,
            Y[r,c]-=ML[r,p]*dx*MR[p,c]
      ));
  );
return([ML,D,MR]);

La matriz L tiene la forma [ha corregido ahora!] $\small L = P^a $

$\pequeño \begin{array} {lllll} 1 & . & . & . & . & . \\ a & 1 & . & . & . & . \\ a^2 & 2a & 1 & . & . & . \\ a^3 & 3a^2 & 3a & 1 & . & . \\ a^4 & 4a^3 & 6a^2 & 4a & 1 & . \\ a^5 & 5a^4 & 10a^3 & 10a^2 & 5a & 1 \end{array} $

mientras que U es simplemente la transposición y una sustituido por b.

---

[actualización] Aquí está el Pari/GP código para generar la matriz M (corregido) y la convocatoria para la LDU-descomposición:

M = matrix(6,6,r,c); for(r=1,6,M[r,1]='a^(r-1)); for(c=1,6,M[1,c]='b^(r-1));
    for(r=2,rows(M),for(c=2,cols(M),M[r,c]='a*M[r-1,c]+'b*M[r,c-1]+'c*M[r-1,c-1]))
M_ldu = LDU(M); L=M_ldu[1];D=diag(M_ldu[2]);U=M_ldu[3];
print (D)  \\ check the diagonal-component
%1164 = [1,
         c + a*b ,
         c^2 + 2*b*a*c + b^2*a^2,
         ... (snipped) ] ~

Answer 3

La identidad de la siguiente manera casi de inmediato desde el determinante de la fórmula para el conteo de los no-caminos se cruzan:

• por un lado, el factor determinante cuenta el número de no-intersección de las rutas desde los puntos de $a_i=(-i,0)$ a los puntos de $b_i=(0,i)$ sobre el enrejado con $a$ bordes yendo a la derecha, $b$, e $c$ arriba-derecha (por cada vértice);

• por otro lado, para elegir no-caminos se cruzan medio para seleccionar la ruta de acceso de cada una de las $n(n-1)/2$ "interna" de vértices es superior derecha del vecino - que se puede hacer exactamente $ab+c$ maneras: uno puede ir hacia arriba, a continuación, a la derecha o en diagonal (por ejemplo, cuando se $c=0$ no es, obviamente, sólo una "geométrica" ruta de acceso con algo de peso). Upd: eso no es del todo cierto, voy a tratar de solucionarlo.