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

1$\begingroup$ Peter, do you want an exact method or an approximate one? $\endgroup$ – Suvrit Apr 15 '11 at 14:07

1$\begingroup$ It is the solution of a system of linear equations. $\endgroup$ – Gerald Edgar Apr 15 '11 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 '11 at 14:28

1$\begingroup$ A is a real, large, sparse matrix whose entries are between 0 and 1. $\endgroup$ – 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 $(n1) \times (n1)$ 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.

$\begingroup$ yeah, computing $A$ is unwise, too costly. Any other efficient way? $\endgroup$ – 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 largescale matrix computation problems Journal of Computational and Applied Mathematics, Volume 74, Issues 12, 5 November 1996, Pages 7189. 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.


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

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