# Computing powers of diagonal + rank-1 matrix?

I'm using a numeric root-finder to find $$k$$ satisfying $$\|A^k x\|=c$$ where $$A$$ is a symmetric $$d\times d$$ diagonal + rank-1 matrix. How to compute $$A^k x$$ efficiently?

• For integer $$k$$, I can get the answer in $$O(k d)$$ time using iterated products.
• For general $$k$$, can use dense eigendecomposition of $$A$$ in $$O(d^3)$$ time
• Is there a way to do it faster than $$O(d^3)$$ for general $$k$$?

My $$d\approx 10000$$, $$k\in(1,10000)$$

## 1 Answer

This paper shows an algorithm to compute the eigendecomposition of symmetric diagonal-plus-rank-1 matrices in $$O(d^2)$$.

• Interesting that they don't reuse work between eigenvectors, procedure is called $d$ times independently. Feb 22 at 22:39
• Found some Matlab code from a different paper as dpr1eig.m in zenodo.org/record/7338121#.Y_eoEezMK0p Feb 23 at 17:53
• I posted this question on mathematica.SO where Henrik Schumacher gave an explanation of approaches and an implementation of Stor's paper. Feb 28 at 20:34
• By coincidence, I encountered this paper that pursues the eigendecomposition of a unitary plus rank-1 matrix in O(n) space / O(n^2) time. I don't think this captures the OP's use case, but I leave it here in the hope a future reader might find it useful: Aurentz, Jared L., et al. "Fast and backward stable computation of roots of polynomials." SIAM Journal on Matrix Analysis and Applications 36.3 (2015): 942-973. Mar 10 at 21:35