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

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!

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.
• Thank you very much for your kind reply. If the intermediate matrices don't need to be stored anywhere, I don't understand the algorithm that let compute $A^p$ in $O(\log n\log p)$ space. – Pierrot Dec 10 '19 at 19:06