13
$\begingroup$

The title is the question. This technique involves using the "matrix of cofactors", or "adjugate matrix", and gives explicit formulae for the components of the inverse of a square matrix. It is not easy to do by hand for a matrix bigger than, say, $3\times 3$. For an $n\times n$ matrix, it requires computing the determinant of the matrix itself and computing $n^2$ determinants of $(n-1)\times(n-1)$ matrices. So I'm guessing it is not that useful for applications. But I would like confirmation.

I am not asking about the theoretical significance of the technique in proving theorems about matrices.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

You're right -- it has absolutely no practical relevance for computing. Even if computing the determinant was an $O(n)$ operation, the complexity of the method would be at least $O(n^3)$ and, consequently, of the same complexity as Gaussian elimination. In practice, computing the determinant of a matrix is actually of exponential complexity, making this method completely unusable.

Improve this answer
$\endgroup$
10
  • 4
    $\begingroup$ Two things I want to add: The complexity of Cramer's Rule (using determinates to calculate an inverse) is $O(n!)$ which is much much much larger than Gaussian Elimination $O(n^3)$. Also, in general, you don't want to calculate an inverse unless you absolutely have to. $\endgroup$
    – Paul
    May 27, 2013 at 2:30
  • $\begingroup$ OTOH, there might be some circumstances where Laplace expansion might be preferred, e.g. banded matrices. But indeed, in general, Laplace expansion has $O(n!)$ complexity. $\endgroup$
    – J. M.
    May 27, 2013 at 2:30
  • 3
    $\begingroup$ @Stefan, yes, Gaussian elimination can be used to compute determinants. Since $\det(\mathbf A\mathbf B)=\det(\mathbf A)\det(\mathbf B)$, and Gaussian elimination produces (triangular) factors whose determinants are easily computed, it will indeed take $O(n^3)$ effort. $\endgroup$
    – J. M.
    May 27, 2013 at 3:55
  • 1
    $\begingroup$ Yes, you are correct -- the determinant can be computed at the cost of an $LU$ decomposition. (The naive way shown in text books using the recursive expansion is exponential in $n$ -- the $n!$ complexity mentioned by Paul). But that still yields an overall complexity of $O(n^5)$ for the proposed algorithm -- far more than the Gaussian elimination, if one were to use it, and even more than iterative solvers. $\endgroup$
    – Wolfgang Bangerth
    May 27, 2013 at 4:43
  • 1
    $\begingroup$ Correct. Row reduction is one half of computing the $LU$ decomposition. It reduces $A$ to the $U$ factor. The other half of the work is doing the same operations starting from the identity matrix, yielding the $L$ matrix. It's true that you can avoid the latter if all you care about is the determinant. $\endgroup$
    – Wolfgang Bangerth
    Sep 12, 2013 at 5:43
9
$\begingroup$

I'm going against the crowd - the adjugate matrix is in fact very useful for some specialty applications with small dimensionality (like four or less), in particular when you need the inverse of a matrix but don't care about scale.

Two examples include computation of an inverse homography and Rayleigh quotient iteration for very small problems (which in addition to being simplified by use of adjugate is numerically better).

Improve this answer
$\endgroup$
1
  • $\begingroup$ I fully agree, there are some cases ( in general with small matrices ) where it helps a lot ! ( for instance, for computing barycentric coordinates in a small simplex ) $\endgroup$
    – BrunoLevy
    Nov 6, 2015 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.