秩为 k 的 Toeplitz 矩阵计数

[Day60] Distribution of Bordered Persymmetric Matrices in a Finite Field，阅读笔记。该篇论文解决了秩为 k 的 Toeplitz 矩阵的计数问题。

Toeplitz 矩阵简单来说就是每条主对角线上的元素都一样的矩阵。更正式来表述，对于一个有限域 $\mathbb{F}_q$ 上的一个数组 $(\alpha_{1 - m}, \ldots, \alpha_0, \alpha_{n - 1})$，它定义一个这样的 $m \times n$ Toeplitz 矩阵：

$M = (\alpha_{j - i})_{m \times n} = \begin{pmatrix} \alpha_0 & \alpha_1 & \cdots & \alpha_{n - 1} \\ \alpha_{-1} & \alpha_0 & \ddots & \vdots \\ \vdots & \ddots & \ddots & \vdots \\ \alpha_{1 - m} & \cdots & \cdots & \alpha_{n - m} \end{pmatrix}.$

如果单从我们关心的问题——秩为 $k$ 的 Toeplitz 矩阵计数——来看，将矩阵左右镜像一下也没有问题，这样我们就得到的了 Hankel 矩阵：对于数组 $(\alpha_1, \ldots, \alpha_{m + n - 1})$，有 Hankel 矩阵：

$M = (\alpha_{i + j - 1})_{m \times n} = \begin{pmatrix} \alpha_1 & \alpha_2 & \cdots & \alpha_n \\ \alpha_2 & \vdots & \vdots & \vdots \\ \vdots & \vdots & \vdots & \vdots \\ \alpha_m & \cdots & \cdots & \alpha_{m + n - 1} \end{pmatrix}.$

下面我们都用 Hankel 矩阵，因为关于 $\alpha$ 数组的形式更对称一点。

这篇文章的主要结果之一如下：

Theorem 1. 设 $f_q(m, n, k)$ 是 $\mathbb{F}_q$ 上 $m \times n$ Hankel 矩阵中秩为 $k$ 的矩阵数量，则其表达式如下：

$f_q(m, n, k) = \begin{cases} 1 & k = 0 \\ q^{2 (k - 1)} (q^2 - 1) & 1 \le k < \min\{m, n\} \\ q^{2 (k - 1)} (q^{|m - n| + 1} - 1) & k = \min\{m, n\} \\ 0 & \text{otherwise} \end{cases}.$

为证明此，我们关注一些子情况，定义这样一个量：对于一个 $m \times n$ Hankel 矩阵 $M$，$\Phi(M)$ 是最小的正整数 $u$ 满足 $\alpha_u \ne 0$；若这样的 $u$ 不存在，定义 $\Phi(M) = m + n$。

于是我们有如下引理：

Lemma 2. 设 $g_q(m, n, k, u)$ 是 $\mathbb{F}_q$ 上 $m \times n$ Hankel 矩阵中秩为 $k$ 且 $\Phi(M) = u$ 的矩阵数量，则其表达式如下：

$g_q(m, n, k) = \begin{cases} (q - 1) q^u f_q(m - u, n - u, k - u) & 1 \le u < \min\{m, n\} \\ (q - 1) q^{m + n - u - 1} & \min\{m, n\} \le u < \max\{m, n\}\text{ and }k = \min\{m, n\} \\ (q - 1) q^{m + n - u - 1} & \max\{m, n\} \le u < m + n\text{ and }k = m + n - u \\ 1 & u = m + n\text{ and }k = 0 \\ 0 & \text{otherwise} \end{cases}.$

可以发现，除了第一条 $1 \le u < \min\{m, n\}$，剩下几条都是简单的。这里以第二条 $\min\{m, n\} \le u < \max\{m, n\}$ 为例。不妨设 $m \ge n$，则这时候相当于 $\alpha_u \ne 0$ 占满了所有列，所以 $M$ 肯定是满秩的。而在 $\alpha_u$ 之下的元素怎么选都不影响，所以 $\alpha_u$ 有 $q - 1$ 中选择，剩下的均有 $q$，乘起来是 $(q - 1) q^{m + n - u - 1}$。

我们接下来都只考虑 $1 \le u < \min\{m, n\}$ 的情况，下面我们进行一些矩阵操作，使得我们可以列出 $f_q, g_q$ 的递推式。

Lemma 3. 设 $m \times n$ 的 Hankel 矩阵 $M$ 满足 $u = \Phi(M) < \min\{m, n\}$。则先定义序列 $\theta_1, \ldots, \theta_{m + n - u}$，满足如下条件：

$\begin{cases} \alpha_u \theta_1 = 1 \\ \alpha_u \theta_t + \alpha_{u + 1} \theta_{t - 1} + \cdots + \alpha_{u + t - 1} \theta_1 = 0,\ \forall 2 \le t \le m + n - u \end{cases} \tag{1}.$

那么我们就有：

$L M R = \begin{pmatrix} X & 0 \\ 0 & -Y \end{pmatrix} \tag{2},$

其中：

