求矩阵的幂

aimisiyou

求\(A = \begin{pmatrix}
1&0&1  \\
1&0 &0\\
0 &1&0\\
\end{pmatrix}^{n},B = \begin{pmatrix}
1&0&0&1\\
1&0 &0&0\\
0 &1&0&0\\0&0&1&0
\end{pmatrix}^{n}\dots\)

hujunhua

记`A_1= \begin{pmatrix}
1&0&1  \\
1&0 &0\\
0 &1&0\\
\end{pmatrix}`,手工计算的话，可以将`A_1`分成两部分之和:`A_1=\omega+\alpha`,其中

`\omega= \begin{pmatrix}
0&0&1  \\
1&0 &0\\
0 &1&0\\
\end{pmatrix}`,`\alpha= \begin{pmatrix}
1&0&0  \\
0&0 &0\\
0 &0&0\\
\end{pmatrix}`
左乘`\omega`即行下移，右乘`\omega`为列左移。所以`\omega^3=E`(3阶单位矩阵)，还有以下几条可以辅助计算的性质：
1、`\alpha^k=\alpha`;
2、`\alpha\omega\alpha=0`, `\alpha\omega^2\alpha=0`;
3、`\D\{a_{ij}\}_{3\times3}=\sum_{i=0}^2\sum_{j=0}^2a_{ij}\omega^i\alpha\omega^{-j}`
设`A=A_1^n=\omega^n+\{a_{ij}(n)\}`, 可以得到一种递推公式`\{a_{ij}(n+3)\}=f(\{a_{ij}(n)\})`。

BeerRabbit

昨天看到这个问题，第一印象想到的是相似矩阵。
在这个问题里各个矩阵都是满秩的，而且特征值互异，所以就可以先找到由A的特征值构成的主对角矩阵Q，然后必然存在可逆矩阵P，使得A=PQP^(-1);
然后容易证明A^n=PQ^nP^(-1)，由于Q是对角矩阵，n次幂只要把主对角线上元素n次幂即可，剩下就没什么了。

wayne

用在线的Mathematica跑了下，Eigenvalues 分别是 $x^3-x^2-1,x^4-x^3-1$的根

zhouguang

BeerRabbit 发表于 2015-10-15 10:17
昨天看到这个问题，第一印象想到的是相似矩阵。
在这个问题里各个矩阵都是满秩的，而且特征值互异，所以就 ...

呵呵，剩下的还有一点点。
如wayne所说，3乘3的那个的本征方程是x^3-x^2-1==0，如果我们把方阵An硬看成“数”，那么，这些数是满足这个本征方程的呢。呵呵。
这有什么用呢？
An正中心的数构成的数列是0,0,1,1,1,2,3,4,6,9,13,...，满足x(k+3)=x(k+2)+x(k)，可以看出这个递推对应于那么本征方程么？当然，其他对应的“格”也是满足递推的。
所以说，将方阵、数列、函数啥啥的硬看成“数”，或许是有些许好处滴，呵呵。

kastin

利用2楼的分解可知（下列公式中的下标均表示方阵的阶数）
`A^n=A^{n-1}(\omega_3+\alpha_3)`，`B^n=B^{n-1}(\omega_4+\alpha_4)`
因为右乘 `\omega` 相当于列循环左移（即第一列变最后一列，其他各列依次往左移动），而右乘 `\alpha` 相当于取第一列，因此 `A^n` 相当于将 `A^{n-1}` 先进行列左移，然后将新的第一列加上原来的第一列。
于是根据初始值 `A` 就能递推得到 `A^n`，`B^n` 也是类似。

就以方阵 `A` 为例，
$$A = \begin{pmatrix}
1&0&1  \\
1&0 &0\\
0 &1&0\\
\end{pmatrix},A^2= \begin{pmatrix}
1+0&1&1  \\
1+0&0 &1\\
0+1 &0&0\\
\end{pmatrix}=\begin{pmatrix}
1&1&1  \\
1&0 &1\\
1 &0&0\\
\end{pmatrix},A^3=\begin{pmatrix}
1+1&1&1  \\
1+0&1 &1\\
1+0 &0&1\\
\end{pmatrix}=\begin{pmatrix}
2&1&1  \\
1&1 &1\\
1 &0&1\\
\end{pmatrix},\dots$$