Dihedral Group D4

The dihedral group $D_4$ is the symmetry group of the square. It is the subgroup of $O(2)$ that maps a square pixel grid onto itself. It has 8 elements, generated by a rotation $r$ by $90°$ and a reflection $f$:

$$D_4=\{e,r,r^2,r^3,f,rf,r^{2}f,r^{3}f\},r^4=f^2=e,fr=r^{-1}f=r^{3}f.$$

Cayley table (row $\cdot$ column):

$\cdot$	$e$	$r$	$r^2$	$r^3$	$f$	$rf$	$r^{2}f$	$r^{3}f$
$e$	$e$	$r$	$r^2$	$r^3$	$f$	$rf$	$r^{2}f$	$r^{3}f$
$r$	$r$	$r^2$	$r^3$	$e$	$rf$	$r^{2}f$	$r^{3}f$	$f$
$r^2$	$r^2$	$r^3$	$e$	$r$	$r^{2}f$	$r^{3}f$	$f$	$rf$
$r^3$	$r^3$	$e$	$r$	$r^2$	$r^{3}f$	$f$	$rf$	$r^{2}f$
$f$	$f$	$r^{3}f$	$r^{2}f$	$rf$	$e$	$r^3$	$r^2$	$r$
$rf$	$rf$	$f$	$r^{3}f$	$r^{2}f$	$r$	$e$	$r^3$	$r^2$
$r^{2}f$	$r^{2}f$	$rf$	$f$	$r^{3}f$	$r^2$	$r$	$e$	$r^3$
$r^{3}f$	$r^{3}f$	$r^{2}f$	$rf$	$f$	$r^3$	$r^2$	$r$	$e$

Structure. $D_4$ is non-abelian. It contains the cyclic rotation subgroup $C_4=\{e,r,r^2,r^3\}$ (index 2, normal) and four reflections: two across the axes and two across the diagonals. It can also be generated by two reflections, for example $f$ and the transpose (reflection across a diagonal). Their product is a rotation.

Action on filters. On a $(2k+1)\times (2k+1)$ filter centred at the origin, $D_4$ acts by rotating and flipping the array (rot90, reverse, transpose). For a point at offset $(i,j)$, the orbit has

• size 1 for the centre,
• size 4 for points on an axis ($j=0$) or a diagonal ($|i|=|j|$),
• size 8 otherwise.

This orbit structure determines the dimension of invariant filter spaces (see Invariant Filter Banks).

References

1. D. S. Dummit, R. M. Foote (2004). Abstract Algebra, 3rd ed. Wiley. ISBN 978-0-471-43334-7
2. T. Cohen, M. Welling (2016). Group Equivariant Convolutional Networks. ICML 2016. arXiv:1602.07576