循环矩阵的探讨

KCF 中的循环矩阵在学习KCF ⽬标跟踪算法时，会⽤到⼀个数学概念：循环矩阵，其对KCF 的速度提升起到了⾮常关键的作⽤，值得了解下。

1. 傅⾥叶矩阵(DFT Matrix)　在了解循环矩阵的定义前，需要先了解下离散傅⾥叶矩阵：2. 循环矩阵定义形状如下的矩阵X 称为循环矩阵，x 为循环矩阵X 的⽣成向量，为矩阵第⼀⾏, 其他⾏都是x 向右循环位移得到。

X =C (x )=x 1x 2x 3x 4x 4x 1x 2x 3x 3x 4x 1x 2x 2x 3x 4x 1通过x ⽣成X , 可以由排列矩阵和x 相乘，连续平移x 得到，⽰例代码如下：import numpy as npx = np.array([[1, 2, 3, 4]])P = np.array([[0, 0, 0, 1],[1, 0, 0, 0],[0, 1, 0, 0],[0, 0, 1, 0]])X = np.zeros((4, 4))X[0, :] = xfor i in range(1, 4):X[i, :] = np.dot(P, X[i-1, :]).T # 排列矩阵P 每作⽤⼀次x ，x 向右移动⼀位print(X)输出：[[1. 2. 3. 4.][4. 1. 2. 3.][3. 4. 1. 2.][2. 3. 4. 1.]][]3. 循环矩阵性质循环矩阵很多优秀的性质，其中最重要的⼏个性质为如下：1. 任意循环矩阵可以被傅⾥叶变换矩阵对⾓化⼀般⽤如下⽅式表达这⼀概念：X=C(x)=F⋅diag(ˆx)⋅F H其中X是⼀个循环矩阵，x是X的⽣成向量, ˆx（读作x hat）为原向量x的傅⾥叶变换；F是傅⾥叶变换矩阵，F H表⽰共轭转置: F H=(F∗)T。

换句话说，X 相似于对⾓阵，X的特征值是ˆx的元素。

另⼀⽅⾯，如果⼀个矩阵能够表⽰成两个傅⾥叶矩阵夹⼀个对⾓阵的乘积形式，则它是⼀个循环矩阵。

其⽣成向量是对⾓元素的傅⾥叶逆变换：F⋅diag(y)⋅F H=C(−1(y))，（−1(y)表⽰y的傅⾥叶逆变换）2. 循环矩阵乘向量等价于⽣成向量的逆序和该向量卷积数学表⽰如下：(Xy)=(C(x)y)=(¯x∗y)=∗(x)⊙(y)这⾥¯x表⽰x的逆序排列，∗表⽰卷积。

浅谈循环矩阵的乘法和快速幂前⾔前置技能：矩阵乘法，矩阵快速幂当然你不会的话也不会点进来（滑稽）今天上午的$HNOI$模拟赛中，$T1$是这么⼀道题⽬：有⼀个长度为$n$的环，执⾏$s$次操作，在⼀次操作中，对于每⼀个数，它变为它左边的数乘上$l$以及它本⾝以及它右边的数乘上$r$的和。

求最后每⼀个位置上的数是多少。

(计算时左边和右边的数都是上⼀次的数)最后结果模上$10^x$，$l,r,x$都为给定的常数$n\leq1000,s\leq2^{30}$很容易想到⽤矩阵快速幂来维护，假设我们现在有$4$个数字需要变换，设$f[i][j]$表⽰当前已经变换了$i$次，第$j$位上的数字是多少，有递推式：$$\begin{aligned}&\begin{bmatrix}f[i-1][1]&f[i-1][2]&f[i-1][3]&f[i-1][4]\end{bmatrix}\times\begin{bmatrix}1&l&0&r\r&1&l&0\0&r&1&l\l&0&r&1\end{bmatrix}\=&\begin{bmatrix}f[i][1]&f[i][2]&f[i][3]&f[i][4]\end{bmatrix}\end{aligned}$$但是这样⼦做是$O(n^3log_2s)$，妥妥的超时（在没有$O(wys)$优化的情况下）这时我们发现，转置矩阵是⼀个循环矩阵。

循环矩阵是什么？下⾯内容引⾃百度百科，侵删在线性代数中，循环矩阵是⼀种特殊形式的$Toeplitz$矩阵，它的⾏向量的每个元素都是前⼀个⾏向量各元素依次右移⼀个位置得到的结果。

