Calculate matrix powering given one outer product: $(x\cdot{y}^T)^k$

Question

It is an exercise on the chapter one of a book. Book: "Matrix Computations 4th edition" by Golub and Van Loan.

It reads: Give an $O(n^2)$ algorithm for computing $C=(x\cdot{y}^T)^k$ where $x$ and $y$ are $n$-vectors.

I did a lot of research because I am not great at linear algebra, I am just starting learning. I know somethings: $x\cdot{y}^T$ is a matrix, so this can be translated to matrix powering. However, I believe knowing one outer product gives more information than just a given matrix. I was trying to figure out if I can use that to my benefit, but I am not sure how. I also know algorithms for fast exponentiation, but they will not help here.

I believe there is a solution, because this book seems very good and I read good reviews. I would love hints at it. Can I translate $(x\cdot{y}^T)^k$ to something more useful, for example?

Answer 1

You have

$$\left( x \cdot y^T \right)^k = x \left( y^T \cdot x\right)^{k-1} y^T$$

$y^T\cdot x$ is an inner product that requires $n$ products and $n-1$ sums. Elevate to power $k$ require $k-1$ products. Multiplying $x$ by $\left( y^T \cdot x\right)^{k-1}$ require $n$ products and finally computing the product of $x \left( y^T \cdot x\right)^{k-1}$ by $y^T$ require $n^2$ products.

In total, this is $O(n^2)$.

Answer 2

If $k=1$, then $O(n)$ operations are required.

If $k>1$ then $(x y^T)^k = x (y^T x)^{k-1} y^T = (y^T x)^{k-1} xy^T $.

$(y^Tx)^{k-1}$ takes $O(n)$ operations, and there are $n^2$ multiplications to compute $(y^T x)^{k-1} xy^T $.