Golub and Van Loan: Another Practice Problem

Question

I am slowing picking my way through the classic: Matrix Computations (3rd Edition) by Golub and Van Loan. I am trying to get back into the math mindset here. I have more linear algebra background than I would like to admit, but some of these practice problems are still elusive. I'm trying to make sure I am really understanding this first section. Here is problem P1.1.1:

P1.1.1 Suppose $A \in \mathbf{R}^{n{\times}n}$ and $x \in \mathbf{R}^{r}$ are given. Give a saxpy algorithm for computing the first column of $M=(A-x^{}_{1}I)\cdots(A-x^{}_{r}I)$.

I am assuming that I am supposed to first use some rules of linear algebra to rearrange the right side of the equation to reduce it to a more trivial matrix multiplication operation using the distributive properties of matrix operation. I tried expanding the right side but didn't see any way to simplify that too much.

I am also assuming that we are supposed to implement the saxpy formulation of the matrix multiplication algorithm from section 1.1.13 which explains the saxpy algorithm for computing the columns of a matrix multiplication.

However I can't quite see the key to this practice problem. Any help would be greatly appreciated.

Answer 1

This is an old question, but I recently worked through this problem, and would like to share my insight... so to make this work as a saxpy formulation, we require some column vector $C$ that will be updated with an assignment $$C := b_kA(:,k)+C$$ where we are looping over the $k$ columns of $A$, and $b_k$ is a scalar.

The way I tackled this, was to first try and find some recursive element in the original equation that could be used as $C$. So I tried to set $$C:=A+x_1I$$ initially, and then $$C := C(A+x_2I) = AC+x_2C$$ (it's easy to check that $C$ and $A$ commute). So it seems we are onto something here...if we set $B:=C$ and then $C:=x_2C$ before entering the $k$-loop, the right-hand-side above becomes $$AB+C$$ and we just need to reduce it to calculating the first column, that is $$A(:,k)B(k,1) + C(:,1)$$ (bearing in mind we need to update $B$ and $C$ in the outer loop when looping over $r$).

Putting it all together: first set

$$C := \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}$$ and then

for i = 1:r
  B := C
  C := x_i*C
  for k = 1:n
      C := A(:,k)B(k,1) + C

I tested on one problem with three terms and it seems to work ok...but if anyone picks up a problem, please let me know.