2
$\begingroup$

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?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $(x y^T)^k$ = $(x y^T)^(k-1)$$(x yT)$. Could you explain why did you change the order? $\endgroup$ – MTLaurentys Aug 9 '18 at 14:26
  • $\begingroup$ $(x y^T)^k = x y^T x y^T \cdots x y^T = x ( y^T x y^T \cdots x )y^T $. $\endgroup$ – copper.hat Aug 9 '18 at 14:28
  • 1
    $\begingroup$ Oh! Thank you so much! $\endgroup$ – MTLaurentys Aug 9 '18 at 14:28
  • $\begingroup$ Matrix multiplication is associative. $\endgroup$ – copper.hat Aug 9 '18 at 14:36
  • $\begingroup$ 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. $\endgroup$ – copper.hat Aug 9 '18 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.