「知识总结」特征多项式与线性递推【矩阵乘法】

特征多项式

定义

定义 n×nn \times n 的矩阵 AA 的特征多项式为:

p(λ)=det(λIA)=λn+g1λn1+g2λn2++gn\begin{aligned} p(\lambda) &= \det(\lambda I - A) \\ &= \lambda^n + g_1 \lambda^{n - 1} + g_2 \lambda^{n - 2} + \cdots + g_n \end{aligned}

其中 IIn×nn \times n 的单位矩阵,λ\lambda 可以为实数、向量或矩阵。

性质

根据 Cayley-Hamilton\text{Cayley-Hamilton} 定理,AA 满足:

p(A)=Op(A) = O

其中 OO 为零矩阵。则 k\forall k

Ak=Ak mod p(A)A^k = A^k \text{ mod } p(A)

上一步本质上将 AkA^k 表示为以 AA 为变量、次数小于 nn 的多项式。

示例

查看更多

「CTS 2019」随机立方体【容斥原理 + 概率与期望】

Time Limit: 12 Sec Memory Limit: 512 MB

Description

有一个 n×m×ln \times m \times l 的立方体,每个格子上都有一个数,如果某个格子上的数比三维坐标至少有一维相同的其他格子上的数都要大的话,我们就称它是极大的。

现在将 1n×m×l1 \sim n \times m \times ln×m×ln \times m \times l 个数等概率随机填入 n×m×ln \times m \times l 个格子,使得每个数均出现一次,求恰有 kk 个极大的数的概率。答案对 998244353998244353 取模。

查看更多