Matrix Exponentiation (Theory Parte 3)


  • administrators

    Ahora que ya vimos en acción este método, surge la pregunta, es posible obtener una matriz de recurrencia para cualquier formula encontrada ? La respuesta es si, dada una recurrencia que se pueda resolver utilizando programación dinámica es casi seguro que se puede implementar una solución con este método.

    Ahora veremos algunas recurrencias transformadas en matrices para el uso de este metodo.

    Problemas Tipo 2:

    Dado el problema hallamos la siguiente función de recurrencia $f(n) = a * f(n-1) + b * f(n-2)$ donde a y b son constantes.

    Como en el anterior caso construiremos las matrices.
    $$
    {\begin{bmatrix}
    ? & ?\\
    ? & ?
    \end{bmatrix}\atop M} \times {\begin{bmatrix}
    f(n-1)\\
    f(n-2)
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    f(n)\\
    f(n-1)
    \end{bmatrix}\atop B}
    $$
    Ahora necesitamos incluir en la matriz $M$ los valores $[a, b]$, en el anterior ejemplo pusimos [1, 1] pero ahora necesitamos $a$ veces $f(n-1)$ y $b$ veces $f(n-2)$ entonces agregando esto obtenemos:
    $$
    {\begin{bmatrix}
    a & b\\
    1 & 0
    \end{bmatrix}\atop M} \times {\begin{bmatrix}
    f(n-1)\\
    f(n-2)
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    f(n)\\
    f(n-1)
    \end{bmatrix}\atop B}
    $$

    Problemas Tipo 3:

    Dado el problema hallamos la siguiente función de recurrencia $f(n) = a * f(n-1) + b * f(n-3)$ donde a y b son constantes.

    Como en el anterior caso construiremos las matrices, pero esta vez tenemos 3 valores que guardar ya que algun momento necesitaremos usar el valor de $f(n-2)$ aunque no este incluido en la formula.
    $$
    {\begin{bmatrix}
    ? & ? & ?\\
    ? & ? & ?\\
    ? & ? & ?
    \end{bmatrix}\atop M} \times {\begin{bmatrix}
    f(n-1)\\
    f(n-2)\\
    f(n-3)
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    f(n)\\
    f(n-1)\\
    f(n-2)
    \end{bmatrix}\atop B}
    $$
    Ahora necesitamos incluir en la matriz $M$ los valores $[a, 0, c]$, esto multiplicado con el array A nos dará el correcto valor que buscamos para $f(n)$.
    $$
    {\begin{bmatrix}
    a & 0 & c\\
    . & . & .\\
    . & . & .
    \end{bmatrix}\atop M} \times {\begin{bmatrix}
    f(n-1)\\
    f(n-2)\\
    f(n-3)
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    f(n)\\
    .\\
    .
    \end{bmatrix}\atop B}
    $$
    Para ver mejor el panorama completo de la multiplicacion podemos ver de la siguiente forma:
    $$
    {\begin{bmatrix}
    a & 0 & c\\
    1 & 0 & 0\\
    0 & 1 & 0
    \end{bmatrix}\atop M} \times {\begin{bmatrix}
    f(n-1)\\
    f(n-2)\\
    f(n-3)
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    a * f(n-1) + 0 * f(n-2) + c * f(n-3)\\
    1 * f(n-1) + 0 * f(n-2) + 0 * f(n-3)\\
    0 * f(n-1) + 1 * f(n-2) + 0 * f(n-3)
    \end{bmatrix}\atop B}
    $$
    Como se puede ver la multiplicación nos da como resultado el valor que buscamos y como en los anteriores casos si estamos buscando el $n-esimo$ valor, solo necesitamos hallar la matriz $M^{n-3}$.

    Problemas Tipo 4:

    Para este tipo vemos un elemento extra $f(n) = f(n-1) + f(n-2) + c$ una constante en la formula!!. Como en los otros casos primero creamos las matrices A y B.
    $$
    {\begin{bmatrix}
    ? & ? & ?\\
    ? & ? & ?\\
    ? & ? & ?
    \end{bmatrix}\atop M} \times {\begin{bmatrix}
    f(n-1)\\
    f(n-2)\\
    c
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    f(n)\\
    f(n-1)\\
    c
    \end{bmatrix}\atop B}
    $$
    Como se puede apreciar no estamos alterando la constante $c$, para eso necesitamos que su valor en la Matriz M sea de 1.
    $$
    {\begin{bmatrix}
    1 & 1 & 1\\
    1 & 0 & 0\\
    0 & 0 & 1
    \end{bmatrix}\atop M} \times {\begin{bmatrix}
    f(n-1)\\
    f(n-2)\\
    c
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    f(n)\\
    f(n-1)\\
    c
    \end{bmatrix}\atop B}
    $$
    Podrás apreciar que no importa que valor tome la matriz $M^{n}$ siempre la constante $c$ multiplicada por la matriz se mantendrá en su valor inicial.

    Conclusion

    Este método nos ayuda a obtener rápidamente posiciones en una secuencia con ayuda de los valores iniciales.