6
$\begingroup$

Let $A$ be a square $n \times n$ matrix, which is invertible. Now we want to find the $i$-th column of $A^{-1}$ and one $(i,j)-$ entry of $A^{-1}$. Is there any way to compute only a small of portion of the entries in $A^{-1}$?

$\endgroup$
4
  • 1
    $\begingroup$ Peter, do you want an exact method or an approximate one? $\endgroup$
    – Suvrit
    Apr 15, 2011 at 14:07
  • 1
    $\begingroup$ It is the solution of a system of linear equations. $\endgroup$ Apr 15, 2011 at 14:16
  • 1
    $\begingroup$ Peter, if you want specific suggestions how to do what you want to do efficiently, it will be inevitable that you specify at least how large n is (roughly), what type of matrix A is (say, many zeros, yes or no), and perhaps what the entries of A are (reals, complex, rationals, something else). Otherwise, you can an only expect general information, which you already got. $\endgroup$
    – user9072
    Apr 15, 2011 at 14:28
  • 1
    $\begingroup$ A is a real, large, sparse matrix whose entries are between 0 and 1. $\endgroup$
    – peter
    Apr 15, 2011 at 16:43

4 Answers 4

5
$\begingroup$

The inverse of a matrix is the adjoint divided by the determinant. So what you want to compute is the determinant of an $(n-1) \times (n-1)$ submatrix, divided by the determinant of your original matrix.

Asymptotically, this won't be much saving, if any, over just inverting $A$, but it might be easier to think about, or might be simpler for matrices with a special form.

Also, if you care about efficiency, remember that you should never compute a determinant, or an inverse, by summing over all $n!$ permutations! Use row reduction or, better, use a good linear algebra library.

$\endgroup$
1
  • $\begingroup$ yeah, computing $|A|$ is unwise, too costly. Any other efficient way? $\endgroup$
    – peter
    Apr 15, 2011 at 13:33
5
$\begingroup$

If you are willing to settle for an approximate answer, then have a look at the paper:

Z. Bai, M. Fahey and G. Golub, Some large-scale matrix computation problems Journal of Computational and Applied Mathematics, Volume 74, Issues 1-2, 5 November 1996, Pages 71-89. Link to PDF

That paper studies simple randomized methods for estimating

$$u^Tf(X)v,$$

where $f(X)$ is a matrix function. In your case, $f(X) = X^{-1}$. If you choose $u=e_i$ and $v=e_j$ (the standard basis vectors), then you can extract an approximation to $(X^{-1})_{ij}$.

In the meanwhile there is more related work, but if you are happy with these types of results that I can expand my answer to provide some more citations.

$\endgroup$
2
$\begingroup$

The ith column of $A^{-1}$ is $A^{-1}$ applied to the ith unit vector. So you can obtain it by solving a linear system. This question does not appear suitable for this site.

$\endgroup$
2
  • $\begingroup$ what about the (i,j)-entry of $A^{-1}$ ? $\endgroup$
    – peter
    Apr 15, 2011 at 13:33
  • 3
    $\begingroup$ actually, the question is suitable. Imagine the matrix $A$ is huge (say $10^6 \times 10^6$), then you do not necessarily want to solve a linear system if you just want to extract a few elements of the inverse. Of course, now the onus is on Peter to refine his question with more details of what exactly he is seeking. $\endgroup$
    – Suvrit
    Apr 15, 2011 at 14:16
1
$\begingroup$

To amplify on @Michael Renardi's answer: finding $x$ such that $A x = y$ (in this case, $y$ is a unit vector) is generally much faster than finding $A^{-1},$ the key words are "conjugate gradient algorithm. I do not understand the question about the $(i, j)$th entry, since once you fiund the column (or the row, by taking transposes) you can find your element.

$\endgroup$
1
  • $\begingroup$ In fact, the key words are "conjugate gradient if it is symmetric, GMRES otherwise". $\endgroup$ Apr 15, 2011 at 17:12

Your Answer

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

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