$L = \begin{pmatrix} \theta_1 & & & \\ \theta_2 & \theta_1 & & \\ \vdots & \ddots & \ddots & \\ \theta_m & \cdots & \theta_2 & \theta_1 \end{pmatrix}, R = \begin{pmatrix} \theta_1 & \theta_2 & \cdots & \theta_n \\ & \ddots & \ddots & \vdots \\ & & \theta_1 & \theta_2 \\ & & & \theta_1 \end{pmatrix}, \\ X = \begin{pmatrix} & & & \theta_1 \\ & & \theta_1 & \theta_2 \\ & \vdots & \vdots & \vdots \\ \theta_1 & \theta_2 & \cdots & \theta_u \end{pmatrix}, Y = \begin{pmatrix} \theta_{u + 1} & \theta_{u + 2} & \cdots & \theta_{n + 1} \\ \theta_{u + 2} & \theta_{u + 3} & \cdots & \theta_{n + 2} \\ \vdots & \vdots & \vdots & \theta_{m + n - u - 1} \\ \theta_{m + 1} & \cdots & \theta_{m + n - u - 1} & \theta_{m + n - u} \end{pmatrix}$

（$L, R$ 分别是上下三角矩阵，$X, Y$ 都是 Hankel 矩阵）。

该引理帮助我们构建 $f_q, g_q$ 之间的递推关系，其证明是一个略显繁琐的计算过程，此处略过。

Proof of Lemma 2. 同前所述，我们只需要考虑 $1 \le u < \min\{m, n\}$ 的情况，剩下的都是简单的。

对于一个满足 $\Phi(M) = u < \min\{m, n\}$ 的 $m \times n$ Hankel 矩阵，我们发现上面 Lemma 3 中的 $X, Y$ 已经包含了 $(\theta_1, \ldots, \theta_{m + n - u})$ 中除 $\theta_{u + 1}$ 的所有数。而再根据 $(1), (2)$，$(\theta_1, \ldots, \theta_{m + n - u})$ 就已经可以决定一个 $M$，而且不同的 $\theta_*$ 显然给出不同的 $M$。于是乎 $\{X, \theta_{u + 1}, Y\}$ 这样一个三元组就决定了 $M$，我们只需要计数这样三元组的个数。

首先由 $(1)$ 中的第一条可知 $\theta_1 \ne 0$，于是 $L, R, X$ 全部满秩，进而：

$k = \text{rank}(M) = \text{rank}(L M R) = \text{rank} \begin{pmatrix} X & 0 \\ 0 & -Y \end{pmatrix} = \text{rank}(X) + \text{rank}(Y) = u + \text{rank}(Y).$

这样我们就得出 $Y$ 是一个秩为 $k - u$ 的 $(m - u) \times (n - u)$ Hankel 矩阵。

最后，由简单的乘法原理，$\{X, \theta_{u + 1}, Y\}$ 的个数为：

$g_q(m, n, k, u) = (q - 1) q^{u - 1} \cdot q \cdot f_q(m - u, n - u, k - u) = (q - 1) q^u f_q(m - u, n - u, k - u),$

即得。$\Box$

Proof of Theorem 1. 第一条和第四条都是简单的，我们关注剩下的。首先有：

$f_q(m, n, k) = \sum_{u = 1}^{m + n} g_q(m, n, k, u).$

(a) 若 $1 \le k < \min\{m, n\}$，则 Lemma 2 告诉我们：

$f_q(m, n, k) = \sum_{u = 1}^k (q - 1) q^u f_q(m - u, n - u, k - u) + (q - 1) q^{k - 1}.$

当 $k = 1$ 时 $f_q(m, n, k) = q^2 - 1$ 正确。剩下的用归纳法，假设对所有更小的 $m, n, k$ 都成立，则：

$f_q(m, n, k) = \sum_{u = 1}^{k - 1} (q - 1) q^u q^{2 (k - u - 1)} (q^2 - 1) + (q - 1) (q^k + q^{k - 1}) = q^{2 (k - 1)} (q^2 - 1).$

(b) 当 $k = \min\{m, n\}$ 时，假设 $m \le n$，则 $k = m$。当 $k = 1$ 时显然 $f_q(1, n, 1) = q^n - 1$ 满足。当 $k > 1$ 时，再次用归纳法，由 Lemma 2 可得：

$\begin{aligned} f_q(k, n, k) & = \sum_{u = 1}^{m + n} g_q(m, n, k, u) \\ & = \sum_{u = 1}^{k - 1} (q - 1) q^u f_q(k - u, n - u, k - u) + \sum_{u = k}^n (q - 1) q^{k + n - u - 1} \\ & = \sum_{u = 1}^{k - 1} (q - 1) q^u \cdot q^{2 (k - u - 1)} (q^{n - k + 1} - 1) + q^n - q^{k - 1} \\ & = (q^{n - k - 1} - 1) q^{2 (k - 1)} = q^{2 (k - 1)} (q^{|k - n| + 1} - 1). \end{aligned}$

$\Box$

该篇文章还进一步探讨了 $\Psi(M) = v$ 的特定秩的 Hankel 矩阵数量，其中 $\Psi(M)$ 是最大的可逆顺序主子式的阶。此处不展开，读者有兴趣可参见原论文。

参考文献

[Day60] David E. Daykin. Distribution of bordered persymmetric matrices in a finite field. In J. reine u. angew. Math. 203, pp. 47-54, 1960.