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

Question

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?

Answer 1

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