5
$\begingroup$

So in class we have been discussing matrix inverses and the quickest way that I know of is to get a matrix A, and put it side by side with the identity matrix, like $[A|I_{n}]$ and apply the Gauss-Jordan algorithm until it is of the form $[I_{n}|A^{-1}$], where $A^{-1}$ will show up assuming A is invertible.

We also discussed using the formula $A^{-1}=\frac{\operatorname{adj}(A)}{\det(A)}$, however after a few examples, it was clear that this formula would take far too long to find the inverse of A as the matrix size got bigger.

Is the first method I described the quickest way to find a inverse of a matrix or is there a more efficient way?

$\endgroup$
4
  • $\begingroup$ Also, frequently you don't really need to find $A^{-1}$ in "real-world" problems. Depending on what you're doing, there are other techniques that are faster than finding the inverse using any method. $\endgroup$
    – vadim123
    May 31, 2013 at 18:31
  • $\begingroup$ For larger order matrix you might like to use iteration methods to compute matrix inverse. $\endgroup$
    – Srijan
    May 31, 2013 at 18:32
  • $\begingroup$ @vadim, faster, or at least just as fast. Not counting the fast algorithms for matrix multiplication, finding the inverse and, say, decomposing a matrix into triangular factors takes about the same amount of effort. If the matrix has a nice structure (e.g. symmetry, sparsity), then yes, inversion is slower than most other methods for solving linear systems. $\endgroup$
    – J. M. ain't a mathematician
    May 31, 2013 at 18:44
  • 2
    $\begingroup$ @Ｊ.M., how did you get a nonstandard J in your name? $\endgroup$
    – vadim123
    May 31, 2013 at 18:56

3 Answers 3

Reset to default
4
$\begingroup$

This depends on whether you're talking about "pen-and-paper" based methods, or computer-based ones.

For pen-and-paper, the Gauss-Jordan elimination is easier and less error-prone than other methods most of the time. In some special cases, the determinants might be easy to calculate because of the matrix having some special form and thus allow the inverse to be found faster -- but for general matrix, it's hard to beat the G-J approach.

On the computer, there are faster methods available (useful mainly for matrices of large dimensions); the fastest ones for general matrices run as fast as matrix multiplication can be performed.

Wikipedia has a nice list of various methods.

$\endgroup$
6
  • 2
    $\begingroup$ In practice, one does use Gaussian elimination to invert a matrix on the computer... $\endgroup$
    – J. M. ain't a mathematician
    May 31, 2013 at 18:32
  • $\begingroup$ Yes, for dense matrix of order 100000 or less, for my matrices you can not use that. $\endgroup$
    – FASCH
    May 31, 2013 at 18:41
  • 1
    $\begingroup$ @FASCH, if you're dealing with matrices that big, you already should be thinking long and hard on whether you actually need to compute an inverse. $\endgroup$
    – J. M. ain't a mathematician
    May 31, 2013 at 18:42
  • 1
    $\begingroup$ Yeah, thats "In practice" mean for me. $\endgroup$
    – FASCH
    May 31, 2013 at 18:44
  • 1
    $\begingroup$ "My matrices" are from the discretization of some 3d partial differential equation by Local Discontinuous Galerkin Method, and sorry, but now my work is under reviewers. But don't worry, in (math.nist.gov/MatrixMarket) you can find some matrices with: motivation, application, etc. If you need more of that, then tell me. $\endgroup$
    – FASCH
    May 31, 2013 at 21:46
2
$\begingroup$

It depends on context: There happen to be a number of techniques to use to find the inverse of a matrix, some of which you may not have yet learned. By paper-pencil, the Gauss-Jordan method is probably easiest, and quickest, to use.

See Methods of Matrix Inversion, in the invertible matrix entry of Wikipedia, you'll fine the methods you mention, as well as other methods for finding the inverse of an invertible matrix.

N.B. Recall: not all $n\times n$ matrices have an inverse! (So when you can easily do so, it might be a good idea to find the determinant prior to attempting to find an inverse.)

$\endgroup$
3
  • 1
    $\begingroup$ But quite often the work involved in finding the determinant would also allow you to compute the inverse (or see that it does not exist), so computing the determinant would be a waste of work. $\endgroup$
    – Tobias Kildetoft
    May 31, 2013 at 18:51
  • $\begingroup$ Yes, indeed, that's true, @Tobias, but when it's readily apparent and easy to compute the determinant, it can be a time-saver. $\endgroup$
    – amWhy
    May 31, 2013 at 18:53
  • $\begingroup$ @amWhy: Gets a +1 from me! $\endgroup$
    – Amzoti
    Jun 1, 2013 at 0:30
1
$\begingroup$

The fast way to get the inverse of the matrix $A$, is when you note that the solution of linear system $$Ax = e_i,$$ where $e_i = (0,...,0,\overbrace{1}^{i \text{ position}},0,...,0)^T$, is $x = i$ th column of the matriz $A^{-1}$. Then, in order to compute $A^{-1}$, you need to compute all its columns, and for that, you need to solve the $n$ linear systems $$Ax_i\ =\ e_i,\quad i=1,2,...,n$$ So, the velocity of compute $A^{-1}$ depends of the velocity of solve a linear system. When you use Gaussian Elimination or $LU$-Factorization, you get the Gauss-Jordan method, but you can change the solver, but for "pen-and-paper", as @Peter Košinár said, is faster Gauss-Jordan.

$\endgroup$
2
  • $\begingroup$ "Gaussian Elimination or LU-Factorization" - you speak as if these two are completely different... they're not. $\endgroup$
    – J. M. ain't a mathematician
    May 31, 2013 at 18:41
  • $\begingroup$ Of course they are not, they are equivalence. But some differents contexts you can use both in different ways. $\endgroup$
    – FASCH
    May 31, 2013 at 18:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .