# Finding only first row in a matrix inverse

Let's say I have a somewhat large matrix $M$ and I need to find its inverse $M^{-1}$, but I only care about the first row in that inverse, what's the best algorithm to use to calculate just this row?

My matrix $M$ has the following properties:

• All its entries describe probabilities, i.e. take on values between $0$ and $1$ (inclusive)
• Many of the entries are $0$, but I don't know before hand which ones
• All entries in the same row sum to $1$
• $M$'s size is on the order of $10\times10$ to $100\times100$

I need to solve this problem literally a trillion times, though, so I need an algorithm that is as efficient as possible for matrices of this size.

• As Omnomnomnom notices, it's equivlent to a linear system. If there is not much change between your trillion matrices, maybe an iteration method will work. As a starting point you will use the solution of the preceding run, and for the first, any direct method will do. – Jean-Claude Arbaut Apr 7 '15 at 22:24

You could row-reduce the augmented matrix $(M^T\mid (1,0,\dots,0)^T)$, where ${}^T$ here means transpose. This will row-reduce to $(I \mid v)$ where $v$ is the (transposed) first row of $M^{-1}$.

• Basically Gauss-Jordan-Elimination, correct? That has a complexity of O(n³). Is that the best I can do for this? – Markus A. Sep 30 '14 at 18:50
• If we don't know more about $M$, then I don't think you can exceed $O(n^3)$; Gauss-Jordan is fairly robust as a general approach. If $M$ has some additional structure (i.e. $M$ is diagonal, orthogonal, upper-triangular, sparse), then you may be able to find an algorithm tailored for that case, which provides an improvement. – Omnomnomnom Sep 30 '14 at 18:59
• Also, I think that there are iterative methods of solution, if you're content with an approximation. – Omnomnomnom Sep 30 '14 at 19:00
• An iterative method could indeed be a good way to go. The output if this calculation will be percentages and an accuracy of 1% would be sufficient. Do you have a suggestion of a specific algoritm? – Markus A. Sep 30 '14 at 19:03
• @MarkusA. Since your matrix is sparse, you might consider a sparse direct solver such as KLU or SuperLU (AFAIK Matlab uses the first one). Efficiency of this approach, however, depends on how "many" entries are (non)zero. – Algebraic Pavel Oct 1 '14 at 13:17

Solve the linear system $$M^T\boldsymbol{x}=\boldsymbol{e}_1,$$ where $${e}_1=(1,0,0,\ldots,0).$$

In general, the solution of the system $$M^T\boldsymbol{x}=\boldsymbol{e}_k,$$ with $\boldsymbol{x}\in\mathbb R$, is the $k-$th row of $M^{-1}$, while $k-$th column of $M^{-1}$ is the solution of $$M\boldsymbol{x}=\boldsymbol{e}_k.$$

• Do you have a suggestion for which algorithm is best for solving this linear system? – Markus A. Sep 30 '14 at 18:56
• Unfortunately, the fact that the right-hand side, i.e., $\boldsymbol{e}_1$, look simple and nice and with many zeroes, does not make our life easier. In other words, solving this system it is equally hard as solving it with arbitrary right-hand side. The algorithm to choose depends only on how nice the matrix $M$. Is it symmetric, is it sparse, does it have any other symmetries? – Yiorgos S. Smyrlis Sep 30 '14 at 19:03
• It is sparse, but unfortunately I don't know anything about its shape before hand... Let me add a bit of information I do know about the matrix to the question, one sec... – Markus A. Sep 30 '14 at 19:05