核心概述
矩阵求逆（Matrix Inverse）：对非奇异方阵 A 求 A^{-1} 使 A·A^{-1}=I，常用高斯–约当消元法，实数域配部分主元，模素数域用逆元，时间复杂度 O(n^3)。
原文引述
Description: Compute A^{-1} via Gauss–Jordan elimination (row operations) in-place. Requires det(A)≠0. Over reals: partial pivoting; over modulo prime: use modular inverses. Time: O(n^3) Status: tested ——摘自本节点现有英文注释
展开阐述
-
函数/接口（据实现）
- template
vector<vector > inv(vector<vector > A) - 输入 n×n 矩阵 A，若可逆返回 A^{−1}；否则可抛异常或返回空。
- bool invertible(const Mat& A)：返回 A 是否可逆（可选）。
- 依赖：模数域下的 088-数论-模逆、091-数论-模幂、094-数论-模运算；实数域的数值稳定技巧。
- template
-
核心算法（Gauss–Jordan）
- 构造增广矩阵 [A | I]（n×2n）。
- 对 i = 0..n−1：
- 选取主元行 p（|A[p][i]| 最大或任一非零）；若 A[p][i]=0 ⇒ A 奇异。
- 若 p≠i，交换第 i 与 p 行（实数版需记录行交换符号，但求逆不关心 det）。
- 将主元缩放为 1：第 i 行除以 piv（模域乘 inv(piv)，实数域乘 1/piv）。
- 对所有 j≠i，消去第 j 行的第 i 列：row_j ← row_j − A[j][i]·row_i。
- 最终左侧变为 I，右侧即为 A^{−1}（原地操作时直接覆盖原矩阵）。
-
数值与实现注意
- 实数域：
- 部分主元（按列最大值）选主元，避免除以小数。
- 浮点误差可能导致“接近奇异”矩阵；对病态矩阵应改用 SVD 或 QR。
- 结果可再乘 A 检查是否接近 I。
- 模数域（素数 p）：
- 所有除法改为乘逆元（见 088-数论-模逆）；需保证主元非零。
- 模运算统一用 094-数论-模运算 的规约与乘法。
- 原地实现：
- 可以用两个矩阵或原地增广；原地可节省内存但增加复杂度。
- 实数域：
-
输出语义
- 返回 n×n 矩阵 B，若 A 可逆则 B=A^{−1}；否则返回空或报错。
-
复杂度
- O(n^3) 次乘加/除法；空间 O(n^2)（原地增广）或 O(n^2) 临时。
-
使用与注意
- 需先判断可逆性：det(A)≠0（见 097-数值算法-行列式、103-数值算法-整数行列式）。
- 对稀疏矩阵可考虑特殊结构（如三角矩阵、带状矩阵）的逆法。
- 与线性方程组的关系：A^{−1}·b 为 Ax=b 的解（见 114-数值算法-线性方程求解）。
- 模逆矩阵（modular inverse）见 108-数值算法-模逆矩阵，常在密码学中直接需求。
- 大整数精确求逆：可用 Bareiss 法求 det，再结合伴随矩阵或用 CRT 合并。