# how to find one column or one entry of the matrix inversion

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

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

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.

-
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.

-

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.

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

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