Solve the problems for your appropriate course track. Problems probe understanding of the definitions and results from the module on floating point arithmetic and linear algebra. Formulate your answers clearly, cogently, and include a concise description of your approach. Each question is meant to be completely answere within five minutes. Allowed test time is 50 minutes.

1Common problems

1. Prove that the inverse of a rank-1 perturbation of $𝑰$ is itself a rank-1 perturbation of $𝑰$, namely

   ${\displaystyle {(𝑰+𝒖{𝒗}^{\ast })}^{-1}=𝑰+\theta 𝒖{𝒗}^{\ast }.}$

   Determine the scalar $\theta$.

   Solution. Self-evident for $𝒖=𝟎$ or $𝒗=𝟎$. Carry out multiplication

   ${\displaystyle (𝑰+𝒖{𝒗}^{\ast }){(𝑰+𝒖{𝒗}^{\ast })}^{-1}=(𝑰+𝒖{𝒗}^{\ast })(𝑰+\theta 𝒖{𝒗}^{\ast })=𝑰+(1+\theta )𝒖{𝒗}^{\ast }+\theta 𝒖{𝒗}^{\ast }𝒖{𝒗}^{\ast }.}$

   Note that $𝒖{𝒗}^{\ast }𝒖{𝒗}^{\ast }=\left({𝒗}^{\ast }𝒖\right)𝒖{𝒗}^{\ast }$, ${𝒗}^{\ast }𝒖\in ℂ$.$$ Impose condition

   ${\displaystyle 𝑰+(1+\theta +\theta {𝒗}^{\ast }𝒖)𝒖{𝒗}^{\ast }=𝑰\Rightarrow \theta =-\frac{1}{1+{𝒗}^{\ast }𝒖}.}$

2. Determine the rank of $𝑩={𝑨}^{-1}𝒖{𝒗}^{\ast }$.

   Solution. Denote $𝒘={𝑨}^{-1}𝒖$ to obtain $𝑩=𝒘{𝒗}^{\ast }$, and $\mathrm{rank}\left(𝑩\right)=1$, $C\left(𝑩\right)=⟨𝒘⟩$.

3. Write the inverse ${(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })}^{-1}$ as a rank-1 perturbation of $𝑰$.

   Solution. Apply above to obtain

   ${\displaystyle 𝑰=𝑰-\frac{𝒘{𝒗}^{\ast }}{1+{𝒗}^{\ast }𝒘}=𝑰-\frac{{𝑨}^{-1}𝒖{𝒗}^{\ast }}{1+{𝒗}^{\ast }{𝑨}^{-1}𝒖}}$

4. Consider $𝑪=𝑨+𝒖{𝒗}^{\ast }=𝑨(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })$. Write ${𝑪}^{-1}$ as a rank-1 perturbation of ${𝑨}^{-1}$.

   Solution. Apply above to obtain

   ${\displaystyle 𝑪={(𝑰+{𝑨}^{-1}𝒖{𝒗}^{\ast })}^{-1}{𝑨}^{-1}={𝑨}^{-1}-\frac{{𝑨}^{-1}𝒖{𝒗}^{\ast }{𝑨}^{-1}}{1+{𝒗}^{\ast }{𝑨}^{-1}𝒖}.}$

2Track 1

1. A procedure is available to compute $𝒚={𝑨}^{-1}𝒙$ in $𝒪\left(m\right)$ operations, $𝑨\in {ℝ}^{m\times m}$. Write an efficient algorithm to compute $𝒛={(𝑨+𝒖{𝒗}^{\ast })}^{-1}𝒙$.

   Solution. In the following solveA(x) computes $𝒚={𝑨}^{-1}𝒙$ in $𝒪\left(m\right)$ operations. Write $𝒛$ as

   ${\displaystyle 𝒛={𝑨}^{-1}𝒙-\frac{{𝑨}^{-1}𝒖{𝒗}^{\ast }{𝑨}^{-1}𝒙}{1+{𝒗}^{\ast }{𝑨}^{-1}𝒖}.}$

   Algorithm with operation count for each step

   Algorithm

   Input: $𝒙,𝒖,𝒗$

   $𝒔=\mathrm{solveA}\left(𝒙\right)$	$𝒪\left(m\right)$
   $a={𝒗}^{\ast }𝒔$	$𝒪\left(m\right)$
   $𝒕=\mathrm{solveA}\left(𝒖\right)$	$𝒪\left(m\right)$
   $b={𝒗}^{\ast }𝒕$	$𝒪\left(m\right)$
   $𝒛=𝒔-$	$𝒪\left(m\right)$

