Grids: Why Translation Equivariance Forces Convolution
Published:
The domain and its symmetry
A grid is the domain where the data sits at regularly spaced positions: pixels in an image, samples in an audio clip, cells in a time series. Its symmetry group is translation — shift the signal and it is still the same kind of object, with the content moved.
For a length-\(n\) signal with wraparound, the shift is a matrix \(S\) with \(S_{ij} = 1\) exactly when \(j = i - 1 \pmod n\). Applying \(S\) moves every entry one place along.
The blueprint asks for a layer \(L\) that is equivariant: shifting then transforming equals transforming then shifting.
That is the whole specification. Now see what it forces.
The constraint pins the matrix down
Write out \(LS = SL\) entrywise. Both sides are matrices, and comparing entry \((i,j)\) gives
Every entry equals the one diagonally up-left from it. So the matrix is constant along each diagonal, and is determined entirely by its first row — there are \(n\) free numbers, not \(n^2\). A matrix of this shape is called circulant, and multiplying a vector by a circulant matrix is exactly a (circular) convolution with the kernel given by that first row.
Verified by exhaustion
The argument above is short enough to check completely on a small case. Take \(3 \times 3\) matrices with entries in \(\{0,1\}\) — there are \(2^9 = 512\) of them — and test every one against the 3-cycle shift.
| count | |
|---|---|
| binary \(3\times3\) matrices | 512 |
| that commute with the cyclic shift | 8 |
| of those, circulant | 8 |
Exactly 8, and every one of them circulant. That is \(2^3\): one free binary value per diagonal, which is precisely the “determined by its first row” claim. Commuting with the shift and being a convolution are the same condition, with nothing in between.
A second check in the other direction: take a genuine circulant matrix, perturb a single entry, and it stops commuting. The property is rigid — it is not approximately satisfied by matrices that are approximately convolutions.
What the theorem actually gives you
Weight sharing. The \(n^2 \to n\) parameter reduction is not a compression heuristic. It is the dimension of the space of equivariant maps. There are no other equivariant linear layers to find.
Locality is a separate assumption. Translation equivariance alone gives you a full-width convolution — the first row can be dense. Restricting the kernel to a small window is an additional prior about how far interactions reach, imposed for efficiency and because it is usually true of images. Two constraints, often conflated: equivariance gives weight sharing, locality gives the small kernel. The CNN chapter in Book 0 works through the consequences of the second one.
Equivariance, then invariance. Stacked convolutions keep the representation equivariant, so a feature that appears at a shifted location produces a shifted activation. Classification needs the shift gone entirely, and that is what global pooling supplies — the invariant readout the blueprint calls for at the end.
✅ Key Takeaways
- The requirement is one equation: \(LS = SL\), the layer commutes with the shift.
- Entrywise it forces \(L_{i,j} = L_{i-1,j-1}\) — constant along diagonals, so circulant, so a convolution.
- Verified exhaustively: of 512 binary \(3\times3\) matrices, exactly 8 commute with the cyclic shift and all 8 are circulant. Perturbing one entry of a circulant matrix breaks the property.
- Weight sharing is the dimension of the equivariant space, not a compression trick.
- Locality is a separate assumption. Equivariance alone permits a full-width kernel.
- A convolution is equivariant to translation and to nothing else — not rotation, not scale.
References
- Bronstein, M. M., Bruna, J., Cohen, T., & Veličković, P. (2021). Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. arXiv:2104.13478.
- Joshi, C. K. (2025). Transformers are Graph Neural Networks. arXiv:2506.22084.