Let ${\displaystyle A}$be an ${\displaystyle n\times n}$matrix, with entries ${\displaystyle A_{0,0}=2,A_{0,1}=-1,A_{0,n-1}=1,A_{i>0,i-1}=1}$, and zero elsewhere. I wish to compute the ${\displaystyle n-1}$st (last) row of ${\displaystyle A^{k}}$, and I don't care about the other rows. Is there a fast way (faster than naive matrix multiplication or exponentiation by squaring) to compute this? 24.255.17.182 (talk) 23:05, 20 December 2016 (UTC)[reply]

Often it is convenient to diagonalize (or put in Jordan form), then raise to powers, then un-diagonalize. I have not considered whether this is nice for your example. --JBL (talk) 23:53, 20 December 2016 (UTC)[reply]

I don't think so- I can show that the characteristic polynomial is ${\displaystyle f_{m}(\lambda )=(-1)^{m}(-\lambda ^{m+1}+2\lambda ^{m}-\lambda ^{m-1}+1)}$which doesn't factorize to anything nice in general. 24.255.17.182 (talk) 00:52, 21 December 2016 (UTC)[reply]

• You might try working out by hand a few simple examples (small n, and several small values of k) and form a hypothesis about the desired row. If the hypothesis is simple enough, it just might be easy to prove by induction. Loraof (talk) 00:19, 21 December 2016 (UTC)[reply]

You may already know this, but depending on ${\displaystyle n}$and ${\displaystyle k}$, iterated multiplication could be faster than exponentiation by squaring. Right-multiplying a row vector by A requires only a left shift, two additions, and a cyclic permutation which can be handled as a renumbering of entries. Repeating this ${\displaystyle k}$times takes ${\displaystyle O(k^{2})}$time and ${\displaystyle O(nk)}$space (assuming ${\displaystyle k>n}$, ignoring factors of ${\displaystyle \log n}$, and considering that the integers grow exponentially with ${\displaystyle k}$). Exponentiation by squaring with FFT integer multiplication and ${\displaystyle O(n^{c})}$matrix multiplication would take ${\displaystyle O(n^{c}\,k\log k)}$time and ${\displaystyle O(n^{2}\,k)}$space, I think. Iterated multiplication also has a smaller constant factor not only because of the simple algorithm but also because of better locality of reference. -- BenRG (talk) 20:18, 23 December 2016 (UTC)[reply]