Let x$,$ y in Rm and let k be a positive

integer. Describe an ecient algorithm to compute the matrix C $=($xyT$)$k$.$ Note that

if you simply form xyT and take its kth power, the computational cost will be in the

order of k $$ m$3$ since xyT is an m $\backslash$times m matrix. Your algorithm should avoid this m$3$

computational complexity. What is the computational complexity of your algorithm?

Hint: The computational cost of A $+$ B for A$,$ B in Rm$\backslash$times n is mn$,$ of $\backslash$alpha A for $\backslash$alpha in R and

A in Rm$\backslash$times n is mn$,$ and of AB for A in Rm$\backslash$times n and B in Rn$\backslash$times k is in the order of mnk$.$