Calculate matrix powering given one outer product: $(x\cdot{y}^T)^k$ 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?

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