月度归档:2018年01月

同伴矩阵的方幂

最近在研究一个矩阵的方幂,这个矩阵如下

    \[A=\left( \begin{array}{ccc}  0 & 0 & -a_0 \\  1 & 0 & -a_1 \\  0 & 1 & -a_2 \\ \end{array} \right).\]

事实上这个矩阵和下面这个多项式存在一一对应的关系,

    \[f(x)=x^3+a_2x^2+a_1x+a_0.\]

使用Mathematica计算A^k, 代码如下:
<< FiniteFields` Assuming[Element[p, Primes] && Element[n, Integers] && n > 0,
F = GF[p, n];
A = {{0, 0, -a[0]}, {1, 0, -a[1]}, {0, 1, -a[2]}};
Print[MatrixForm[
Simplify[MatrixPower[A, k],
Element[a[0], F] && Element[a[1], F] && Element[a[2], F] &&
Element[k, Integers] && k > 1]]];
];

计算结果为:

    \[\left( \begin{array}{ccc}  \frac{x_2 x_3 x_1^k}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\left(\frac{x_3 x_2^k}{x_2^2-a_1+2 x_1 x_3}+\frac{x_3^k x_2}{\left(x_1-x_3\right) \left(x_2-x_3\right)}\right) x_1 & a_0 \left(\frac{x_2^k}{-x_2^2+a_1-2 x_1 x_3}+\frac{\frac{x_3^k}{x_3-x_2}-\frac{x_1^k}{x_1-x_2}}{x_1-x_3}\right) & a_0 \left(\frac{\left(a_2+x_2+x_3\right) x_1^k}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+1}}{\left(x_1-x_3\right) \left(x_3-x_2\right)}+\frac{x_2^{k+1}}{-x_2^2+a_1-2 x_1 x_3}\right) \\  \frac{x_1 x_2 x_3 \left(-\frac{\left(a_2+x_1\right) x_1^k}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^k \left(a_2+x_3\right)}{\left(x_1-x_3\right) \left(x_3-x_2\right)}+\frac{x_2^k \left(a_2+x_2\right)}{-x_2^2+a_1-2 x_1 x_3}\right)}{a_0} & \frac{\left(a_2+x_1\right) x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+1} \left(a_2+x_3\right)}{\left(x_3-x_1\right) \left(x_3-x_2\right)}+\frac{x_2^{k+1} \left(a_2+x_2\right)}{x_2^2-a_1+2 x_1 x_3} & -\frac{\left(a_2+x_1\right) \left(a_2+x_2+x_3\right) x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+2} \left(a_2+x_3\right)}{\left(x_1-x_3\right) \left(x_2-x_3\right)}+\frac{x_2^{k+2} \left(a_2+x_2\right)}{x_2^2-a_1+2 x_1 x_3} \\  \frac{-x_1 x_3 \left(x_1^k+x_2^k-2 x_3^k\right) x_2^2+x_1 x_3^2 \left(x_1^k-2 x_2^k+x_3^k\right) x_2+a_0 a_2 \left(x_2^k-x_3^k\right)}{a_0 \left(x_1-x_2\right) \left(x_1-x_3\right) \left(x_2-x_3\right)} & \frac{x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+1}}{\left(x_3-x_1\right) \left(x_3-x_2\right)}+\frac{x_2^{k+1}}{x_2^2-a_1+2 x_1 x_3} & -\frac{\left(a_2+x_2+x_3\right) x_1^{k+1}}{\left(x_1-x_2\right) \left(x_1-x_3\right)}+\frac{x_3^{k+2}}{\left(x_1-x_3\right) \left(x_2-x_3\right)}+\frac{x_2^{k+2}}{x_2^2-a_1+2 x_1 x_3} \\ \end{array} \right).\]

显然在化简方面,Mathematica并没有充分利用a_0,a_1,a_2是有限域上的元素的特点,所以这个表达式还是挺复杂的,需要自己进一步做化简. 最终的目标是为了计算det(A^k-I).

突然灵机一动, 改动了一下Mathematica的代码如下:
<< FiniteFields` Assuming[Element[p, Primes] && Element[n, Integers] && n > 0,
F = GF[p, n];
A = {{0, 0, -a[0]}, {1, 0, -a[1]}, {0, 1, -a[2]}};
Print[MatrixForm[
Simplify[Det[MatrixPower[A, k] - IdentityMatrix[3]],
Element[a[0], F] && Element[a[1], F] && Element[a[2], F] &&
Element[k, Integers] && k > 1]]];
];

结果为:

    \[det(A^k-I)=(-1+x_1^k) (-1+x_2^k) (-1+x_3^k),\]

其中x_1,x_2,x_3是方程f(x)的三个根.