# Powers of convergent DPR1 matrices in $O(d)$ time?

Suppose $$u$$,$$v$$ are vectors and $$A$$ is a convergent $$d\times d$$ diagonal + rank-1 matrix.

How do I estimate $$u^T A^k v$$ in $$O(d)$$ time?

Powers of convergent diagonal $$D$$ can be computed in $$O(d)$$ time by utilizing Laplace transform. For a general DPR1 matrix, there's $$O(d^2)$$ algorithm but I need something that works much faster.

It is not necessary to compute $$A^k$$ in your case. You can do a matrix-vector product with $$A=D+pq^T$$ in about $$5d$$ operations, and so multiplying with $$A^k$$ via $$A^k v = A (A (A \cdots (Av)))$$ is going to cost you $$5kd$$ operations. The last dot product, $$u^T A^k v$$ is going to add $$2d$$ operations to that, for a total of $$(5k+2)d$$.

Assuming $$k\ll d$$, this is likely optimal. If $$k\gtrsim d$$, then you're already in the $$O(d^2)$$ case and the Laplace transform case is probably going to win.

• Yes I'm looking at k>>d, but wasn't clear how to generalize the Laplace approach to dpr1 case. Commented Mar 10, 2023 at 4:15
• I see, tough. Can you compute the eigenvectors of $A$ in better than $O(d^2)$? If so, you can expand $u,v$ in terms of these eigenvectors, and go from there. Commented Mar 10, 2023 at 5:13
• It seems you can get a single eigenvector in O(d), but full eigendecomposition needs d^2 Commented Mar 10, 2023 at 5:24