Let $A$ in $\mathbb R^{n \times n}$.
(a) Compute the number of flops needed to compute $A^k$ using matrix-matrix multiplications.
(b) Assuming that $A = VDV ^{-1}$ where $V^{-1}$ is given and $D$ is a diagonal matrix, propose a different procedure to compute $A^k$ that requires less flops. Compute the number of flops.
My attempt:
a) So we have $k$ square matrices. Computing element $a_{ij}$ of $A^k$ requires taking the dot product of row $i$ in the first matrix $A$ and column $j$ in the subsequent matrix $A$. Computing the dot product requires $n$ multiplications and $n−1$ additions. Since there are $n^2$ elements, the dot product must be computed $n^2$ times. Thus the total number of operations is $n^2(n+(n−1))=2n^3−n^2=O(n^3)$. But since we are doing the procedure $k$-times, then the number of flops $= k(2n^3 - n^2)$. Is it correct?
b) since $A = VDV ^{-1}$, then $A$ and $D$ are similar matrices, and hence $A$ and $D$ have the same set of eigenvalues, and since $D$ is a diagonal matrix, its diagonal entries $=$ its eigenvalues. Also, we have rank($A$) = rank($D$) and det($A$) = det($D$). So given all these, how to compute $A^k$ using the least number of flops? Thank you
In the first example, we're actually only performing a matrix multiplication $k - 1$ times, so it seems like the number of flops should be $(k-1)(2n^3 - n^2)$. Usually we're not too concerned about this, though. We might say that the total number of flops is $\sim 2kn^3$.
For the next part, note that $A^k = V D^k V^{-1}$, where $D^k$ is easy to compute as $D$ is diagonal! To compute $D^k$, at worst we need to do $k$ multiplications for each diagonal entry (we can actually do this in a smarter way; ask in the comments if you're interested). This amounts to $kn$ multiplications. Now we have $V^{-1}$, and we would need to find $V$ by inverting it. If you're familiar with Gaussian Elimination, we can then do this in $\sim n^3$ flops (see the computational efficiency section of the Wikipedia page I mentioned). Finally, we need to multiply the three matrices. Let us first multiply $V$ by $D$. This is easy, as we only need to scale each column by the respective diagonal entry in $D$, amounting to $n^2$ flops. Finally, we need to multiply $(VD)$ by $V^{-1}$, for an additional $2n^3 - n^2$ operations.
In total we have $$kn + n^3 + n^2 + (2n^3 - n^2) = 3n^3 + kn$$ which is better than $(k - 1) (2n^3 - n^2)$ for basically all choices of $k \geq 3$ and $n$.