前置知识
- \(\sum\) 为累加符号,\(\prod\) 为累乘符号。
- 上三角矩阵指只有对角线及其右上方有数值其余都是 \(0\) 的矩阵。
- 如果一个矩阵的对角线全部为 \(1\) 那么这个矩阵为单位矩阵记作 \(I\)。
- 对于矩阵 \(A_{n,m}\) 和矩阵 \(B_{m,n}\) 满足 \(A_{i,j}=B_{j,i}\) 记作 \(A=B^T\)。
- 如果 \(i,j\in[1,n]\) 满足 \(i<j\) 且 \(p_i>p_j\),那么称 \((p_i,p_j)\) 为一对逆序对。
- 假设 \(p\) 是一个排列,那么 \(\tau(p)\) 为 \(p\) 中逆序对的个数。
定义
行列式 \(A\) 为 \(n\) 阶方阵,那么 \(|A|\) 为该矩阵的行列式,记作 \(\operatorname{det}(A)\)。
\[\begin{vmatrix} a_{1,1} & a_{1,2} &\cdots & a_{1,n} \\ a_{2,1} & a_{2,2} &\cdots & a_{2,n} \\ \cdots & \cdots &\cdots & \cdots \\ a_{n,1} & a_{n,2} &\cdots & a_{n,n} \\ \end{vmatrix}=\sum_{j_1,j_2,\cdots ,j_n}(-1)^{N(j_1,j_2,\cdots ,j_n)}\prod_{i=1}^n a_{i,j_i}\]几何意义
对于一个 \(n\) 维的向量空间中的 \(n\) 个向量,我们可以构造一个 \(n\) 阶行列式。这个行列式的绝对值等于由这 \(n\) 个向量所构成的平行体的体积。
具体来说,如果我们有 \(n\) 个向量 \(\vec{v_1}, \vec{v_2}, ..., \vec{v_n}\),我们可以将这些向量的坐标构造成一个n阶行列式:
\[\begin{bmatrix} v_{1,1} & v_{1,2} & \cdots & v_{1,n} \\ v_{2,1} & v_{2,2} & \cdots & v_{2,n} \\ \cdots & \cdots & \cdots & \cdots \\ v_{n,1} & v_{n,2} & \cdots & v_{n,n} \\ \end{bmatrix} \]其中,\(v_{ij}\) 是向量 \(\vec{v_i}\) 的第 \(j\) 个坐标。这个行列式的绝对值就是由向量 \(\vec{v_1}, \vec{v_2}, ..., \vec{v_n}\) 所形成的平行体的体积。
求解
暴力
首先有一个粗暴的做法单纯是根据定义求解的,虽然无法应用到那时有助于理解定义。
要求解行列式首先需要随机选择一行,为了方便说明不妨取第一行。那么在这一行的第 \(i\) 个元素的贡献为 \((-1)^{1+i}\times 1\times\) 不看这一行和这一列剩余的矩阵。
\[\begin{vmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 &8 &9\end{vmatrix}\\=(-1)^{1+1}\times 1\times \begin{vmatrix}5& 6\\8&9\end{vmatrix}+(-1)^{1+2}\times 2\times \begin{vmatrix}4&6\\7&9\end{vmatrix}+(-1)^{1+3}\times 3\times \begin{vmatrix}4&5\\7&8\end{vmatrix} \]通过这个操作,我们就将这个行列式降阶了,接下来我们只需要一直进行递归操作直到行列式的阶成为 \(1\) 就好了。所以根据定义我们就可以在 \(O(n!)\) 的时间复杂度内求解出 \(n\) 阶行列式的值了。
优化
假设矩阵 \(A\) 是一个上三角矩阵,那么 \(\operatorname{det}(A)=\prod_{i=1}^{n}a_{i,i}\) 的值,求解的时间复杂度十分优秀为 \(O(n)\),考虑是否可以使用高斯消元进行优化。
排列的性质
- 定义如果 \(\tau(p)\) 为奇数那么 \(p\) 为奇排列,反之即为偶排列。
- 对于一个 \(n(n\geq2)\) 阶排列的所有排列情况,奇排列与偶排列的情况各有 \(\dfrac{1}{2}\cdot n!\) 种。
- 将 \(p\) 中两个不同的元素进行交换得到一个新的排列的过程叫对换操作,进行一次对换操作会改变序列的奇偶性。
矩阵性质
- \(\operatorname{det}(A)=\operatorname{det}(A^T)\),所以说所有的对列成立的性质均对行成立,反之亦然。
带入排列的性质自行观察即可以得到。 - 交换某 \(2\) 行或列,此时的 \(\operatorname{det}(A)\) 需要乘以 \(-1\)。
证明同上。 - 根据上一行进行推论,如果有两行相同那么 \(\operatorname{det}(A)=0\)。
假设 \(s=\operatorname{det}(A)\),不妨设行 \(x\) 与行 \(y\) 相等,那么假设交换 \(x,y\) 则有 \(\operatorname{det}(A)=-s\) 但是矩阵并未变化,所以 \(\operatorname{det}(A)=-\operatorname{det}(A)\) 就得到了 \(\operatorname{det}(A)=0\) 是唯一解了。 - 将 \(A\) 的一行全部乘以 \(k\),那么 \(\operatorname{det}(A)\) 也需要乘以 \(k\)。
考虑从使用定义求解行列式的值的角度进行解释。因为在求值是选择任意行计算的结果都是相同的,所以不妨假设我们刚好选择了全部乘以 \(k\) 的那一行,使用乘法分配律将 \(k\) 提出即可证明。 - 根据上一行进行推论,如果有一行全部为 \(0\) 那么,那么 \(\operatorname{det}(A)=0\)。
假设 \(s=\operatorname{det}(A)\),那么不妨假设 \(x\) 行全部为 \(0\)。将行 \(x\) 全部乘以 \(k\) 得到 \(\operatorname{det}(A)=s\cdot k\),可是矩阵并未变化所以 \(\operatorname{det}(A)=s\),因为 \(k\) 为任意值所以得到 \(\operatorname{det}(A)=0\)。 - 如果行列式对应矩阵 \(A\) 中有一行,是对应 \(2\) 个矩阵 \(B,C\) 中分别的 \(2\) 行所有元素之和,那么有 \(\det(A)=\det(B)+\det(C)\)。
- 将某一行的的 \(k\) 倍加到另外一行,不影响 \(\operatorname{det}(A)\) 的值。
结合前面的一些性质即可证明,十分显然。
高斯消元
考虑到将某一行的的 \(k\) 倍加到另外一行不影响 \(\operatorname{det}(A)\) 的值,可以直接使用高斯消元就可以求解了。同样还是高斯消元,用一个变量记录交换两行引起的符号改变。因为将一行的 \(
标签:det,vmatrix,cdots,行列式,求值,优化,operatorname,vdots From: https://www.cnblogs.com/liudagou/p/18219099