# complexity theory – Iterated multiplication of permutation matrices

It’s not in $$AC^0$$, by reduction from parity, which is not in $$AC^0$$.

Let $$x$$ be a parity input of length $$n$$.
For each bit $$x_i$$, we build an $$n times n$$ matrix $$A_i$$, s.t. $$A_i$$ is the identity matrix $$I$$ if $$x_i$$ is $$0$$. Otherwise, it’s a matrix I’ll call $$P_{12}$$ which permutes first $$2$$ elements (i.e. it’s almost $$I$$, but $$a_{11}=a_{22}=0$$ and $$a_{12}=a_{21}=1$$).

The result of the multiplication of these matrices is either $$I$$ or $$P_{12}$$.
And finding the parity of $$x$$ is equivalent to checking whether the result is $$I$$ or $$P_{12}$$.
These matrices can be built in depth $$1$$.
If we can multiply the matrices in $$O(1)$$ depth, then we can check parity in $$O(1)$$ depth, which is impossible.