四阶循环行列式

青青子衿

\begin{align*}
\begin{vmatrix}
a & b & c & d \\
b & c & d & a \\
c & d & a & b \\
d & a & b & c \\
\end{vmatrix}
=
\begin{vmatrix}
b^2+d^2-2 a c & a^2+c^2-2 b d \\
a^2+c^2-2 b d & b^2+d^2-2 a c \\
\end{vmatrix}\\
\\
\begin{vmatrix}
a & b & c & d \\
d & a & b & c \\
c & d & a & b \\
b & c & d & a \\
\end{vmatrix}
=
\begin{vmatrix}
a^2+c^2-2 b d & b^2+d^2-2 a c \\
b^2+d^2-2 a c & a^2+c^2-2 b d \\
\end{vmatrix}
\end{align*}

tommywong

$\begin{vmatrix}
a & b & c & d \\
b & c & d & a \\
c & d & a & b \\
d & a & b & c \\
\end{vmatrix}
=(a+b+c+d)
\begin{vmatrix}
1 & b & c & d \\
1 & c & d & a \\
1 & d & a & b \\
1 & a & b & c \\
\end{vmatrix}
=(a+b+c+d)\begin{vmatrix}
c-b & d-c & a-d \\
d-b & a-c & b-d \\
a-b & b-c & c-d \\
\end{vmatrix}$

$=(a+b+c+d)(a-b+c-d)\begin{vmatrix}
1 & d-c & a-d \\
0 & a-c & b-d \\
1 & b-c & c-d \\
\end{vmatrix}
=(a+b+c+d)(a-b+c-d)\begin{vmatrix}
a-c & b-d \\
b-d & c-a \\
\end{vmatrix}
$

$=-(a+b+c+d)(a-b+c-d)((a-c)^2+(b-d)^2)$

Czhang271828

记一般循环方阵 $(a_{ij})_{n\times n}$ 满足 $a_{ij}=b_{j-i}$, 其中 $j-i$ 在模 $n$ 下等价(例如 $b_{-2}=b_{n-2}$). 记矩阵

$$
Z:=\begin{pmatrix}
0^{n-1}&I_{n-1}\\
1&(0^{n-1})^T
\end{pmatrix}
=
\begin{pmatrix}
0&1&0&\cdots &0\\
0&0&1&\cdots &0\\
\vdots&\ddots&\ddots&\ddots&0\\
\vdots&\ddots&\ddots&\ddots&1\\
1&\cdots&\cdots&\cdots&0
\end{pmatrix}
$$

则待求矩阵即 $\sum_{k=0}^{n-1}b_k Z^k=:f(Z)$. 从而相应的特征值为 $f(\omega)$, 其中 $\omega=e^{2\pi i/n}$.

因此 $f(Z)$ 的行列式为 $\prod_{k=0}^{n-1}f(\omega^k)$.

例如
$$
\begin{align*}
&\det\begin{pmatrix}a&b&c&d\\d&a&b&c\\c&d&a&b\\b&c&d&a\end{pmatrix}\\
=&\prod_{k=0}^3(a+b(\omega^j)+c(\omega^j)^2+d(\omega^j)^3)\\
=&(a+b+c+d)(a+bi-c-di)(a-b+c-d)(a-bi-c+di)
\end{align*}
$$

Czhang271828

这道题 Mark 一下, 循环矩阵 $A$ 与 $x$ 相乘的算法复杂度可以为 $O(N\log N)$, 其中 $A\in K^{N\times N}$.

记 $A =(a_{i,N-j})_{N\times N}$ 为循环矩阵, 即 $a_k:=a_{l,l+k}$ 为与 $l$ 无关的定值. 记
\[
\begin{pmatrix}\mathbf 0^T&1\\I_{N-1}&\mathbf 0\end{pmatrix}.
\]
注意到
\[
Z^k=\begin{pmatrix}\mathbf 0&I_l\\I_{N-l}&\mathbf 0\end{pmatrix},\quad k\equiv l\mod N.
\]
从而 $A=\sum_{k=0}^{N-1}a_kZ^k=:p(Z)$.

由于 $Z$ 的特征值为 $\{e^{2k\pi i/N}\}_{k=0}^{N-1}:=\{\zeta_N^k\}_{k=0}^{N-1}$, 其中 $\zeta_N^k$ 对应的特征向量为
\[
v^k=(\zeta_N^{0\cdot k},\zeta_N^{-k},\ldots,\zeta_N^{-(N-1)k}).
\]
故求得 $Av^k=p(\zeta_N^k)v^k$.

记 $Q=(v^1\mid v^2\mid\cdots\mid v^{N-1})$ 为对角化矩阵, 注意到 $\hat x=Qx$ 无非 $x$ 的离散 Fourier 变换, 故
\begin{align*}
&\,y=Ax\\
\Leftrightarrow&\,Qy=\mathrm{diag}(p(\zeta_N^0),\ldots,p(\zeta_N^{N-1}))\cdot Q x\\
\Leftrightarrow&\,(\hat y_0,\hat y_1,\ldots,\hat y_{N-1})=(p(\zeta_N^0)\hat x_0,p(\zeta_N^1)\hat x_1,\ldots,p(\zeta_N^{N-1})\hat x_{N-1}).
\end{align*}
算法复杂度即 $N$ 加上两个 FFT.

青青子衿

感觉最上面的恒等式像是循环群的群表行列式在特殊数域上的分解