# Matrix multiplication circuit

I am trying to understand which operations are computable by an $$\texttt{NC}^1$$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector or if the circuit will necessarily be in $$\texttt{NC}^2$$.

• Doesn't it have an arithmetic circuit of constant depth? That would imply it's in $\texttt{NC}^1$, I believe. Commented Jul 1, 2023 at 3:38

Say you have $$A\in \mathbb{F}_p^{m\times n}$$, and $$s\in\mathbb{F}_p^n$$. We want to compute $$As\in\mathbb{F}_p^m$$. Note that
1. We can split this into $$m$$ computations of $$\langle A_i, s\rangle$$, where $$A_i$$ are the rows of $$A$$, i.e. it is $$m$$ $$n$$-dimensional inner products
2. Each inner product can be computed in $$\log_2(n)$$ depth using $$O(n)$$ processors, essentially via putting each summand in $$\langle A_i, s\rangle = \sum_{j = 1}^n A_{ij}s_j$$ on the leaf of a full binary tree, and having each internal node sum the results of its two children. The root will then contain $$\langle A_i, s\rangle$$.
In total, with $$O(mn)$$ processors, we should be able to determine it in depth $$O(\log n)$$, provided the underlying arithmetic in $$\mathbb{F}_p$$ can be done in constant depth, which seems like a reasonable assumption. This would put it in $$\mathsf{NC}^1$$.