拉普拉斯展开式的副对角线形式算法优化小结

拉普拉斯展开式的教科书形式

乏善可陈,课上是这么讲的:

\begin{vmatrix}A& O \\O & B \end{vmatrix}= \begin{vmatrix}A &C \\O& B \end{vmatrix}=\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}B\end{vmatrix}

这段我没有什么需要补充的,主要是作为引入。

而关于其副对角线形式,课上是这么教的:

\begin{vmatrix}O& A \\B & O \end{vmatrix}= \begin{vmatrix}C &A \\B& O \end{vmatrix}=(-1)^{mn}\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}B\end{vmatrix}

其中m为 A 的阶,n为 B 的阶。

对于这个形式可以说是完全正确,但我接下来要将这个形式更替为更简单的表达方式

拉普拉斯展开的副对角线形式的证明过程

a_1 表示的是矩阵 A 的第一列,以此类推,请记住这两个算式,后面要用:

A =\left[\begin{matrix} a_1&a_2&a_3… a_m \end{matrix}\right]

B =\left[\begin{matrix} b_1&b_2&b_3… b_n \end{matrix}\right]

教科书给的证明方案如下:

不妨令原矩阵为MATHJAX-SSR-4,逐项将 a_1 所在列与前一项互换,直到抵达第一列,将 a_2 所在列逐项与前一项互换……在这个过程中, b_1 b_2 所在列的顺序没有变化。

根据行列式的性质可以得到,经过了 m 次运算将 A 所有列提前,每次运算发生了 n 次交换。

故应该乘以 (-1)^{mn} ,交换后的算式为: (-1)^{mn}\begin{vmatrix}A& O \\O & B \end{vmatrix}

使用小学二年级的证明方式:

小学二年级学过乘法、加法和奇数偶数,所以这个证明确实是小学二年级学过的

对于, m n 同为自然数,有以下性质:

m n 同为偶数的时候,有 m+n 的奇偶性与 mn 相同,所以我们也可以说

(-1)^{mn}\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}B\end{vmatrix}=(-1)^{m+n}\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}B\end{vmatrix} m n 同为偶数时成立

天哪就是这么一个没有任何说服力的猜想,居然和我们最终的结果有联系

使用先进一点点的算法证明:反转算法

对于这个问题我们可以归纳为如下形式:

原矩阵的每一列写作 s_i ,原矩阵写作 S=\left[\begin{matrix}s_1&s_2&s_3… s_m&s_{m+1}&s_{m+2}&s_{m+3}… s_{m+n}\end{matrix}\right]

此时我们不采用逐项交换的思想,而是改为整体反转的思想

将矩阵 S m 项整体反转,一共经过 \lfloor{\frac{m}{2}}\rfloor 次交换,我们得到 S=\left[\begin{matrix}s_{m}&s_{m-1}&s_{m-2}… s_1&s_{m+1}&s_{m+2}&s_{m+3}… s_{m+n}\end{matrix}\right]

将矩阵 S n 项整体反转,一共经过 \lfloor{\frac{n}{2}}\rfloor 次交换,我们得到 S=\left[\begin{matrix}s_{m}&s_{m-1}&s_{m-2}… s_1&s_{m+n}&s_{m+n-1}&s_{m+n-2}… s_{m+1}\end{matrix}\right]

将整个矩阵整体反转,一共经过了 \lfloor{\frac{m+n}{2}}\rfloor 次交换,我们得到 S=\left[\begin{matrix}s_{m+1}&s_{m+2}&s_{m+3}… s_{m+n}&s_{1}&s_{2}&s_{3}… s_{m}\end{matrix}\right]

天哪,这个结果正好是我们要的

\begin{vmatrix}A& O \\O & B \end{vmatrix}=\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}B\end{vmatrix}

而我们一共经过了 \lfloor{\frac{m}{2}}\rfloor \lfloor{\frac{n}{2}}\rfloor \lfloor{\frac{m+n}{2}}\rfloor 次交换,所以应该乘以 (-1)^{\lfloor{\frac{m+n}{2}}\rfloor+\lfloor{\frac{m}{2}}\rfloor+\lfloor{\frac{n}{2}}\rfloor}

m n 不同为奇数时,等价于 (-1)^{m+n}\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}B\end{vmatrix}

值得注意的是,在计算机运算中,向下取整和除以2都是容易计算的,我们将乘法转化为了加法,而在计算机中这意味着我们降低了运算的时间复杂度。

使用更先进的计算方法:循环领袖算法

同样思考这个问题,我们可以将原问题总结为:

对于矩阵 S 中的所有列,前 m 项向后移动 n 项,后 n 项向前移动 m

  • 映射函数 f(k) 定义如下:
    • 如果 k\leq m ,则 f(k)=k+n (对应 S 的前 m 列向右移动 n 位)。
    • 如果 k>m ,则 f(k)=k−m (对应 S 的后 n 列向左移动 m 位)。
  • 该映射形成一个置换,其循环分解后的循环个数为 gcd⁡(m,n) ,每个循环的长度为 d=(m+n)/gcd⁡(m,n)

每个循环的长度为 d ,需要 d−1 次交换。共有 gcd⁡(m,n) 次循环,故共交换 m+n-gcd(m,n)

使用欧几里得算法,时间复杂度不超过 O(n+m) ,空间复杂度为 O(1)

然而并不止于此……

对于计算机而言,考虑 (-1)^{m+n} 实际上并不需要考虑完整的 m n ,因为在计算机中使用二进制存储,只用考虑二进制最低位即可。

循环领袖算法理论复杂度低于反转算法,但反转算法中,我们只需要考虑4个位置: m 的最低位和倒数第二低位、 n 的最低位和倒数第二低位即可。

对于人眼观测,实际上只用看两个数字的奇偶即可。

但对于更高阶的拉普拉斯展开式(例如: \begin{vmatrix}O&O&O&A \\O&O&B & O \\O&C&O&O\\D&O&O&O\end{vmatrix} ),我们的算法显著能够降低运算难度,将多个多项式乘法转化为欧几里得算法和加法的结合,能够降低时间复杂度。