2. Determine the operation count for the above algorithm.

   Solution. From above total operation count is $𝒪\left(5m\right)$, i.e., rank-1 perturbation of a known coordinate transformation costs $\sim 5m$ FLOPS.

3Track 2

1. Let $𝑨\in {ℝ}^{m\times m}$. Determine the relationship between the singular values of $𝑨$ and the eigenvalues of

   ${\displaystyle 𝑿=\left[\begin{array}{ll}𝟎& 𝑨\\ {𝑨}^T& 𝟎\end{array}\right].}$

   Solution. SVD of $𝑨=𝑼𝚺{𝑽}^T$. Since $𝑿$ is symmetric, it is unitarily diagonalizable, $\exists 𝑸\in {ℝ}^{2m\times 2m}$ orthogonal such that

   ${\displaystyle 𝑿=𝑸𝚲{𝑸}^T}$

   Consider simplest case when $m=1$, $𝑨=\left[1\right]$ with SVD $𝑨=\left[1\right]\left[1\right]\left[1\right]$

   ${\displaystyle 𝑿=\left[\begin{array}{ll}0& 1\\ 1& 0\end{array}\right].}$

   Compute eigendecomposition

   ${\displaystyle p_{𝑿}\left(\lambda \right)=\det (\lambda 𝑰-𝑿)=\left|\begin{array}{ll}\lambda & -1\\ -1& \lambda \end{array}\right|={\lambda }^2-1}$ ${\displaystyle 𝑿=\frac{1}{\sqrt{2}}\left[\begin{array}{ll}-1& 1\\ 1& 1\end{array}\right]\left[\begin{array}{ll}-1& 0\\ 0& 1\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{ll}-1& 1\\ 1& 1\end{array}\right]}$

   The above suggests for $m>1$

   ${\displaystyle 𝑸=\frac{1}{\sqrt{2}}\left[\begin{array}{ll}-𝑼& 𝑽\\ 𝑽& 𝑼\end{array}\right].}$

   Verify orthogonality of $𝑸$

   ${\displaystyle {𝑸}^T𝑸=\frac{1}{2}\left[\begin{array}{ll}-{𝑼}^T& {𝑽}^T\\ {𝑼}^T& {𝑽}^T\end{array}\right]\left[\begin{array}{ll}-𝑼& 𝑼\\ 𝑽& 𝑽\end{array}\right]=\frac{1}{2}\left[\begin{array}{ll}{𝑼}^T𝑼+{𝑽}^T𝑽& -{𝑼}^T𝑼+{𝑽}^T𝑽\\ -{𝑼}^T𝑼+{𝑽}^T𝑽& {𝑼}^T𝑼+{𝑽}^T𝑽\end{array}\right]=\left[\begin{array}{ll}𝑰& 𝟎\\ 𝟎& 𝑰\end{array}\right],}$

   since ${𝑼}^T𝑼={𝑽}^T𝑽=𝑰$ (orthogonal matrices in SVD). Verify eigenvalue relationship

   ${\displaystyle 𝑿=\frac{1}{2}\left[\begin{array}{ll}-𝑼& 𝑼\\ 𝑽& 𝑽\end{array}\right]\left[\begin{array}{ll}-𝚺& 𝟎\\ 𝟎& 𝚺\end{array}\right]\left[\begin{array}{l}\begin{array}{ll}-{𝑼}^T& {𝑽}^T\\ {𝑼}^T& {𝑽}^T\end{array}\end{array}\right]\Rightarrow }$ ${\displaystyle 𝑿=\frac{1}{2}\left[\begin{array}{ll}-𝑼& 𝑼\\ 𝑽& 𝑽\end{array}\right]\left[\begin{array}{ll}𝚺{𝑼}^T& -𝚺{𝑽}^T\\ 𝚺{𝑼}^T& 𝚺{𝑽}^T\end{array}\right]=\left[\begin{array}{ll}𝟎& 𝑼𝚺{𝑽}^T\\ 𝑽𝚺{𝑼}^T& 𝟎\end{array}\right]}$

   It results that eigenvalues of $𝑿$ are ${\lambda }_i=\pm {\sigma }_i$, with ${\sigma }_i$ the singular values of $𝑨$

2. Determine the relationship between the singular vectors of $𝑨$ and the eigenvectors of $𝑿$.

   Solution. From above, eigenvectors are

   ${\displaystyle 𝑸=\frac{1}{\sqrt{2}}\left[\begin{array}{ll}-𝑼& 𝑽\\ 𝑽& 𝑼\end{array}\right].}$