文章目录
- 基本概念
- 拉普拉斯定理
- Python实现
- 结语
基本概念
在学习拉普拉斯定理之前，先介绍几个重要概念,第一个概念是k阶子式。k-阶子式是指挑选矩阵的k行，k列，按原来的顺序组成的子矩阵的行列式 ，记号比较复杂，我举个例子，第
1
,
3
,
5
1,3,5
1,3,5行和第
1
,
2
,
4
1,2,4
1,2,4列组成的3-阶子式就记为：
A
(
1
,
3
,
5
1
,
2
,
4
)
=
∣
a
11
a
12
a
14
a
31
a
32
a
34
a
51
a
52
a
54
∣
A\begin{pmatrix}1,3,5\\1,2,4\end{pmatrix}= \begin{vmatrix}a_{11} & a_{12} & a_{14}\\ a_{31} & a_{32} & a_{34}\\ a_{51} & a_{52} & a_{54} \end{vmatrix}
A(1,3,51,2,4)=
a11a31a51a12a32a52a14a34a54
k-阶余子式，就是取反操作，删除对应行和对应列，剩余的矩阵元素，按照位置不变形成的子矩阵的行列式，比如对于5-阶矩阵来说，
1
,
3
,
5
1,3,5
1,3,5行和第
1
,
2
,
4
1,2,4
1,2,4列的余子式就是
A
(
2
,
4
3
,
5
)
A\begin{pmatrix}2,4\\3,5\end{pmatrix}
A(2,43,5).
剩下一个概念就是代数余子式，是余子式根据行索引和列索引加起来的奇偶性来判断，奇数为负的余子式，偶数为正的余子式。
拉普拉斯定理
拉普拉斯定理提供了一种计算
n
n
n阶行列式的办法。就是按k行或k列展开。它的算法第一步就是先求n的全部k种组合，然后求这k行和所有k种列组合的子式与代数余子式的乘积，把这些乘积加起来就是行列式。
公式描述比较麻烦，我以五阶矩阵按第一和第二行展开为例子，讲讲怎么计算。
首先求所有五阶矩阵取两列的所有的列组合，得出以下10种：
(
1
,
2
)
,
(
1
,
3
)
,
(
1
,
4
)
,
(
1
,
5
)
(
2
,
3
)
,
(
2
,
4
)
,
(
2
,
5
)
(
3
,
4
)
,
(
3
,
5
)
(
4
,
5
)
(1,2),(1,3),(1,4),(1,5)\\ (2,3),(2,4),(2,5)\\ (3,4),(3,5)\\ (4,5)\\
(1,2),(1,3),(1,4),(1,5)(2,3),(2,4),(2,5)(3,4),(3,5)(4,5)
那么展开就是：
∣
A
∣
=
A
(
1
,
2
1
,
2
)
×
A
(
3
,
4
,
5
3
,
4
,
5
)
+
A
(
1
,
2
1
,
3
)
×
(
−
1
)
A
(
3
,
4
,
5
2
,
4
,
5
)
+
A
(
1
,
2
1
,
4
)
×
A
(
3
,
4
,
5
2
,
3
,
5
)
+
A
(
1
,
2
1
,
5
)
×
(
−
1
)
A
(
3
,
4
,
5
2
,
3
,
4
)
+
A
(
1
,
2
2
,
3
)
×
A
(
3
,
4
,
5
1
,
4
,
5
)
+
A
(
1
,
2
2
,
4
)
×
(
−
1
)
A
(
3
,
4
,
5
1
,
3
,
5
)
+
A
(
1
,
2
2
,
5
)
×
A
(
3
,
4
,
5
1
,
3
,
4
)
+
A
(
1
,
2
3
,
4
)
×
A
(
3
,
4
,
5
1
,
2
,
5
)
+
A
(
1
,
2
3
,
5
)
×
(
−
1
)
A
(
3
,
4
,
5
1
,
2
,
4
)
+
A
(
1
,
2
4
,
5
)
×
A
(
3
,
4
,
5
1
,
2
,
3
)
|A|=A\begin{pmatrix}1,2\\1,2\\\end{pmatrix} \times A\begin{pmatrix}3,4,5\\3,4,5\end{pmatrix}\\ +A\begin{pmatrix}1,2\\1,3\\\end{pmatrix} \times (-1)A\begin{pmatrix}3,4,5\\2,4,5\end{pmatrix}\\ +A\begin{pmatrix}1,2\\1,4\\\end{pmatrix} \times A\begin{pmatrix}3,4,5\\2,3,5\end{pmatrix}\\ +A\begin{pmatrix}1,2\\1,5\\\end{pmatrix} \times (-1)A\begin{pmatrix}3,4,5\\2,3,4\end{pmatrix}\\ +A\begin{pmatrix}1,2\\2,3\\\end{pmatrix} \times A\begin{pmatrix}3,4,5\\1,4,5\end{pmatrix}\\ +A\begin{pmatrix}1,2\\2,4\\\end{pmatrix} \times (-1)A\begin{pmatrix}3,4,5\\1,3,5\end{pmatrix}\\ +A\begin{pmatrix}1,2\\2,5\\\end{pmatrix} \times A\begin{pmatrix}3,4,5\\1,3,4\end{pmatrix}\\ +A\begin{pmatrix}1,2\\3,4\\\end{pmatrix} \times A\begin{pmatrix}3,4,5\\1,2,5\end{pmatrix}\\ +A\begin{pmatrix}1,2\\3,5\\\end{pmatrix} \times (-1)A\begin{pmatrix}3,4,5\\1,2,4\end{pmatrix}\\ +A\begin{pmatrix}1,2\\4,5\\\end{pmatrix} \times A\begin{pmatrix}3,4,5\\1,2,3\end{pmatrix}\\
∣A∣=A(1,21,2)×A(3,4,53,4,5)+A(1,21,3)×(−1)A(3,4,52,4,5)+A(1,21,4)×A(3,4,52,3,5)+A(1,21,5)×(−1)A(3,4,52,3,4)+A(1,22,3)×A(3,4,51,4,5)+A(1,22,4)×(−1)A(3,4,51,3,5)+A(1,22,5)×A(3,4,51,3,4)+A(1,23,4)×A(3,4,51,2,5)+A(1,23,5)×(−1)A(3,4,51,2,4)+A(1,24,5)×A(3,4,51,2,3)
再具体以实际的矩阵展开，还是以
5
×
5
5\times 5
5×5的矩阵为例子：
∣
2
2
4
1
−
1
−
1
−
2
−
3
−
4
4
−
2
3
1
2
−
2
3
−
4
3
−
2
−
4
4
−
4
3
−
4
−
1
∣
=
∣
2
2
−
1
−
2
∣
×
∣
1
2
−
2
3
−
2
−
4
3
−
4
−
1
∣
+
∣
2
4
−
1
−
3
∣
×
(
−
1
)
∣
3
2
−
2
−
4
−
2
−
4
−
4
−
4
−
1
∣
+
∣
2
1
−
1
−
4
∣
×
∣
3
1
−
2
−
4
3
−
4
−
4
3
−
1
∣
+
∣
2
−
1
−
1
4
∣
×
(
−
1
)
∣
3
1
2
−
4
3
−
2
−
4
3
−
4
∣
+
∣
2
4
−
2
−
3
∣
×
∣
−
2
2
−
2
3
−
2
−
4
4
−
4
−
1
∣
+
∣
2
1
−
2
−
4
∣
×
(
−
1
)
∣
−
2
1
−
2
3
3
−
4
4
3
−
1
∣
+
∣
2
−
1
−
2
4
∣
×
∣
−
2
1
2
3
3
−
2
4
3
−
4
∣
+
∣
4
1
−
3
−
4
∣
×
∣
−
2
3
−
2
3
−
4
−
4
4
−
4
−
1
∣
+
∣
4
−
1
−
3
4
∣
×
(
−
1
)
∣
−
2
3
2
3
−
4
−
2
4
−
4
−
4
∣
+
∣
1
−
1
−
4
4
∣
×
∣
−
2
3
1
3
−
4
3
4
−
4
3
∣
=
58
\begin{vmatrix}2 & 2 & 4 & 1 & -1\\ -1 & -2 & -3 & -4 & 4\\ -2 & 3 & 1 & 2 & -2\\ 3 & -4 & 3 & -2 & -4\\ 4 & -4 & 3 & -4 & -1\\ \end{vmatrix}\\ =\begin{vmatrix}2 & 2\\ -1 & -2\\ \end{vmatrix} \times \begin{vmatrix}1 & 2 & -2\\ 3 & -2 & -4\\ 3 & -4 & -1\\ \end{vmatrix} \\+\begin{vmatrix}2 & 4\\ -1 & -3\\ \end{vmatrix} \times (-1)\begin{vmatrix}3 & 2 & -2\\ -4 & -2 & -4\\ -4 & -4 & -1\\ \end{vmatrix} \\+\begin{vmatrix}2 & 1\\ -1 & -4\\ \end{vmatrix} \times \begin{vmatrix}3 & 1 & -2\\ -4 & 3 & -4\\ -4 & 3 & -1\\ \end{vmatrix} \\+\begin{vmatrix}2 & -1\\ -1 & 4\\ \end{vmatrix} \times (-1)\begin{vmatrix}3 & 1 & 2\\ -4 & 3 & -2\\ -4 & 3 & -4\\ \end{vmatrix} \\+\begin{vmatrix}2 & 4\\ -2 & -3\\ \end{vmatrix} \times \begin{vmatrix}-2 & 2 & -2\\ 3 & -2 & -4\\ 4 & -4 & -1\\ \end{vmatrix} \\+\begin{vmatrix}2 & 1\\ -2 & -4\\ \end{vmatrix} \times (-1)\begin{vmatrix}-2 & 1 & -2\\ 3 & 3 & -4\\ 4 & 3 & -1\\ \end{vmatrix} \\+\begin{vmatrix}2 & -1\\ -2 & 4\\ \end{vmatrix} \times \begin{vmatrix}-2 & 1 & 2\\ 3 & 3 & -2\\ 4 & 3 & -4\\ \end{vmatrix} \\+\begin{vmatrix}4 & 1\\ -3 & -4\\ \end{vmatrix} \times \begin{vmatrix}-2 & 3 & -2\\ 3 & -4 & -4\\ 4 & -4 & -1\\ \end{vmatrix} \\+\begin{vmatrix}4 & -1\\ -3 & 4\\ \end{vmatrix} \times (-1)\begin{vmatrix}-2 & 3 & 2\\ 3 & -4 & -2\\ 4 & -4 & -4\\ \end{vmatrix} \\+\begin{vmatrix}1 & -1\\ -4 & 4\\ \end{vmatrix} \times \begin{vmatrix}-2 & 3 & 1\\ 3 & -4 & 3\\ 4 & -4 & 3\\ \end{vmatrix}\\=58
2−1−2342−23−4−44−31331−42−2−4−14−2−4−1
=
2−12−2
×
1332−2−4−2−4−1
+
2−14−3
×(−1)
3−4−42−2−4−2−4−1
+
2−11−4
×
3−4−4133−2−4−1
+
2−1−14
×(−1)
3−4−41332−2−4
+
2−24−3
×
−2342−2−4−2−4−1
+
2−21−4
×(−1)
−234133−2−4−1
+
2−2−14
×
−2341332−2−4
+
4−31−4
×
−2343−4−4−2−4−1
+
4−3−14
×(−1)
−2343−4−42−2−4
+
1−4−14
×
−2343−4−4133
=58
通过上面两个实际例子，就更容易理解拉普拉斯定理了。
Python实现
对于线性代数里学到的东西，我习惯性地用python实验一下，以下是我的python代码：
def laplace(self, rows):
k = len(rows)
n = len(self.__vectors)
import com.youngthing.mathalgorithm.combinatorics.binomial_combination_tree as bct
indices = [i for i in range(n)]
combinations = bct.combinations(indices, k)
rows_sum = sum(rows)
result = 0
remain_rows = [x for x in indices if x not in rows]
for combination in combinations:
# 子式
subdeterminant = self.subdeterminant(rows, combination)
# 代数余子式的符号
columns_sum = sum(combination)
even = (rows_sum + columns_sum) & 1 == 0
# 余子式
remain_columns = [x for x in indices if x not in combination]
minor = self.subdeterminant(remain_rows, remain_columns)
if even:
result += subdeterminant * minor
else:
result -= subdeterminant * minor
return result
def subdeterminant(self, rows, columns):
array = [[self.__vectors[column][row] for row in rows] for column in columns]
matrix = Matrix(array)
return matrix.cofactor_expansion()
结语
至此，我写了五种行列式的算法，定义法、chiò算法、Dodgson算法、按一行一列展开，按k行k列展开。前三种算法性能不高，计算量庞大，后两种算法只有在矩阵中含有比较多的0的时候（这种矩阵也叫稀疏矩阵）好用。接下来我要介绍一种实际应用中最常用，性能最好的算法，也就是高斯消元法。