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