Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)

Question

The solution to this problem can be found here. It says:

To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of the first $k − 1$ and the $tj$th entry in the last matrix. Inductively, we need to maintain $k$ counters which can be done in $O(k \log n)$ space. Finally, note that using repeated squaring, we can compute $A^p$ using $O(\log p)$ matrices, which are different powers of $A$. To generate each of these matrices, we just need $A$ and a single counter. Hence the total space needed is $O(\log p \log n)$.

What I don't understand is that in the case of multiplying $k$ fixed matrices, they're part of the input tape so no space is needed for them in the work tapes. In the case of the $A^p$ computation, the intermediate results $A^{2^t}$ must be stored somewhere demanding more space. So how can this be done in $O(\log p \log n)$ space?

Thanks!

Answer 1

No. The intermediate matrices $A^{2^t}$ don't need to be stored anywhere. When you need a value, you just recompute it. This might sound very inefficient -- but remember, we're only counting the space complexity here, not the time complexity, so it's fine to take a very long time to recompute the same value many times, if that saves you some space.