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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.