矩阵快速幂运用

引入

想要了解矩阵快速幂，就不得不提到矩阵的概念。矩阵就像一个二维数组，存储了一组数据，如：

$M=\left[ \begin{matrix} 1&2&3\\ 4&5&6\\ 7&8&9\end{matrix} \right]$

用 $M_{ij}$ 表示矩阵第 $i$ 行第 $j$ 列的数据，如 $M_{23}=6$。

矩阵运算

加法

矩阵的加法和实数加法类似，要求运算的两个矩阵大小相等，将对应位置相加即可。

减法

与加法相同，对应位置相减即可。

乘法

矩阵乘法并非对应位置相乘。

若矩阵 $A\times B=C$ 有意义，那么 $A$ 的列数要求与 $B$ 的行数相等。

若 $A$ 的列数与 $B$ 的行数等于 $n$：

$C_{ij}=\sum_{k=1}^{n}A_{ik}\times B_{kj}$

即结果第 $i$ 行第 $j$ 列的值为 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列的对应项相乘后求和。

一个很直观的理解是，把 矩阵放在结果的左侧， 矩阵放在结果的下方，将行与列延长，对应相乘后结果写在交点处。

$\left[ \begin{matrix} \bold{1}&\bold{2}&\bold{3}\\ 4&5&6\\ 7&8&9\end{matrix} \right]\left[ \begin{matrix} \rightarrow&36&&\\ &\uparrow&&\\ &\uparrow&&\end{matrix} \right]\\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \left[ \begin{matrix} 1&\bold{2}&3\\ 4&\bold{5}&6\\ 7&\bold{8}&9\end{matrix} \right]$