LU 分解
考虑将 \(A\) 分解成 \(LU\)，\(L\) 为上三角矩阵，\(U\) 为下三角矩阵。
利用矩阵经典性质 \(|A|=|L||U|\)，可以轻易算出 \(det(A)\)。
考虑 \(A_{i,j}=\gcd(i,j)\)，一个经典性质是 \(\sum_{d|n} \phi(d)=n\)，那么设 \(L_{i,j}=[j|i]\)，\(U_{i,j}=[i|j]\phi(i)\)。故可以得到 \(|A|=\prod_{i=1}^n \phi(i)\)。
Matrix Determinant Lemma
\[|I_n+UV|=|I_m+VU|
\]
\(U,V\) 分别为 \(n\times m\) 和 \(m\times n\) 的矩阵。
证明：
\[\begin{pmatrix}I_n & \\V & I_m
\end{pmatrix}
\begin{pmatrix}I_n+UV &U \\& I_m
\end{pmatrix}
\begin{pmatrix}I_n & \\-V & I_m
\end{pmatrix}
=
\begin{pmatrix}I_n & U\\& VU+I_m
\end{pmatrix}
\]
两边取行列式即可。
扩展：对于 \(|A-B|\)（\(A,B\) 都是 \(n\times n\)），如果 \(B=UV\)（\(U,V\) 分别是 \(n\times m\) 和 \(m\times n\)），可以知道 \(A-B=A(I_n+A^{-1}B)\)，那么 \(|A-B|=|A||I_n+A^{-1}UV|=|A||I_m+VA^{-1}U|\)。原本计算需要 \(O(n^3)/O(n^2m)\)，现在就只要 \(O(nm^2)\)，在 \(m\) 比较小时比较优。