Finding only first row in a matrix inverse

Question

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.

Answer 1

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

Answer 2

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