等比矩阵求和的另一种思路

引言

当我们对一个矩阵进行快速幂时，我们可能需要对矩阵的某一行进行求和，即计算矩阵 \(A\) \(A^1 + A^2 + A^3 + A^4 + A^5 + \ldots + A^n\) 中的第一行的和。

如何解决？

考虑对矩阵右侧加一行 \(1\) 例如，假设原矩阵是 \[ \begin{bmatrix} a_1&a_2\\ a_3&a_4\\ \end{bmatrix} \] 对于矩阵转换后，我们有: \[ \begin{bmatrix} a_1&a_2&1\\ a_3&a_4&1\\ 0&0&1\\ \end{bmatrix} \] 考虑对这个矩阵进行乘方 矩阵的二次幂为 \[ \begin{bmatrix} a_1^2+a_2a_3+0&a_1a_2+a_2a_4+0&a_1+a_2+1\\ a_1a_3+a_3a_4+0&a_2a_3+a_4^2+0&a_3+a_4+1\\ 0+0+0&0+0+0&0+0+1\\ \end{bmatrix} \] 首先我们可以观察到 右侧增加的一行1对矩阵的本身乘方无影响 其次，考虑右侧的一列的数值，可发现其数值等于第一行的 \(1\) 次方的和。 由矩阵乘法的性质： 最右一列的值在数值上等于对应列的第一个元素+对应列的第二个元素+对应列的第三个元素+...+1

考虑再乘一次转换后的矩阵，我们可以得到一个喜闻乐见的性质： 最右一列的数值，等于该矩阵的一次方的对应行的和 + 该矩阵二次方的对应行的和 + 1

至此，我们的问题已经解决，最后某一行的和，就等于对应行的和减去 \(1\)

为什么这样做是正确的

首先，我们在末尾一行补了 \(0\) ，这样便不会影响到原矩阵的乘法(即最后的一项始终是 \(0\))

其次，最后一行的值在矩阵乘法中不会发生变化，该为 \(0\) 的始终为 \(0\) ，为 \(1\) 的始终为 \(1\)

最后，我们考虑最后一列的值，以第一行举例： 在第一次乘方后，数值上等于 第一行矩阵各元素的和 + 1 第二次乘方前，由于第一行除了最后一列外所有的元素均为原本矩阵二次幂后的值，因此最后一列数值上等于 原本矩阵第一行二次幂后的值 + 原本矩阵一次幂后的值 + 1. 此时考虑原矩阵，最后一列的值已经不是 \(1\) 而是一次幂元素的和 + 1，因此 \(1\) 不会被重复累计。

这样乘下去，最终第一行前 \(n\) 次幂的和会等于矩阵第一行的和 - 1