矩阵乘法与其运用（logn递推）
规则：
1.当矩阵A的列数（column）等于矩阵B的行数（row）时，A与B可以相乘。
\[\left( \begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ \end{matrix} \right) * \begin{pmatrix} 1 & 2 \\ \end{pmatrix} \]如上图所示，A的行数等于B的列数
2.矩阵C的行数等于矩阵A的行数，C的列数等于B的列数。
3.乘积C的第m行第n列的元素等于矩阵A的第m行的元素与矩阵B的第n列对应元素乘积之和。
\[A=\begin{bmatrix} {a_{1,1}}&{a_{1,2}}&{a_{1,3}}\\ {a_{2,1}}&{a_{2,2}}&{a_{2,3}}\\ \end{bmatrix} \]\[B=\begin{bmatrix} {b_{1,1}}\\ {b_{2,1}}\\ {b_{3,1}}\\ \end{bmatrix} \]\[C=A*B= \begin{bmatrix} {a_{1,1}*b_{1,1}+a_{1,2}*b_{2,1}+a_{1,3}*b_{3,1}}\\ {a_{2,1}*b_{1,1}+a_{2,2}*b_{2,1}+a_{2,3}*b_{3,1}}\\ \end{bmatrix} \]有了矩阵我们可以干嘛呢？
不可以能出门买菜还要用矩阵吧
本人学识浅薄，目前只了解一些应用，浅谈一下
在O（logn）时间复杂度推递推式
我们以最简单的递推式斐波那契为例子
\[f[i]=f[i-1]+f[i-2] \]如果扩展一下
\[\begin{cases} \quad \text{f[i]=f[i-1]+f[i-2]} \\ \quad \text{f[i-1]=f[i-1]+0*f[i-2]}\\ \end{cases} \]为什么要这样扩展呢？
这样可以适配矩阵乘法
\[\begin{bmatrix} {f[i-1]}\\ {f[i-2]}\\ \end{bmatrix} * \begin{bmatrix} {1}&{1}\\ {1}&{0}\\ \end{bmatrix} = \begin{bmatrix} {1*f[i-1]+1*f[i-2]}\\ {1*f[i-1]+0*f[i-2]}\\ \end{bmatrix} = \begin{bmatrix} {f[i]}\\ {f[i-1]}\\ \end{bmatrix} \]这样就把递推变成矩阵乘法
为什么要这样变成矩阵呢，直接推不好吗，矩阵有什么好处呢？
我们可以很容易的发现之前是两个递推式中的数相加得到第3个
而矩阵中是递推矩阵中的一个乘上一个常量矩阵
在斐波那契中我们可以用下面的式子
\[\begin{bmatrix} {f[0]}\\ {f[1]}\\ \end{bmatrix} * \begin{bmatrix} {1}&{1}\\ {1}&{0}\\ \end{bmatrix}^n \]快速算出f[n]与f[n+1]
如何快速算常数矩阵
\[ \begin{bmatrix} {1}&{1}\\ {1}&{0}\\ \end{bmatrix}^n \]考虑快速幂O（logn）
完结撒花~~~~
标签：begin,end,矩阵,bmatrix,列数,递推,与其,乘法 From： https://www.cnblogs.com/hfjh/p/17035596.html