Is there a polynomial sized arithmetic formula for iterated matrix multiplication?

Question

I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow up with some more details.

In particular, they describe a scheme for iterated matrix multiplication (for the purposes of this post, multiplying $n$, $n \times n$ matrices) in log space, poly "catalytic space", and polynomial time. The argument to the best of my understanding can be sketched as follows.

1. Theorem 4 (second article) says any arithmetic formula (i.e. arithmetic circuit w/ fanout 1) of depth $d$ can be computed with a program of size $4^d$ (and all the previously mentioned space guarantees). Here, "program" is in the context of register machines, and the size is the number of instructions and equals the runtime.

2. Brent et al. 1973 proved that any arithmetic formula of size $s$ can be "balanced" to have depth $O(\log s)$, so combining with (1) it has a program of size $poly(s)$

3. For some reason, I cannot find this last, implied claim in either of the articles: there is a arithmetic formula of size $s = poly(n)$ for iterated matrix multiplication. This would imply the claim made by the papers -- that IMM can be done in polynomial time with the other space bounds, but for some reason I can't find the claim explicitly written out, which suggests I am missing something.

The smallest formula I can think of for iterated matrix multiplication is "divide and conquer" on the number of matrices, and results in size $n^{O(\log n)}$, and I don't see any way to improve on this.

The first linked article says "iterated matrix product can be computed transparently by polynomial size programs", which would seem to follow by putting together 1,2, and 3, but it references an old thesis I can't find anywhere.

So, it's either the case that I've totally misread the argument, or there should exist a polynomial sized arithmetic formula for iterated matrix multiplication. Does anyone know of one?

Answer 1

After reading over everything more carefully, I think I was misunderstanding the argument a bit, and as Yuval points out, IMM can be computed transparently in poly size without having a poly size formula. The idea seems pretty straightforward too:

Everything stated previously applies to all rings, so if the elements of the matrix were $Z_2$, then we could consider the ring of $n \times n$ matrices over $Z_2$. There's clearly a $\log n$ depth formula for the product of $n$ ring elements, so we can apply theorem 4.

The only additional considerations are

1. Theorem 4 says the program will need only 3 working registers, but since each register holds an entire matrix, these registers will take up $O(n^2)$ space. This turns out to be completely fine for us, since we have polynomial catalytic space to work with.

2. In order to actually translate the program back onto our (catalytic) turing machine, we need to rewrite matrix instructions to instructions on the underlying ring ($Z_2$ for example). Luckily, this is trivial since each instruction in the form $r_i \leftarrow r_i \pm x \ast y$ becomes $n^3$ primitive instructions: $r_i^{uv} \leftarrow r_i^{uv} \pm x^{uw}y^{wv}$ for $u,v,w = 1 \ldots n$ and no extra space of any sort is used.

This seems to be roughly in agreement with the $O(n^9)$ time complexity given by the second reference from the OP -- the program size of $4^d$ from Theorem 4 combined with the $\log_2 n$ depth of the straightforward matrix multiplication formula makes an $O(n^2)$ sized program, each matrix instruction which is further broken down into $O(n^3)$ "primitive" instructions, and each instruction might take up to $O(n^3)$ time to execute on a turing machine due to the size of the inputs.