首页 > 其他分享 >行列式求值,从 $n!$ 优化到 $n^3$

行列式求值,从 $n!$ 优化到 $n^3$

时间:2024-05-28 22:33:00浏览次数:23  
标签:det vmatrix cdots 行列式 求值 优化 operatorname vdots

前置知识

  • \(\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)\)。

\[\begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ b_{i,1}+c_{i,1} &b_{i,2}+c_{i,2} &\cdots &b_{i,n}+c_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} = \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ b_{i,1} &b_{i,2} &\cdots &b_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} + \begin{vmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n}\\ a_{2,1} &a_{2,2} &\cdots &a_{2,n}\\ \vdots &\vdots &\ddots &\vdots\\ c_{i,1} &c_{i,2} &\cdots &c_{i,n}\\ \vdots &\vdots &\ddots &\vdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,n}\\ \end{vmatrix} \]

  • 将某一行的的 \(k\) 倍加到另外一行,不影响 \(\operatorname{det}(A)\) 的值。
    结合前面的一些性质即可证明,十分显然。

高斯消元

考虑到将某一行的的 \(k\) 倍加到另外一行不影响 \(\operatorname{det}(A)\) 的值,可以直接使用高斯消元就可以求解了。同样还是高斯消元,用一个变量记录交换两行引起的符号改变。因为将一行的 \(

标签:det,vmatrix,cdots,行列式,求值,优化,operatorname,vdots
From: https://www.cnblogs.com/liudagou/p/18219099

相关文章

  • 如何进行接口优化?如何进行接口优化?多线程的核心参数有哪些?SpringCloud使用了哪些组件?
    在快速迭代的技术领域中,持续地回顾与总结项目经验不仅是个人成长的催化剂,也是智慧积累的关键环节,本次知识积累旨在深入剖析如何进行接口优化?如何进行接口优化?多线程的核心参数有哪些?SpringCloud使用了哪些组件?一、如何优化SQL?优化SQL语句以提高查询效率和性能是一项......
  • JVM调优维护常用工具之VisualVM 可视化优化工具
    VisualVM是一个工具,它提供了一个可视界面,用于查看Java虚拟机(JavaVirtualMachine,JVM)上运行的基于Java技术的应用程序(Java应用程序)的详细信息。VisualVM对JavaDevelopmentKit(JDK)工具所检索的JVM软件相关数据进行组织,并通过一种使您可以快速查看有关多个......
  • 在Linux中,如何进行网络资源的优化?
    在Linux中进行网络资源优化,主要目标是提高网络吞吐量、降低延迟、确保稳定性和安全性。以下是一些常见的优化措施:1.调整网络参数修改TCP缓冲区大小:通过调整/proc/sys/net/core/wmem_max和rmem_max来增大发送和接收缓冲区的大小,可以提高大文件传输或高带宽链接的性能。使用sys......
  • 在Linux中,如何进行系统资源的优化?
    在Linux中进行系统资源优化是为了提高系统性能、响应速度和稳定性。这通常涉及内存管理、CPU调度、磁盘I/O、网络及进程管理等多个方面。以下是一些基本的系统资源优化策略:1.内存优化调整Swappiness值:Swappiness参数控制着Linux使用swap空间的倾向性。减少该值可以减少对swap......
  • 【MySQL】MySQL语句优化
    一、嵌套查询优化当SLQ语句存在嵌套查询时,MySLQ会生成临时表来存储子查询的结果数据,外层查询会从临时表中读取数据,待整个查询完毕后,会删除临时表,在这个过程中是非常耗时的。方案:使用JOIN语句进行联表查询来代替,提升查询性能。例如这里查询t_goods数据表中t_category字段......
  • 【MySQL】MySQL语句优化
    一、嵌套查询优化当SLQ语句存在嵌套查询时,MySLQ会生成临时表来存储子查询的结果数据,外层查询会从临时表中读取数据,待整个查询完毕后,会删除临时表,在这个过程中是非常耗时的。方案:使用JOIN语句进行联表查询来代替,提升查询性能。例如这里查询t_goods数据表中t_category字段不在t_g......
  • React中何时使用memo、useCallback、useMemo以及useRef进行性能优化
    react无法做到像vue一样自动收集依赖更新(期待react19的ReactCompiler),需要开发人员手动的进行性能优化,此时memo、useCallback、useMemo、useRef就是性能优化中的重要API本文虽然介绍可应用场景,但是正常开发中,尤其是useCallback。除非遇到性能问题或者组件库封装,亦或......
  • 得到杨辉三角某行数据算法优化
    引导注意:最佳方案在文章最后,中间为思考过程最朴实的方法:        我们将这些数据的第一行称作为杨辉三角的第0行,每行的第一个数据称作为第0个数据,以方便之后的算法        根据杨辉三角的基础性质,即第row行index个数据等于第row-1行第index数......
  • 锂电池寿命预测 | Matlab基于ALO-SVR蚁狮优化支持向量回归的锂离子电池剩余寿命预测
    目录预测效果基本介绍程序设计参考资料预测效果基本介绍【锂电池剩余寿命RUL预测案例】基于蚁狮优化和支持向量回归的锂离子电池剩余寿命预测(完整源码和数据)1、提取NASA数据集的电池容量,以历史容量作为输入,采用迭代预测的方法对未来的容量进行预测:2......
  • Redis如何进行内存优化
    控制key的数量。当使用Redis存储大量数据时,通常会存在大量键,过多的键同样会消耗大量内存。Redis本质是一个数据结构服务器,它为我们提供多种数据结构,如hash,list,set,zset等结构。使用Redis时不要进入一个误区,大量使用get/set这样的API,把Redis当成Memcached使用。对于存储相同的......