Polinomios característicos de una clase de matrices simples

Question

Sea $M_{k}$ sea la matriz kxk con entradas $m(i,j,k)=0$ para $i+j<k-1$ y $m(i,j,k)=1$ si no. Por ejemplo $M_{3}=\begin{bmatrix}0 & 0 & 1\\0&1&1\\ 1&1&1\end{bmatrix}.$

Sea $F_{n}(x)$ denotan los polinomios de Fibonacci definidos por $F_{n}(x)= F_{n-1}(x)+x F_{n-2}(x)$ con valores iniciales $ F_{0}(x)= F_{1}(x)=1.$

Los cálculos sugieren que el polinomio característico de $M_{k}^2$ es $F_{2k}(-x)=\sum_{j=0}^k\binom{2k-j}{j}(-x)^k.$

¿Existe una prueba sencilla de este resultado?

Answer 1

Las plazas $N_k = M_k^2$ son matrices muy bonitas: tenemos (indexando desde $1$ a $k$ )

$$N_k(i, j) = \text{min}(i, j)$$

de ahí, por ejemplo,

$$N_4 = \left[ \begin{array}{cc} 1 & 1 & 1 & 1 \\ 1 & 2 & 2 & 2 \\ 1 & 2 & 3 & 3 \\ 1 & 2 & 3 & 4 \end{array} \right].$$

Definir los polinomios $P_k(x) = \det (N_k - xI)$ y (resulta que lo necesitaremos) definir también $Q_k(x)$ sea el determinante de $N_k - \text{diag}(x, x, \dots 0)$ . Restando la penúltima fila de la última fila de $N_k - xI$ da la última fila $(0, 0, \dots x, 1-x)$ y la expansión de Laplace a lo largo de esta fila da

$$P_k(x) = (1 - x) P_{k-1}(x) - x Q_{k-1}(x).$$

La misma operación de fila para $N_k - \text{diag}(x, x, \dots 0)$ da la última fila $(0, 0, \dots x, 1)$ y la expansión de Laplace a lo largo de esta fila da

$$Q_k(x) = P_{k-1}(x) - x Q_{k-1}(x).$$

Esto da

$$\left[ \begin{array}{c} P_k(x) \\ Q_k(x) \end{array} \right] = \left[ \begin{array}{cc} 1-x & -x \\ 1 & -x \end{array} \right] \left[ \begin{array}{c} P_{k-1}(x) \\ Q_{k-1}(x) \end{array} \right]$$

que, junto con las condiciones iniciales $P_0(x) = 1, Q_0(x) = 0$ (que puede comprobar que es coherente con $P_1(x) = 1-x, Q_1(x) = 1$ ), da

$$\left[ \begin{array}{c} P_k(x) \\ Q_k(x) \end{array} \right] = \left[ \begin{array}{cc} 1-x & -x \\ 1 & -x \end{array} \right]^n \left[ \begin{array}{cc} 1 \\ 0 \end{array} \right].$$

Así que $P_k(x)$ satisface una relación de recurrencia lineal con polinomio característico el polinomio característico de $\left[ \begin{array}{cc} 1-x & -x \\ 1 & -x \end{array} \right]$ que es

$$\lambda^2 - (1-2x) \lambda + x^2.$$

Esto da $P_0(x) = 1, P_1(x) = 1 - x$ y

$$P_k(x) = (1 - 2x) P_{k-1}(x) - x^2 P_{k-2}(x).$$

Esto coincide con tus polinomios de Fibonacci por inducción, aunque ten en cuenta que Wikipedia utiliza condiciones iniciales diferentes y pone el $x$ en un lugar diferente al tuyo y no sé cuál es la convención estándar. Para ver esto concretamente escriba

$$F_{2k}(-x) = F_{2k-1}(-x) - x F_{2k-2}(-x)$$ $$F_{2k-1}(-x) = F_{2k-2}(-x) - x F_{2k-3}(-x)$$ $$F_{2k-2}(-x) = F_{2k-3}(-x) - x F_{2k-4}(-x)$$

Escribiendo la tercera ecuación como $F_{2k-3}(-x) = F_{2k-2}(-x) + x F_{2k-4}(x)$ y sustituyendo dos veces para eliminar los términos impar se obtiene

$$F_{2k}(-x) = (1 - 2x) F_{2k-2}(-x) - x^2 F_{2k-4}(-x)$$

como desee.

Más abstractamente, $F_k(-x)$ satisface una relación de recurrencia con polinomio característico $\lambda^2 - \lambda + x$ por lo que puede expresarse como una suma de $k^{th}$ potencias de las dos raíces de este polinomio. Es decir $F_{2k}(-x)$ satisface una relación de recurrencia con polinomio característico el polinomio cuyas raíces son los cuadrados de $\lambda^2 - \lambda + x$ . En general, si $\lambda^2 - b \lambda + c$ tiene raíces $r, s$ el polinomio con raíces $r^2, s^2$ es $\lambda^2 - (b^2 - 2c) \lambda + c^2$ y aplicando esta transformación a $\lambda^2 - \lambda + x$ da $\lambda^2 - (1 - 2x) \lambda + x^2$ como se esperaba.