数列最短线性递推式唯一性的充要条件

· · 算法·理论

先给出结论：线性递推数列的最短线性递推式唯一的充要条件是，最短线性递推式的长度不超过数列长度的 \frac12。

证明：

设数列为 a_0\sim a_{n-1}，最短线性递推式（之一）为 r_1\sim r_m，即：

\forall m\le i<n,a_i=\sum_{j=1}^ma_{i-j}r_j

上式可以看做 r_i 是一个有 m 个未知数、n-m 个方程的线性方程组的解。

必要性较为显然，若 m>\frac12n，则方程组的未知数数量大于方程数量，显然解不唯一。

下面证明充分性，即 m\le\frac12n 时 r_i 唯一。

考虑取出数列 a 的前 2m 项列出一个 m 元 m 个方程的线性方程组：

a_0r_m+a_1r_{m-1}+\cdots+a_{m-1}r_1=a_m\\ a_1r_m+a_2r_{m-1}+\cdots+a_{m}r_1=a_{m+1}\\ \vdots\\ a_{m-1}r_m+a_mr_{m-1}+\cdots+a_{2m-2}r_1=a_{2m-1}

考虑反证法，假设最短递推式不唯一，即这个方程组解不唯一。由于方程组的未知数数量和方程数量相等，所以它的行一定线性相关。设第 i 行乘上 k_i 后所有行加起来得到 \vec{0}，其中 k_i 非全 0。记 l 为最大的 i 满足 k_i\ne0，这意味着：

a_0k_1+a_1k_2+\cdots+a_{l-1}k_l=0\\ a_1k_1+a_2k_2+\cdots+a_lk_l=0\\ \vdots\\ a_mk_1+a_{m+1}k_2+\cdots+a_{m+l-1}k_l=0

也就是说，a_0\sim a_{m+l-1} 有一个长度为 l-1 的线性递推式为

-\frac{k_{l-1}}{k_l},-\frac{k_{l-2}}{k_l},\cdots,-\frac{k_1}{k_l}

采用与钟子谦 2019 年国家集训队论文中引理 1.1 的证明类似的方法可以证明，这个长度为 l-1 的线性递推式对整个 a 序列都成立。这与 r_1\sim r_m 是最短线性递推式矛盾。于是原命题得证。