简单地说，就是以⼀⾏不断向前/后变换的形式出现。

循环矩阵有⼀些性质假设矩阵$a,b$都是循环矩阵，那么：1. $a+b$是⼀个循环矩阵2. $a\times b$是⼀个循环矩阵循环矩阵的矩阵快速幂根据性质$2$，那么这个转置矩阵⽆论⾃乘多少次，它还是⼀个循环矩阵，所以说，我们理论上只要知道第⼀⾏的最终形态，就可以知道整个矩阵了。

循环矩阵的特征向量
循环矩阵是指将矩阵的最后一列移到第一列，其余列依次向后移动一列所得到的矩阵。

循环矩阵在通信、图像处理等领域有着广泛的应用。

对于循环矩阵，其特征向量的求解是一个重要的问题。

以3阶循环矩阵为例，其矩阵形式为：
```
A = [a0 a1 a2
a2 a0 a1
a1 a2 a0]
```
我们可以通过猜测得到该矩阵的一个特征向量:
```
v = [1 e e^2]
```
其中e为一个复数。

将其带入矩阵特征值的定义式：
```
Av = λv
```
化简得到：
```
a0 + a1e + a2e^2 = λ
a0 + a1e^2 + a2e = λ
a0e^2 + a1e + a2 = λ
```
将前两个式子相减，得到：
```
(a1 - a2)e(e - 1) = 0
```
由于e不能为0或1，因此我们可以得到：
```
e = (-a1 ± sqrt(a1^2 - 4a0a2)) / 2a2
```
代入第三个式子，可以得到特征值为：
```
λ = a0 + a1e + a2e^2
```
以上就是求解循环矩阵特征向量的基本方法。

对于任意阶循环矩阵，其特征向量的求解可以采用类似的方式，具体细节可以参考相关文献和教材。

