循环矩阵的乘法-学习笔记
i207M
·
·
个人记录
定义
定义循环矩阵为：
\begin{pmatrix} a_{0} & a_{1} & a_{2} & \cdots & a_{n-1} \\ a_{n-1} & a_{0} & a_{1} & \cdots & a_{n-2} \\ a_{n-2} & a_{n-1} & a_{0} & \cdots & a_{n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{1} & a_{2} & a_{3}& \cdots & a_{0} \end{pmatrix}
换而言之，A_{i,j}=A_{0,(j-i) \bmod n}，也就是说可以用循环矩阵的第一行来表示整个矩阵
矩阵乘法 O(k^3)
根据矩阵乘法的定义，假设有 A,B 两个 n 阶矩阵，则 C = A \times B 为：
c_{i,j}=\sum_{k=0}^{n-1}a_{i,k}b_{k,j}
矩阵乘法 O(k^2)
考虑循环矩阵的特殊性，即可以用第一行来表示整个矩阵，也就是说这个矩阵的所有信息只存在于第一行中
那么考虑 n 阶矩阵 C=A \times B：
\begin{aligned}
c_{i,j}
&=\sum_{k=0}^{n-1}a_{i,k}b_{k,j} \\
&=\sum_{k=0}^{n-1}a_{0,(k-i) \bmod n}b_{0,(j-k) \bmod n} \\
&=c_{0,(j-i) \bmod n} \\
\end{aligned}
也就是说，循环矩阵的乘积依旧是循环矩阵
所以可以得知，循环矩阵的乘法实际上只有第一行参与了运算，那么就可以直接用 a_0,b_0,c_0 代替掉 A,B,C 了
于是可以得到：
c_{k}=\sum_{i+j \equiv k \pmod {n}}a_{i}b_{j}
矩阵乘法 O(k \log k)
实际上 C=A \times B 是一个循环卷积运算，直接求出 c'=a \times b，然后可以得到：
c_i=c'_i+c'_{i+n}
应用
给定一个序列 p_0 \sim p_{n-1}，以及一个系数系列 t_0 \sim t_{n-1}，一共进行 T 次变换，每一次会把 p 变化为 p'，其中 ：
p_i'=\sum_{j=0}^{n-1}t_{(j-i) \bmod n}p_j
是不是感觉有点眼熟？我们来看一下常系数齐次线性递推的一般形式：
p_i=\sum_{j=1}^{k}t_jp_{i-j}
没错，本质上是模意义下的常系数齐次线性递推！
构造矩阵 A：
A=
\begin{pmatrix}
p_0 & p_1 & \cdots & p_{n-1} \\
\end{pmatrix}
构造矩阵 B：
B=
\begin{pmatrix}
t_{0} & t_{n-1} & \cdots & t_{1} \\
t_{1} & t_{0} & \cdots & t_{2} \\
\vdots & \vdots & \ddots & \vdots \\
t_{n-1} & t_{n-2} & \cdots & t_{0} \\
\end{pmatrix}
那么矩阵 B 依然是一个循环矩阵，但是需要把 t_1 \sim t_{n-1} 翻转一下
之后可以得到矩阵 C=A \times B：
C=
\begin{pmatrix}
p'_0 & p'_1 & \cdots & p'_{n-1} \\
\end{pmatrix}
然而行矩阵乘以循环矩阵还需要再进行讨论，不妨直接把 A 扩充为循环矩阵，最后第一行的结果依旧是期望的结果：
A=
\begin{pmatrix}
p_0 & p_1 & \cdots & p_{n-1} \\
p_{n-1} & p_0 & \cdots & p_{n-2} \\
\vdots & \vdots & \ddots & \vdots \\
p_{1} & p_{2} & \cdots & p_{0} \\
\end{pmatrix}
即 C=A \times B 就是：
C=
\begin{pmatrix}
p'_0 & p'_1 & \cdots & p'_{n-1} \\
p'_{n-1} & p'_0 & \cdots & p'_{n-2} \\
\vdots & \vdots & \ddots & \vdots \\
p'_{1} & p'_{2} & \cdots & p'_{0} \\
\end{pmatrix}