Let $A \in \mathbb{R}^{n \times n}$ be a non-singular matrix. Let $u, v \in \mathbb{R}^n$ be col umn vectors. Define the rank 1 perturbation $\hat{A}=A+u v^T$.
(a) Derive a necessary and sufficient condition for $\hat{A}$ to be inv ertible.
(b) Let $x, z$ and $b$ be column vectors in $\mathbb{R}^n$. Suppose one can solve $A z=b$ with $\mathcal{O}(n)$ floating-point operations (flops). Un der conditions derived in (a), design an algorithm to solve $\hat{A} x=b$ with $\mathcal{O}(n)$ flops, and provide justification for your an swer.