拉普拉斯展开式的教科书形式
乏善可陈,课上是这么讲的:
这段我没有什么需要补充的,主要是作为引入。
而关于其副对角线形式,课上是这么教的:
其中m为的阶,n为的阶。
对于这个形式可以说是完全正确,但我接下来要将这个形式更替为更简单的表达方式
拉普拉斯展开的副对角线形式的证明过程
表示的是矩阵的第一列,以此类推,请记住这两个算式,后面要用:
教科书给的证明方案如下:
不妨令原矩阵为MATHJAX-SSR-4,逐项将所在列与前一项互换,直到抵达第一列,将所在列逐项与前一项互换……在这个过程中,、所在列的顺序没有变化。
根据行列式的性质可以得到,经过了次运算将所有列提前,每次运算发生了次交换。
故应该乘以,交换后的算式为:
使用小学二年级的证明方式:
小学二年级学过乘法、加法和奇数偶数,所以这个证明确实是小学二年级学过的
对于,和同为自然数,有以下性质:
当、同为偶数的时候,有的奇偶性与相同,所以我们也可以说
在、同为偶数时成立
天哪就是这么一个没有任何说服力的猜想,居然和我们最终的结果有联系
使用先进一点点的算法证明:反转算法
对于这个问题我们可以归纳为如下形式:
原矩阵的每一列写作,原矩阵写作
此时我们不采用逐项交换的思想,而是改为整体反转的思想
将矩阵前项整体反转,一共经过次交换,我们得到
将矩阵后项整体反转,一共经过次交换,我们得到
将整个矩阵整体反转,一共经过了次交换,我们得到
天哪,这个结果正好是我们要的
而我们一共经过了、、次交换,所以应该乘以
在、不同为奇数时,等价于
值得注意的是,在计算机运算中,向下取整和除以2都是容易计算的,我们将乘法转化为了加法,而在计算机中这意味着我们降低了运算的时间复杂度。
使用更先进的计算方法:循环领袖算法
同样思考这个问题,我们可以将原问题总结为:
对于矩阵中的所有列,前项向后移动项,后项向前移动项
- 映射函数 定义如下:
- 如果 ,则 (对应
的前列向右移动 位)。
- 如果 ,则 (对应
的后列向左移动 位)。
- 该映射形成一个置换,其循环分解后的循环个数为
,每个循环的长度为 。
每个循环的长度为 ,需要
次交换。共有次循环,故共交换次
使用欧几里得算法,时间复杂度不超过,空间复杂度为
然而并不止于此……
对于计算机而言,考虑实际上并不需要考虑完整的和,因为在计算机中使用二进制存储,只用考虑二进制最低位即可。
循环领袖算法理论复杂度低于反转算法,但反转算法中,我们只需要考虑4个位置:的最低位和倒数第二低位、的最低位和倒数第二低位即可。
对于人眼观测,实际上只用看两个数字的奇偶即可。
但对于更高阶的拉普拉斯展开式(例如:),我们的算法显著能够降低运算难度,将多个多项式乘法转化为欧几里得算法和加法的结合,能够降低时间复杂度。