# Given LU decomposition of matrix A, How to solve $(A-uv^T)x=b$?

Homework disclaimer... 9 tasks for homework, out of which 6 required, out of which I can solve 4 but have no idea what to do with the other 2. This is one of these 2.

Given the decomposition $$PA=LU$$ of a nonsingular matrix $$A\in \mathbb{R}^{N\times N}$$, give an algorithm to solve the equation: $$Mx=b$$ where $$M=A-uv^T$$ and $$u,v\in\mathbb{R}^N$$. In addition, the algorithm has to determine whether $$M$$ is singular. Estimate computational complexity of your algoritm depending on $$N$$.

Quite clearly, it is required to come with something smarter than "Use the standard LU decomposition of $$M$$, which is $$\operatorname{O}(N^2)$$"...

With shame I admit I don't know where to start. Could you hint me the right track?

## 1 Answer

$$Mx=b$$
$$(A-uv^T)x=b$$
$$Ax-uv^Tx = b$$
$$Ax = b + u(v^Tx)$$

Computing $$v^Tx$$ is $$O(n^2)$$ since $$v^T$$ is $$1 \times n$$ and $$x$$ is $$n \times n$$
Computing $$u(v^Tx)$$ is $$O(n^2)$$ since $$u$$ is $$n \times 1$$ and $$(v^Tx)$$ is $$1 \times n$$

Computing $$y = b + u(v^Tx)$$ is $$O(n^2)$$
Now, solving $$Ax=y$$ using $$PA=LU$$ is $$O(n^2)$$ So, total complexity is O(n^2)

Hope this helps.