# 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?

• Do you mean $(x y^T)^k$? – copper.hat Aug 9 '18 at 14:16
• @copper.hat Yes! Thank you – MTLaurentys Aug 9 '18 at 14:17

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

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

• $(x y^T)^k$ = $(x y^T)^(k-1)$$(x yT)$. Could you explain why did you change the order? – MTLaurentys Aug 9 '18 at 14:26
• $(x y^T)^k = x y^T x y^T \cdots x y^T = x ( y^T x y^T \cdots x )y^T$. – copper.hat Aug 9 '18 at 14:28
• Oh! Thank you so much! – MTLaurentys Aug 9 '18 at 14:28
• Matrix multiplication is associative. – copper.hat Aug 9 '18 at 14:36
• The points don't matter to me, but I am curious why you selected the other answer which was posted 5 mins. after mine, is essentially the same and I clarified your confusion about the order change? I am not asking you to switch (don't), I am asking why. – copper.hat Aug 9 '18 at 14:41