循环矩阵的性质及其应⽤\S 1循环矩阵的定义及多项式表⽰设\mathbb{K}为数域. 任取\mathbb{K}中n个数a_1,a_2,\cdots,a_n,下列矩阵称为\mathbb{K}上的n阶循环矩阵:A=\begin{pmatrix} a_1 & a_2 & a_3 & \cdots & a_n \\ a_n & a_1 & a_2 & \cdots & a_{n-1} \\ a_{n-1} & a_n & a_1 & \cdots & a_{n-2} \\ \vdots & \vdots & \vdots & & \vdots \\ a_2 & a_3 & a_4 & \cdots & a_1 \\ \end{pmatrix}.\quad(1)取a_2=1, a_1=a_3=\cdots=a_n=0, 则可得到如下基础循环矩阵:J=\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ 1 & 0 & 0 & \cdots & 0 \\ \end{pmatrix}.\quad(2)由复旦⾼代⽩⽪书的例 2.1 可知, J^k=\begin{pmatrix} 0 & I_{n-k} \\ I_k & 0 \\ \end{pmatrix}\,(1\leq k\leq n), 从⽽A=a_1I_n+a_2J+a_3J^2+\cdots+a_nJ^{n-1}.\quad(3)令g(x)=a_1+a_2x+a_3x^2+\cdots+a_nx^{n-1}, 则g(x)是\mathbb{K}上次数不超过n-1的多项式, 使得A=g(J), 这就是循环矩阵关于基础循环矩阵的多项式表⽰.记C_n(\mathbb{K})为\mathbb{K}上所有n阶循环矩阵构成的集合, 容易验证: 在矩阵的加法和数乘下, C_n(\mathbb{K})是⼀个n维线性空间, 它的⼀组基为\{I_n,J,\cdots,J^{n-1}\}. 再任取循环矩阵B=h(J), 其中h(x)是\mathbb{K}上次数不超过n-1的多项式, 则利⽤多项式乘法和J^n=I_n可知AB=g(J)h(J)仍然是⼀个循环矩阵 (参考⾼代⽩⽪书的例 2.12). 因此, C_n(\mathbb{K})是\mathbb{K}上的n维交换代数, 同构于\mathbb{K}[x]/(x^n-1).\S 2循环矩阵的性质下⾯将依次研究循环矩阵的特征值、特征向量和可对⾓化等性质, 由此可得循环矩阵的⾏列式、秩和⾮异性等信息. 这些内容包含在⾼代⽩⽪书的例 2.52, 例 6.9, 例 6.32 和例 6.39 的推论中.容易计算出基础循环矩阵J的特征多项式|\lambda I_n-J|=\lambda^n-1, 从⽽J在复数域中有n个不同的特征值, 即n次单位根\omega_k=\cos\dfrac{2k\pi}{n}+i\sin\dfrac{2k\pi}{n}\,(0\leq k\leq n-1), 因此J在复数域上可对⾓化. 经计算可知, 特征值\omega_k的特征向量是\alpha_k=(1,\omega_k,\omega_k^2,\cdots,\omega_k^{n-1})'. 将这些特征向量按列分块拼成⼀个矩阵: P=\begin{pmatrix} 1 & 1 & 1 &\cdots & 1 \\ 1 & \omega_1 & \omega_2 & \cdots & \omega_{n-1} \\ 1 & \omega_1^2 & \omega_2^2 & \cdots & \omega_{n-1}^2 \\ \vdots &\vdots & \vdots & & \vdots \\ 1 & \omega_1^{n-1} & \omega_2^{n-1} & \cdots & \omega_{n-1}^{n-1} \\ \end{pmatrix},\quad(4)则由Vandermonde ⾏列式或特征值特征向量的性质可知, P是⾮异阵, 并且满⾜P^{-1}JP=\mathrm{diag}\{1,\omega_1,\omega_2,\cdots,\omega_{n-1}\},\quad(5)从⽽P^{-1}AP=P^{-1}g(J)P=g(P^{-1}JP)=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}.\quad(6)由 (6) 式可知循环矩阵A=g(J)具有如下基本性质:(P1) A的特征值为g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1}), 对应的特征向量是\alpha_0,\alpha_1,\alpha_2,\cdots,\alpha_{n-1};(P2) |A|=g(1)g(\omega_1)g(\omega_2)\cdots g(\omega_{n-1});(P3) 循环矩阵A可对⾓化;(P4) r(A)=\sharp\{0\leq k\leq n-1\mid g(\omega_k)\neq 0\};(P5) A⾮异当且仅当g(\omega_k)\neq 0\,(0\leq k\leq n-1), 也即当且仅当(\lambda^n-1,g(\lambda))=1.定理 1 n阶复循环矩阵全体C_n(\mathbb{C})与n阶复对⾓矩阵全体D_n(\mathbb{C})之间存在⼀个⾃然的代数同构\xi.证明n阶复对⾓矩阵全体在矩阵的加法、数乘和乘法下成为复数域上的代数. 我们通过 (6) 式来定义映射\xi, 即\xi: C_n(\mathbb{C})\toD_n(\mathbb{C})定义为\xi(A)=P^{-1}AP=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}. 容易验证\xi保持矩阵的加法、数乘和乘法, 从⽽是⼀个代数同态. 对任⼀\Lambda=\mathrm{diag}\{\lambda_0,\lambda_1,\cdots,\lambda_{n-1}\}, 利⽤ Lagrange 插值公式可知, 存在次数不超过n-1的复系数多项式h(\lambda), 使得h(\omega_k)=\lambda_k(0\leq k\leq n-1). 令B=h(J), 则\xi(B)=\Lambda, 即\xi是满射. ⼜\dim C_n(\mathbb{C})=\dim D_n(\mathbb{C})=n, 从⽽\xi是⼀个线性同构, 从⽽是代数同构. \Box推论 2 n阶复矩阵B可对⾓化的充要条件是B相似于某个循环矩阵.证明由定理 1 中的代数同构\xi是通过相似变换实现的即得结论. \Box推论 3 设A\in C_n(\mathbb{K}), 则A^*也是循环矩阵.证法 1 由 (6) 式可知P^*A^*(P^*)^{-1}=(P^{-1}AP)^*=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}^*仍为对⾓阵. 注意到P^*=|P|P^{-1}, 故上述等式可化为P^{-1}A^*P=(P^{-1}AP)^*=\mathrm{diag}\{g(1),g(\omega_1),g(\omega_2),\cdots,g(\omega_{n-1})\}^*.因此由定理 1 可知, A^*=\xi^{-1}\bigg(\xi(A)^*\bigg)也是循环矩阵.证法 2 由⾼代⽩⽪书的例 6.62 可知, 存在多项式h(\lambda)\in\mathbb{K}[\lambda], 使得A^*=h(A). 设A=g(J), 则A^*=h(A)=h(g(J))仍为J的多项式, 从⽽是循环矩阵.证法 3 设A=(a_{ij})的代数余⼦式为A_{ij}\,(1\leq i,j\leq n), 要证A^*是循环矩阵, 根据定义只要证明: 对任意的1\leq i,j\leq n,A_{ij}=A_{i+1,j+1}成⽴即可, 其中若i+1>n或j+1>n, 则需要把i+1或j+1换成i+1-n或j+1-n. 证明A_{ij}=A_{i+1,j+1}只需要简单的⾏列式计算即可. ⽐如先把A_{ij}的最后⼀列经过n-2次相邻对换换⾄第⼀列, 再把得到⾏列式的最后⼀⾏经过n-2次相邻对换换⾄第⼀⾏, 最后就能得到A_{i+1,j+1}. 我们把验证的细节留给读者完成. \Box推论 4 若A\in C_n(\mathbb{K})是⾮异阵, 则A^{-1}也是循环矩阵.证法 1 由定理 1 可知, A^{-1}=\xi^{-1}\bigg(\xi(A)^{-1}\bigg)也是循环矩阵.证法 2 由 Cayley-Hamilton 定理可知, 存在多项式h(\lambda)\in\mathbb{K}[\lambda], 使得A^{-1}=h(A) (参考⾼代⽩⽪书的例 6.61). 设A=g(J), 则A^{-1}=h(A)=h(g(J))仍为J的多项式, 从⽽是循环矩阵.证法 3 设A=g(J), 则由A⾮异可知(\lambda^n-1,g(\lambda))=1. 由互素多项式的性质可知, 存在u(\lambda),v(\lambda)\in\mathbb{K}[\lambda], 使得(\lambda^n-1)u(\lambda)+g(\lambda)v(\lambda)=1. 令\lambda=J, 代⼊上式可得g(J)v(J)=I_n, 从⽽A^{-1}=v(J)也是循环矩阵.证法 4 由A^{-1}=\dfrac{1}{|A|}A^*以及推论 3 即得结论. \Box推论 5 \mathbb{K}上的n阶⾮异循环矩阵全体GC_n(\mathbb{K})在矩阵乘法下成为⼀个 Abel 群.推论 6 设A为n阶复循环矩阵, f(z)是收敛半径等于+\infty的复幂级数, 则f(A)也是循环矩阵.证法 1 注意到f(P^{-1}AP)=P^{-1}f(A)P, 从⽽f(A)=\xi^{-1}\bigg(f(\xi(A))\bigg)也是循环矩阵.证法 2 由可知, 存在多项式h(z), 使得f(A)=h(A)也是循环矩阵.证法 3 设f(z)=\sum\limits_{i=0}^\infty a_iz^i, f_p(z)=\sum\limits_{i=0}^p a_iz^i为f(z)的部分和多项式. 设A=a_1I_n+a_2J+a_3J^2+\cdots+a_nJ^{n-1}, 则f_p(A)=b^{(p)}_1I_n+b^{(p)}_2J+b^{(p)}_3J^2+\cdots+b^{(p)}_nJ^{n-1}. 由于矩阵序列\lim\limits_{p\to\infty}f_p(A)收敛到f(A), 故每个数列\lim\limits_{p\to\infty}b^{(p)}_i都收敛. 若设\lim\limits_{p\to\infty}b^{(p)}_i=b_i\,(1\leq i\leq n), 则f(A)=\lim\limits_{p\to\infty}f_p(A)=b_1I_n+b_2J+b_3J^2+\cdots+b_nJ^{n-1}仍为循环矩阵. \Box\S 3循环矩阵的应⽤下⾯我们给出循环矩阵的⼀个应⽤.命题 7 设有\mathbb{K}中n^2\,(n\geq 2)个不同的数, 则存在⼀个全排列, 记为a_1,\cdots,a_{n^2}, 使得\begin{vmatrix} a_1 & a_2 & \cdots & a_n \\ a_{n+1} & a_{n+2} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n^2-n+1} & a_{n^2-n+2} & \cdots & a_{n^2} \\\end{vmatrix}\neq 0.证明对n进⾏归纳. n=2时, 先取到a_1,a_2, 使得a_1+a_2\neq 0, 从⽽\begin{vmatrix} a_1 & a_2 \\ a_2 & a_1 \\ \end{vmatrix}=(a_1-a_2) (a_1+a_2)\neq 0, 于是B=\{(a_1,a_2),(a_2,a_1)\}是\mathbb{K}^2的⼀组基. 注意到(a_3,a_4)\neq 0, 故由基扩张定理, 必可从基B中选取⼀个基向量, 不妨设为(a_1,a_2), 使得\{(a_1,a_2),(a_3,a_4)\}成为\mathbb{K}^2的⼀组新基, 因此\begin{vmatrix} a_1 & a_2 \\ a_3 & a_4 \\\end{vmatrix}\neq 0. 设n-1时结论成⽴, 现证n的情形.证法 1 先取到a_1,a_2,\cdots,a_n, 使得a_1+a_2\omega_k+\cdots+a_n\omega_k^{n-1}\neq 0对0\leq k\leq n-1都成⽴. 这⼀定能做到, ⽐如先选定a_2,\cdots,a_n, 则不满⾜上述条件的a_1最多只有n个, 从⽽可取到满⾜上述条件的a_1. 由循环矩阵的性质可知, (1) 式中的循环矩阵A是⾮异阵, 特别地, A的n个⾏向量\{\beta_1,\beta_2,\cdots,\beta_n\}是\mathbb{K}^n的⼀组基. 由归纳假设, 可从剩下n^2-n个数中选出(n-1)^2个数的全排列, 使得\begin{vmatrix} a_{n+2} & \cdots & a_{2n} \\ \vdots & & \vdots \\ a_{n^2-n+2} & \cdots & a_{n^2} \\\end{vmatrix}\neq 0,后⾯随便选取a_{n+1},\cdots,a_{n^2-n+1}, 均可使n-1个⾏向量(a_{n+1},a_{n+2},\cdots,a_{2n}), \cdots, (a_{n^2-n+1},a_{n^2-n+2},\cdots,a_{n^2})线性⽆关 (参考复旦⾼代教材的习题 3.4.9). 因此由基扩张定理, 必可从基\{\beta_1,\beta_2,\cdots,\beta_n\}中选出⼀个基向量, 不妨设为\beta_1, 使得\{(a_1,a_2,\cdots,a_n), (a_{n+1},a_{n+2},\cdots,a_{2n}), \cdots, (a_{n^2-n+1},a_{n^2-n+2},\cdots,a_{n^2})\}构成\mathbb{K}^n的⼀组新基, 从⽽结论得证.证法 2 ⽤反证法, 设对n^2个数的所有全排列, 对应的⾏列式都等于零, 我们来推出⽭盾. 先取到a_1,a_2,\cdots,a_n, 使得a_1+a_2+\cdots+a_n\neq 0, 再由归纳假设, 不妨设取到的⾏列式中, a_1的代数余⼦式A_1\neq 0. 设其余元素a_i的代数余⼦式为A_i\,(2\leq i\leq n), 因此a_1A_1+a_2A_2+\cdots+a_nA_n=0. 在取到的⾏列式中, 对换第⼀⾏的a_1与a_i\,(2\leq i\leq n), 其余n^2-2个元素保持不变, 则有a_iA_1+\cdots+a_1A_i+\cdots+a_nA_n=0. 由此可得(a_1-a_i)(A_1-A_i)=0, 但a_1\neq a_i, 从⽽A_1=A_i\,(2\leq i\leq n). 最后,0=a_1A_1+a_2A_2+\cdots+a_nA_n=(a_1+a_2+\cdots+a_n)A_1\neq 0, ⽭盾. \Box注 1 命题 7 的证法 1 是构造性的, 利⽤这⼀证法可以给出满⾜条件的全排列的总个数的⼀个粗略估计. 命题 7 的证法 2 由复旦数学学院 16 级本科⽣朱民哲提供.注 2 本⽂的主要结论还可以推⼴到特征零的域或者特征p>0的域 (要求p\nmid n) 及其分裂域或代数闭包上. 另外, ⾼代⽩⽪书第⼆章的解答题 13 还给出了b-循环矩阵的推⼴. 有兴趣的读者可以⾃⾏学习和验证这些结论.参考⽂献[1] ⾼代教材: 姚慕⽣, 吴泉⽔, 谢启鸿编著, ⾼等代数学 (第三版), 复旦⼤学出版社, 2014.[2] ⾼代⽩⽪书: 姚慕⽣, 谢启鸿编著, 学习⽅法指导书: ⾼等代数 (第三版), 复旦⼤学出版社, 2015.Processing math: 0%。