Finding the matrix inverse given a solver for the matrix equation $Ax=b$

Question

So I'm given a solver that can solve for $x$ in the matrix equation $\underset{=}{A} \underline{x} = \underline{b}$ where $b$ can be anything we specify. (NB: A is an NxN matrix).

I now want to find the inverse of matrix A, $\underset{=}{A}^{-1}$, using the solver. How would i go about doing this?

My first two ideas were this, but I'm not sure if they are relevant:

1. Find the LU decomposition somehow using this solver, and then finding the inverse of U and L should be simple because of their shape and thus the inverse of A should be easy to calculate through the product of the inverses of U and L.

2. Can i use the fact that $A = R\Lambda R^{-1}$ and subsequently find the eigenvectors and eigenvalues somehow using the equation above?

Thank you very much :)

Answer 1

Your two ideas make it much too complicated. If $X$ is the inverse of $A$, $$ AX=I, $$ and $x_i$ is the $i$-th column of $X$ and $e_i$ is the $i$-th column of the identity matrix $I$ ($e_i$ is a vector of all zeros except with $1$ in the $i$-th location), then the columns $x_i$ of the inverse are defined by $$ Ax_i = e_i. $$ All you need to do is solve $n$ systems of linear equations with the vectors $e_i$ in the r.h.s..

After all, think of what it means to represent a (general, black-box) linear operator in a given basis. If the basis is $e_i$, and all you can do is compute the function $x\mapsto Ax$, the matrix elements can be computed as $$ A_{ij} = e_i^\top (Ae_j). $$ In your case, the function is $x\mapsto A^{-1}x$.