代数余子式
给定 \(n\) 阶方阵 \(A=(a_{ij})\)，定义 \(a_{ij}\) 的余子式 \(M_{ij}\) 为 \(A\) 划去第 \(i\) 行第 \(j\) 列后的行列式，\(a_{ij}\) 的代数余子式 \(A_{ij}=(−1)^{i+j}M_{ij}\) 。
代数余子式可以用于行列式的求值，比如按第 \(r\) 行展开：
\[\det A=\sum_{c=1}^na_{rc}A_{rc} \]按第 \(c\) 列展开是同理的。
伴随矩阵
定义
在 \((1)\) 式中，如果把 \(a_{rc}\) 中的 \(r\) 替换成 \(i≠r\)，则该乘积对应了将 \(A\) 的第 \(i\) 行替换成第 \(r\) 行后的行列式——该行列式有两行相等，所以它等于 \(0\) 。
所以我们有 \(\sum_{c=1}^na_{ic}A_{jc}=\det A \cdot [i=j]\)，把它写成矩阵乘法就是：
\[A(A_{ij})^{\mathrm T}=\det A \cdot I_n \]我们定义 \(A^*=(A_{ij})^{\mathrm T}\) 是 \(A\) 的伴随矩阵。
同样的结论对列也成立，所以 \(AA^*=A^*A=\det A \cdot I_n\) 。
计算
-
如果 \(r(A)=n\)，用高斯消元法分别求出 \(\det A\) 和 \(A−1\)，\(A^*=\det A \cdot A^{-1}\) 。
-
如果 \(r(A)⩽n−2\)，\(A\) 的任意 \(n−1\) 阶子式都为 \(0\)，所以 \(A^*=O\) 。
-
如果 \(r(A)=n−1\):
假设 \(A\) 的列向量组为 \(\vec{c}_{1}, \vec{c}_{2}, \ldots, \vec{c}_{n}\) 。
由它们线性相关，可知存在不全为 \(0\) 的实数 \(q_{1}, q_{2}, \ldots, q_{n}\) 满足 \(\sum_{i=1}^{n} q_{i} \vec{c}_{i}=\overrightarrow{0}\) 。不妨设 \(q_{c} \neq 0\) 。
考虑同行两余子式 \(M_{r i}\) 和 \(M_{r c}\) 的关系，不妨讨论 \(i<c\) 的情况，\(i>c\) 类似。不难发现，如果我们将 \(M_{r i}\) 的第 \(i\) 至 \(c-2\) 列向右推移，而第 \(c-1\) 列移动到第 \(i\) 列，唯一的不同点是 \(M_{r i}\) 的第 \(i\) 列为 \(\vec{c}_{c}\) 删去第 \(r\) 行，\(M_{r c}\) 的第 \(i\) 列为 \(\vec{c}_{i}\) 删去第 \(r\) 行。
联系上述线性相关式，可设 \(M^{\prime}\) 表示在 \(M_{r i}\) 进行推移的基础上，把第 \(i\) 列乘以 \(q_{c \prime}\) 并与 \(M_{r c}\) 的第 \(i\) 列的 \(q_{i}\) 倍相加，所得到的 \(n-1\) 阶行列式。
那么 \(M^{\prime}=q_{c}(-1)^{c-i} M_{r i}+q_{i} M_{r c}\) 。
最后，将 \(M^{\prime}\) 的第 \(i\) 列依次加上其对应 “原行列式的第 \(j \notin\{i, c\}\) 列” 的列的 \(q_{j}\) 倍。
这样，\(M^{\prime}\) 的值不变，而第 \(i\) 列全为 \(0\) 。这说明了 \(q_{c}(-1)^{c-i} M_{r i}+q_{i} M_{r c}=M^{\prime}=0\) 。
所以
\[q_{c} A_{r i}-q_{i} A_{r c}=(-1)^{r+c}\left(q_{c}(-1)^{c-i} M_{r i}-q_{i} M_{r c}\right)=0 \]即
\[A_{r i}=\frac{q_{i}}{q_{c}} A_{r c} \]同样的结论对列也成立。
于是对于列向量 \(\vec{p}=\left(p_{1} p_{2} \cdots p_{n}\right)^{\mathrm{T}}\) 和行向量 \(\vec{q}=\left(q_{1} q_{2} \cdots q_{n}\right)\) 使得 \(A\vec{p}=\overrightarrow{0}, \vec{q} A=\overrightarrow{0}\) ，不妨设 \(p_{r}, q_{c} \neq 0\) ，就有 \(A_{i j}=\frac{p_{i} q_{j}}{p_{r} q_{c}} A_{r c}\) 。
\(\vec{p}\) 与 \(\vec{q}\) 都可以通过高斯消元法解方程组解出，而代数余子式 \(A_{r c}\) 也可以通过高斯消元法求出。
综上所述，求一个矩阵的伴随矩阵，时间复杂度为 \(O\left(n^{3}\right)\) 。
标签：prime,det,矩阵,ij,vec,代数,余子式 From： https://www.cnblogs.com/A-Quark/p/16600271.html