Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$?

share|improve this question
1  
Peter, do you want an exact method or an approximate one? –  Suvrit Apr 15 '11 at 14:07
1  
It is the solution of a system of linear equations. –  Gerald Edgar Apr 15 '11 at 14:16
1  
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. –  quid Apr 15 '11 at 14:28
1  
A is a real, large, sparse matrix whose entries are between 0 and 1. –  peter Apr 15 '11 at 16:43

4 Answers 4

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.

share|improve this answer
    
yeah, computing $|A|$ is unwise, too costly. Any other efficient way? –  peter Apr 15 '11 at 13:33

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.

share|improve this answer

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.

share|improve this answer
    
what about the (i,j)-entry of $A^{-1}$ ? –  peter Apr 15 '11 at 13:33
1  
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. –  Suvrit Apr 15 '11 at 14:16

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.

share|improve this answer
    
In fact, the key words are "conjugate gradient if it is symmetric, GMRES otherwise". –  Federico Poloni Apr 15 '11 at 17:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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