For $n \in \mathbb{N}$, let $\mathcal{X}_n = \{x_{i,j} : i, j \in [n]\}$ be the entries of an $n \times n$ matrix of variables. The group $\Gamma_n = \mathbf{Sym}_n \times \mathbf{Sym}_n$ acts on $\mathcal{X}_n$ by permuting rows and columns independently, $(\sigma, \tau)\, x_{i,j} = x_{\sigma(i), \tau(j)}$, and on the disjoint union $[n] \uplus [n]$ of a copy of $[n]$ indexing the rows (the left side) and a copy indexing the columns (the right side).

Let $C$ be an algebraic circuit with variables $\mathcal{X}_n$. A permutation $\sigma$ of the gates of $C$ extends $\gamma \in \Gamma_n$ if it preserves the labels of internal gates and the multiplicities of wires, $m(\sigma g, \sigma h) = m(g, h)$, and maps every input gate labelled by a variable $x$ to a gate labelled by $\gamma x$ and every input gate labelled by a constant to a gate labelled by the same constant. Such permutations are the circuit automorphisms extending $\gamma$.

The circuit $C$ is matrix-symmetric if every $\gamma \in \Gamma_n$ extends to a circuit automorphism, and rigid if every $\gamma \in \Gamma_n$ extends to a unique circuit automorphism. Let $\mathbf{Aut}_\Gamma(C)$ be the group of circuit automorphisms extending some element of $\Gamma_n$. The orbit size of $C$ is

the maximum taken over all gates $g$ of $C$.