Matrix Exponentiation (Theory Parte 2)


  • administrators

    Nota: para esta sección dejar de lado soluciones con programación dinámica u otras formulas.

    Una vez comprendido cómo funciona la Exponenciación Binaria pasemos a revisar que sucede en el caso de tener más elementos involucrados en nuestra fórmula de recurrencia. Hagamos el caso más conocido de todos, la Sucesión de Fibonacci, conociendo su recurrencia sabemos que la sucesión está dada por la formula:

    $$
    \begin{equation*}
    Fibo_i=
    \begin{cases}
    1, & \text{si}\ N \text{ es menor o igual a 1}\ \\
    Fibo_{i-1} + Fibo_{i-2}, & \text{si}\ N \text{ es mayor que 1}
    \end{cases}
    \end{equation*}
    $$

    Como se puede apreciar no basta con el número anterior, ahora necesitamos 2 valores anteriores. Escribiendo la fórmula de forma simple sabemos que $f(n) = f(n-1) + f(n-2)$ y para los valores iniciales tenemos $[f(0), f(1)] = [1, 1]$.

    Para completar esta solución necesitaremos entender la representación de funciones en matrices. Ya que necesitamos una Matriz M que dando la Matriz A (la matriz que representa al estado inicial) logremos llegar a un estado n-esimo representado con la Matriz B, obteniendo $M \times A = B$.

    $$
    M \times \begin{bmatrix}
    g(n-1)\\
    g(n-2)
    \end{bmatrix} = \begin{bmatrix}
    f(n)\\
    f(n-1)
    \end{bmatrix}
    $$
    "las funciones $f$ y $g$ son las mismas solo están con diferente letra por motivo de mejor comprensión"

    Para hallar la matriz M necesitamos saber dos cosas, Multiplicación de Matrices y Las Formulas de La recursion.

    Multiplicación de Matrices de dos dimensiones.

    Para multiplicar dos matrices uno puede utilizar la siguiente formula (Se puede memorizar esta formula recordando multiplicar y sumar, filas por columnas):
    $$
    \begin{bmatrix}
    a & b\\
    c & d
    \end{bmatrix} \times \begin{bmatrix}
    e & f\\
    g & h
    \end{bmatrix} = \begin{bmatrix}
    ae+bg & af+bh\\
    ce+dg & cf+dh
    \end{bmatrix}
    $$
    o si es mas facil entender:
    $$
    \begin{bmatrix}
    A_{1,1} & A_{1,2}\\
    A_{2,1} & A_{2,2}
    \end{bmatrix} \times \begin{bmatrix}
    B_{1,1} & B_{1,2}\\
    B_{2,1} & B_{2,2}
    \end{bmatrix} = \begin{bmatrix}
    A_{1,1}B_{1,1}+A_{1,2}B_{2,2} & A_{1,1}B_{1,2}+A_{1,2}B_{2,2}\\
    A_{2,1}B_{1,1}+A_{2,2}B_{2,2} & A_{2,1}B_{1,2}+A_{2,2}B_{2,2}
    \end{bmatrix}
    $$
    Ahora una implementación para hallar esta multiplicación utilizando c++:

    vector<vector<double> > multiply(vector<vector<double> >& a, vector<vector<double> >& b) {
        vector<vector<double> > res(2, vector<double>(2));
        res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
        res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
        res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
        res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
        return res;
    }
    

    Formulas de La Recursion para las Matrices A y B

    $$
    \begin{align*}
    f(n) & = g(n-1) + g(n-2)\\
    f(n-1)& = g(n-1)
    \end{align*}
    $$

    Armando la solucion

    Una vez mas recordemos, estamos buscando una matriz $M$ de tal forma que $M \times A = B$. El valor de la matriz A sabemos que sera el valor inicial $[g(0), g(1)] = [1, 1]$.
    $$
    M \times \begin{bmatrix}
    g(n-1)\\
    g(n-2)
    \end{bmatrix} = \begin{bmatrix}
    f(n)\\
    f(n-1)
    \end{bmatrix}
    $$
    No tenemos que mezclar funciones la Matriz A representa un estado anterior o inicial. La Matriz B es el resultado y la Matriz M sale de nuestras "Formulas de La Recursion" de la siguiente forma.
    $$
    \begin{bmatrix}
    ? & ?\\
    ? & ?
    \end{bmatrix} \times \begin{bmatrix}
    f(n-1)\\
    f(n-2)
    \end{bmatrix} = \begin{bmatrix}
    f(n)\\
    f(n-1)
    \end{bmatrix}
    $$
    Aplicamos la primera formula $f(n) = f(n-1) + f(n-2)$ y necesitaremos los siguientes valores $[1, 1]$ para obtener $f(n) = f(n-1) * 1 + f(n-2) * 1$ de esta forma los aplicamos a nuestra matriz M:
    $$
    \begin{bmatrix}
    1 & 1\\
    . & .
    \end{bmatrix} \times \begin{bmatrix}
    f(n-1)\\
    f(n-2)
    \end{bmatrix} = \begin{bmatrix}
    f(n)\\
    .
    \end{bmatrix}
    $$

    Analicemos un poco el resultado de la multiplicación de la matriz M y la matriz A. Si aplicamos filas por columnas tendremos que $f(n) = 1 * f(n-1) + 1 * f(n-2)$ lo cual es correcto para la formula que acabamos de incluir a la matriz.

    Ahora aplicando la segunda formula $f(n-1) = f(n-1)$ tenemos:
    $$
    \begin{bmatrix}
    . & .\\
    1 & 0
    \end{bmatrix} \times \begin{bmatrix}
    f(n-1)\\
    f(n-2)
    \end{bmatrix} = \begin{bmatrix}
    .\\
    f(n-1)
    \end{bmatrix}
    $$
    Ahora una vez mas analicemos un poco el resultado de la multiplicación de la matriz $M$ y la matriz $A$. Si aplicamos filas por columnas tendremos que $f(n-1) = 1 * f(n-1) + 0 * f(n-2)$ que para la formula que aplicamos es perfecto y da como resultado una igualdad de la forma $f(n-1) = f(n-1)$.

    Entonces como resultado final tenemos lo siguiente:
    $$
    {\begin{bmatrix}
    1 & 1\\
    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}
    $$
    Que significa ? Bueno si utilizamos la matriz $M$ tal cual simplemente obtendremos el siguiente valor de la sucesion dado un $f(3)$ y un $f(4)$ tendremos un $f(5)$.

    Ejemplo

    $$
    \begin{bmatrix}
    1 & 1\\
    1 & 0
    \end{bmatrix} \times \begin{bmatrix}
    f(4)\\
    f(3)
    \end{bmatrix} = \begin{bmatrix}
    f(5)\\
    f(4)
    \end{bmatrix}
    $$
    Reemplazando la sucesion de Fibonacci ($1_0, 1_1, 2_2, 3_3, 5_4, 8_5$) los valores $f(3) = 3$ y $f(4) = 5$
    $$
    \begin{bmatrix}
    1 & 1\\
    1 & 0
    \end{bmatrix} \times \begin{bmatrix}
    5\\
    3
    \end{bmatrix} = \begin{bmatrix}
    1 * 5 + 1 * 3\\
    1 * 5 + 0 * 3
    \end{bmatrix} = \begin{bmatrix}
    8_5\\
    5_4
    \end{bmatrix} = \begin{bmatrix}
    f(5)\\
    f(4)
    \end{bmatrix}
    $$

    Exponenciando M

    Si exponenciamos la matriz M podremos obtener otros valores, tal cual vimos en la "Parte 1".

    La matriz M como vimos en la Parte 1 igual nos ayudara a obtener el valor N con ayuda de los valores iniciales.
    $$
    {\begin{bmatrix}
    1 & 1\\
    1 & 0
    \end{bmatrix}^{n-2}\atop M} \times
    {\begin{bmatrix}
    g(2)\\
    g(1)
    \end{bmatrix}\atop A} = {\begin{bmatrix}
    f(n)\\
    f(n-1)
    \end{bmatrix}\atop B}
    $$
    Pero ahora como hallamos la Matriz $M^{n-2}$ si "n" puede ser un valor muy grande ? esto es sencillo ya que conocemos "Exponenciación Binaria"!.

    A continuacion el codigo de la solucion para el problema de obtener el n-esimo valor de una Sucesión de Fibonacci.

    typedef long long   LL;
    const LL MOD = 1000000007LL;
    
    vector<vector<LL> > multiply(vector<vector<LL> >& a, vector<vector<LL> >& b) {
        vector<vector<LL> > res(2, vector<LL>(2));
        res[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
        res[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
        res[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
        res[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;
        return res;
    }
    
    vector<vector<LL> > getExpo(LL power) {
        vector<vector<LL> > matrix(2, vector<LL>(2, 0)), res;
        matrix[0][0] = 1;
        matrix[0][1] = 1;
        matrix[1][0] = 1;
        res = matrix;
        while (power > 0LL) {
            if (power & 1LL) {
                res = multiply(res, matrix);
            }
            matrix = multiply(matrix, matrix);
            power >>= 1;
        }
        return res;
    }
    
    void solve(LL N) {
        if (N <= 1LL) {
            cout << 1 << endl; // caso base
        }
        else {
        	vector<vector<LL> > res = getExpo(N-2);
            cout << 1LL * res[0][0] + 1LL * res[0][1] << endl;
        }
    }
    

    Conclusion

    Es posible encontrar soluciones a recurrencias de distinto tipo la parte complicada es armar la matriz M. Mas ejemplos veremos en la siguiente seccion (Parte 3).