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