¿Es posible calcular los factoriales convirtiéndolos en multiplicaciones de matrices?

Question

Un $n$ -de la secuencia de Fibonacci puede calcularse mediante un bonito truco que consiste en convertir la relación de recurrencia en una forma de matriz . A continuación, calculamos $M^n$ en $O(\log n)$ pasos utilizando exponenciación al cuadrado .

¿Sería posible utilizar este truco para calcular factoriales? Si no es así, ¿se puede demostrar? He descubierto cómo calcular cualquier polinomio en $n$ utilizando este enfoque, pero para los factoriales no pude expresar la relación de recurrencia del factorial como una transformación lineal.

Answer 1

La relación de recurrencia de Fibonacci:

$$F_{n+1} = F_n + F_{n-1}$$

es lineal. Con esto quiero decir que da el siguiente término como una combinación lineal de los términos anteriores. Otras recurrencias que tienen esta característica son:

$$A_{n+1} = 3A_n + A_{n-1}$$ $$B_{n+1} = -4B_n$$ $$C_{n+1} = C_n + C_{n-1} + C_{n-2}$$

por lo que cualquiera de ellos podría ser representado por matrices. ¡Aquí están!

$$ \begin{aligned} M_A &= \begin{bmatrix}3 & 1\\1& 0\end{bmatrix}\\ M_B &= \begin{bmatrix}-4\end{bmatrix} \end{aligned} $$

Y el último es un reto para el lector.

La matriz de Fibonacci

$$\begin{bmatrix}1&1\\0&1\end{bmatrix}$$

mapea un vector

$$\begin{bmatrix}F_n\\F_{n-1}\end{bmatrix} \rightarrow \begin{bmatrix}F_{n+1}\\F_n\end{bmatrix}$$

y estos funcionan de forma análoga.

Pero la relación de recurrencia factorial:

$$n! = n(n-1!)$$

no es una combinación lineal (con coeficientes constantes) de los argumentos anteriores, por lo que no podemos representarla como una matriz. Es decir, no podemos representarla mediante la mismo matriz, no importa lo que $n$ que estamos tratando de calcular. Cuando los coeficientes son constantes, podemos, lo que nos permite hacer la exponenciación al cuadrado, etc.

Las matrices son una forma cómoda de representar lineal sobre vectores. (No son sólo una abreviatura, pero a menudo me resulta útil pensar en ellas de esta manera).

Answer 2

Probablemente no sea la respuesta que busca, pero puede ser interesante.

Dejemos que $D_k$ sea el $k \times k$ con ceros en todas partes excepto en la superdiagonal, donde tiene los valores $1, 2, \dots, k - 1$ . Entonces el factorial $(k-1)!$ es igual al primer elemento del vector $$D_k^{k-1} e_k$$ donde $e_k$ es el vector unitario con un uno en la posición $k$ . De forma equivalente, el elemento en la posición $(1,k)$ en $D_k^{k-1}$ es $(k-1)!$ .

Ejemplo

$$D_5 = \left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 4 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right)$$ $$D_5^4 = \left( \begin{array}{ccccc} 0 & 0 & 0 & 0 & 24 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right)$$

Explicación

La matriz $D_k$ actúa sobre el espacio de polinomios de grado $\leq k$ como diferenciación. Entonces se puede utilizar la siguiente caracterización del factorial: $$n!= \frac{d^n}{dx^n} x^n$$ y obtener el resultado anterior.

Observaciones

La matriz $D_k$ también puede utilizarse para generar un triángulo superior Matriz de Pascal $U_k$ a través de $U_k = e^{D_k}$ utilizando el matriz exponencial .

Una mirada más cercana a $D_k$

Cuando se pone $D_k$ en Forma normal de Jordania . Por ejemplo, con $D_5$ arriba se obtiene $D_5 = S^{-1}JS$ :

$$D_5 = \underbrace{\left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 6 & 0 \\ 0 & 0 & 0 & 0 & 24 \end{array} \right)}_{=S^{-1}} \underbrace{\left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right)}_{=J} \underbrace{ \left( \begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{6} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{24} \end{array} \right)}_{=S} $$ donde $J$ es un gran bloque de Jordania (lo que no es sorprendente ya que $D_k$ es nilpotente), y $S^{-1}$ ¡es una matriz diagonal con factoriales en la diagonal!

Investigando un poco más se descubre que no es tan extraño. $D_k$ sólo tiene un valor propio, 0, con multiplicidad algebraica $k$ y multiplicidad geométrica 1. El vector propio perteneciente a este valor propio es $e_1$ .

Cuando ponemos algo en la forma normal de Jordan, utilizamos vectores propios generalizados, que son vectores $v$ que satisfagan $(D_k - \lambda I)^n v = 0$ para algunos $k$ . En nuestro caso $\lambda = 0$ Así que sólo miramos $D_k^n v = 0$ . Esto nos da que $e_k$ es un vector propio generalizado. ¿Recuerdas nuestra formulación original? $$D_k^{k-1}e_k = (k-1)! e_1$$ lo que explica por qué tenemos factoriales en $S^{-1}$ .