# Is there an algorithm to compute this matrix at $\frac{2}{3}n^3 + O(n^2)$ flops?

If $A$ is an $n\times n$ nonsingular matrix, and $b$ , $c$ are column vectors of length $n$. Is there an algorithm I can use to compute the matrix $W = bc^\top A^{-1}$ in $\frac{2}{3}n^3 + O(n^2)$ flops?

-

Well,

1. Decompose $\mathbf A$ with your favorite decomposition. (e.g. the LU decomposition, $\mathbf P\mathbf A=\mathbf L\mathbf U$).

2. Solve the system $\mathbf A^\top\mathbf y=\mathbf c$ with your decomposition.

3. Form the outer product $\mathbf b\mathbf y^\top$.

I leave the details, including the flop counting, to you.

It seems the hints I gave earlier wasn't sufficiently clear, so here's another:

$$\mathbf A^{-\top}=\mathbf P\mathbf L^{-\top}\mathbf U^{-\top}$$

where $\mathbf A^{-\top}$ denotes the inverse of $\mathbf A^\top$.

You should now be able to figure how to use the LU decomposition of $\mathbf A$ to generate the column vector $\mathbf y$.

-
Sorry I was actually looking for an algorithm that is $\frac{2}{3}n^3$+$O(n^2)$ not $\frac{8}{3}n^3$+$O(n^2)$ – Mark Jul 24 '12 at 6:46
As I said, do the flop counting yourself. How much flops does an LU decomposition take? A backsubstitution? Forming an outer product? – J. M. Jul 24 '12 at 6:52