# Calculate cofactor-matrix efficiently [duplicate]

I've implemented an algorithm that can calculate the cofactor-matrix of a matrix in $$\mathcal{O}(n^5)$$.

The algorithm just step-by-step iterates over the whole matrix ($$\mathcal{O}(n^2)$$) and for every $$(i,j)$$ in the matrix, it then calculates the determinant of the "sub-matrix" (leaving off row $$i$$ and column $$j$$) by using the bareiss algorithm in $$\mathcal{O}(n^3)$$.

Is there a faster way to do this?

• Computing determinants of anything is so vastly expensive that it is almost always a good question to ask what you actually need it for, and whether what you want to do could not also be done without actually computing determinants. – Wolfgang Bangerth Feb 22 '20 at 1:12
• Your are working on integers, do I understand correctly? And you need an exact integer answer even if it is going to be astronomically huge? – Federico Poloni Feb 22 '20 at 9:45
• No, I am working with vector<vector<double>> in C++. – user34175 Feb 22 '20 at 14:31
• @chrysaetos99 then I would suggest switching to proper structures for matrices (raw double*, wrappers, external libraries), as while keeping the same asymptotic complexity, you will get the results much faster. Not sure it is your goal, though. – Anton Menshov Feb 22 '20 at 19:38
• It seems to me that this question still does not have a satisfying answer. The most interesting case is the one when the matrix is singular or almost singular, and in this case using the formula $\det(A) A^{-T}$ is either outright impossible, or otherwise it probably still is a bad idea in terms of stability. It looks like there should be an $O(n^3)$ solution even for this case. – Federico Poloni Feb 23 '20 at 11:04

I prefer to use SVD (singular value decomposition) instead of calculating inverse and determinant directly. SVD is still $$\mathcal{O}(n^{3})$$ in time complexity, but I think is much more stable. For singular decomposition of $$A$$ you have:

$$A = U \Sigma V^{T}$$

Where $$U$$ and $$V$$ are orthogonal matrices and $$\Sigma$$ is just a diagonal matrix. So:

$$|\mathrm{det}(A)| = \prod_{i} \mathrm{diag}(\Sigma)_{i}$$

Please pay attention to the abs in the above formula, cause the only thing that we know is $$\mathrm{det}(U),\mathrm{det}(V) = \pm 1$$. Also, an inverse could be calculated from SVD as because $$U$$ and $$V$$ are orthogonal matrices:

$$A^{-1} = V \Sigma^{-1} U^{T}$$

So the co-factor is:

$$\mathbf{C} = \mathrm{det}(A) A^{-T}$$

• I know that A^T is the transposed matrix, but what is meant by A^(-T)? Is it the transposed of the inverse? This also doesn't work, if det(A) = 0, right? – user34175 Feb 22 '20 at 16:52
• @chrysaetos99 $A^{-T} = (A^{-1})^T$ of course a matrix with zero determinant does not have co-factor. – Alone Programmer Feb 22 '20 at 20:34

Determinants and matrix inversion are pretty numerically unstable, but if all you are going for is speed, you can compute $$A^{-1}$$ in $$O(n^3)$$ time, then we have the cofactor matrix given by $$C = \mathrm{det}(A)(A^{-1})^T$$

• And how do you get $\mathrm{det}(A)$? Even calculating the inverse of matrix is really bad idea. – Alone Programmer Feb 22 '20 at 1:28