Geometry and the Discrete Fourier Transform

Affine transformations

The general form of an affine transformation of the plane with coordinates $x$ and $y$, can be written $$\left(\begin{array}{c}x\\ y\\ \end{array}\right) \mapsto \left(\begin{array}{cc}a&b\\ c&d\\ \end{array}\right) \left(\begin{array}{c}x\\ y\end{array}\right) + \left(\begin{array}{c}e\\ f\end{array}\right) .$$ If we view the $(x,y)$-plane as the complex plane $\cplx$, thus in terms of $z=x+\ii y$ with $\ii = \sqrt{-1}$, we have to translate the above into complex language. We see the general plane affine transformation written in complex coordinates is $$z \mapsto \lambda z + \mu \overline z + \nu$$ with $2 \lambda=(a+d)+(c-b)\ii,\ 2 \mu=(a-d)+(c+b)\ii,\ \nu\in\cplx$.

If we separate the two triangles by making the standard one larger, say lying on a circle of radius $\lambda>1$ then we get

which shows the triangle is an isosceles one with height $\sfrac34(\lambda+1)$ lying along the real axis.

The slider labelled $\lambda$ controls the radius of the outer circle. The green isosceles triangle in the middle is the average of the two triangles with labelled vertices. Note the opposite orientations of the two triangles being averaged.

If we separate the two basic triangles $\chi_1$ and $\chi_2$ by turning them in opposite directions by a turn $\ee^{\ii \alpha}$ (in the attractive terminology of Frank Morley for complex numbers of modulus 1) to make $$\begin{eqnarray} {\textstyle\sfrac12}(\ee^{\ii \alpha}\chi_1+\ee^{-\ii \alpha}\chi_2)&=& {\textstyle\sfrac12}\left\{\ee^{\ii \alpha}(1,-{\textstyle\sfrac12}+{\textstyle\sfrac{\ sqrt3}2}\ii, -{\textstyle\sfrac12}-{\textstyle\sfrac{\sqrt3}2}\ii) +\ee^{-\ii \alpha}(1,-{\textstyle\sfrac12}-{\textstyle\sfrac{\ sqrt3}2}\ii, -{\textstyle\sfrac12}+{\textstyle\sfrac{\sqrt3}2}\ii)\ right\}\cr &=& \left({\textstyle\sfrac12}(\ee^{\ii \alpha}+\ee^{-\ii \alpha}), -{\textstyle\sfrac14}(\ee^{\ii \alpha}+\ee^{-\ii \alpha})+ {\textstyle\sfrac{\sqrt3}4}\ii(\ee^{\ii \alpha}-\ee^{-\ii \alpha}) ,-{\textstyle\sfrac14}(\ee^{\ii \alpha}+\ee^{-\ii \alpha})- {\textstyle\sfrac{\sqrt3}4}\ii(\ee^{\ii \alpha}-\ee^{-\ii \alpha})\right)\cr &=&(\cos \alpha, -{\textstyle\sfrac12}\cos \alpha-{\textstyle\sfrac{\sqrt3}2}\sin \alpha, -{\textstyle\sfrac12}\cos \alpha+{\textstyle\sfrac{\sqrt3}2}\sin \alpha) ) \end{eqnarray}$$ $$\begin{eqnarray} {\textstyle\sfrac12}(\ee^{\ii \alpha}\chi_1+\ee^{-\ii \alpha}\chi_2)= (\cos \alpha, -{\textstyle\sfrac12}\cos \alpha-{\textstyle\sfrac{\sqrt3}2}\sin \alpha, -{\textstyle\sfrac12}\cos \alpha+{\textstyle\sfrac{\sqrt3}2}\sin \alpha) ) \end{eqnarray}$$ then we have achieved a splitting of the double point at $-\sfrac12$ in $\sfrac12(\chi_1+\chi_2)$ but still have a degenerate triangle on the real axis, with the second vertex at $z_1=-\sfrac12\cos \alpha-\sfrac{\sqrt3}2\sin \alpha$ and the third symmetrically placed about $-\frac12\cos\alpha$ at $z_2=-\sfrac12\cos \alpha+\sfrac{\sqrt3}2\sin \alpha$.

The green slider $\alpha$ controls the angle away from the $x$-axis that the triangles are rotated; it goes from $0$ to $2 \pi$. The linear green triangle is the average of the triangles with vertices on the unit circle. Note that the cycle $\ee^{\ii\alpha}$, $\ee^{\ii\alpha}\omega$ and $\ee^{\ii\alpha}\omega^2$ is positively oriented (counter-clockwise) and $\ee^{\ii\alpha}$, $\ee^{\ii\alpha}\omega^2$ and $\ee^{-\ii\alpha}\omega$ is negatively oriented.

The fully general case is then the addition of two arbitrarily sized and rotated standard triangles. This is a case where the interactive form of the diagram can be quite helpful.

The triangle $C$ is the average of triangles $A$ and $B$ so $C_i$ is midway between $A_i$ and $B_i$. That is, $C$ is the triangle ${\scriptstyle\frac12}(\lambda \ee^{\ii \alpha}\chi_1 +\mu \ee^{\ii \beta}\chi_2)$ for real numbers $\lambda, \mu, \alpha$ and $\beta$.

The red sliders are $\lambda$ controlling the size of the red image of the standard triangle and $\alpha$ controlling its angle of rotation. Then the blue $\mu$ and $\beta$ are the corresponding controls for the blue image of the reversed standard triangle.

The general sum of this form, with six real parameters $\lambda,\mu,\nu,\alpha,\beta,\gamma\in \reals$, is $$\lambda \ee^{\ii \alpha}\chi_1 +\mu \ee^{\ii \beta}\chi_2 + \nu \ee^{\ii \gamma}\chi_0$$ and can represent any triangle in the plane; the centre of gravity is $\nu \ee^{\ii \gamma}\chi_0$.

One can spend quite some time playing with the interactive figures for polygon superpositions.

Proof of Median Coincidence

If the vertices of a triangle are $z=(z_0,z_1,z_2)$, the midpoints of the sides are $$\begin{eqnarray} (\sfrac12(z_1+z_0),\sfrac12(z_2+z_1),\sfrac12(z_0+z_2)) &=& \sfrac12((z_1+z_0),(z_2+z_1),(z_0+z_2))\\ &=& \sfrac12(z+Jz) = \sfrac12(I + J)z, \end{eqnarray}$$ where $I$ is the identity and $J$ is the cyclic permutation $$J: (z_0,z_1,z_2) \mapsto (z_1,z_2,z_0) .$$ The points on the line from $z_0$ to $\sfrac12(z_2+z_1)$ are of the form, for some $\lambda \in \reals$ $$(1-\lambda)z_0 + \lambda {\textstyle\sfrac12}(z_2+z_1)$$ and similarly on the line from $z_1$ to $\sfrac12(z_0+z_2)$ we have, for some $\mu \in \reals$ $$(1-\mu)z_1 + \mu {\textstyle\sfrac12}(z_0+z_2).$$ The only solution for a point that lies on both lines is $$(1-{\textstyle\sfrac23})z_1 + {\textstyle\sfrac23}{\textstyle\sfrac12}(z_0+z_2) = {\textstyle\sfrac13}(z_0 + z_1 + z_2) = \chi_0 \Dot z.$$ The common intersection point of medians as the centre of gravity has become obvious.▓

Proof of other coincidences and collinearity

Other coincidence cases can be a bit more tricky but fundamentally proceed in a similar way. We need to show the Fourier transform coefficients of $\chi_1$ and $\chi_2$ both vanish. For collinearity we only need to show that $\chi_1 \Dot x$ and $\chi_2 \Dot x$ have the same absolute value.

Pentagon geometry and Jesse Douglas' pentagon construction explained

Let $\omega$ be the simplest primitive $5$th root of unity, with $\ii := \sqrt{-1}$: $$\omega = \cos\frac {2\pi}{5} + \ii \sin\frac {2\pi}{5}.$$ Note that complex conjugation acts as $\bar{\omega}_5^j = \omega_5^{5-j}$.

These are the 5 standard vectors $$\chi_0=( 1, 1, 1, 1, 1 ) \quad;\quad \chi_1=( 1, \omega_5^\strut, \omega_5^2, \omega_5^3, \omega_5^4 ) \quad;\quad \chi_2=( 1, \omega_5^2, \omega_5^4, \omega_5^\strut, \omega_5^3 ) \quad;$$

$$\chi_3=( 1, \omega_5^3, \omega_5^\strut, \omega_5^4, \omega_5^2 ) \quad;\quad \chi_4=( 1, \omega_5^4, \omega_5^3, \omega_5^2, \omega_5^\strut ).$$ which form a basis for $\cplx^5$.

Going back to examine the coordinates for $q_i$, the point obtained by extending a line from a vertex to an opposite midpoint by an extra $\frac1{\sqrt5}$, we see $$q_i = -\frac{\sqrt5}5 p_i + \frac{5+\sqrt5}{10} p_{i+2}+ \frac{5+\sqrt5}{10} p_{i+3}.$$ To establish properties, see what components of the various standard types it has. The function $q=(q_0,q_1,q_2,q_3,q_4))\in{\cplx}[{\intg}/5]$ has the harmonic expansion $$q = \sum_{k=0}^{4} (\chi_k \Dot q) \chi_k = \sum_{k=0}^{4}\hat q_k \chi_k.$$ The character $\chi_0$ is the trivial (or degenerate) character of the trivial representation, and $\hat f_{0}$ is the center of gravity of the values of $f$. The other $\hat f_{1},\hat f_{2},\hat f_{3},\hat f_{4}$ are the harmonic components of $f$.

The center of gravity is just an expression of where the geometric object is located, so we don't expect any special properties for it. But look at $\hat q_2$; we find by calculation

So $\hat q_2$ vanishes identically. Thus there is no regular pentagram component of the polygon $q$. Similarly look at $\hat q_3$, or at

We have thus shown that $q = {\hat q}_0 + {\hat q}_1 \chi_1 + {\hat q}_4\chi_4={\hat q}_0 + {\hat q}_1 \chi_1 + {\hat q}_4 \overline{\chi_1}$. This means that $q$ is an affine image of the regular convex pentagon.

Similarly the polygon $r$ constructed is the affine image of a regular pentagram, for like reasons.

Proof of Napoleon's Theorem

Again take $\omega := \omega_3^{\strut} = \frac12(-1 + \ii \sqrt3)$ until further notice, so $\omega^3 - 1 = 0 = 1 + \omega + \omega^2.$ Start by expressing the construction steps in the Napoleon theorem with the help of the characters we introduced. We need to specify an equilateral triangle constructed positively on an oriented segment. The standard unit equilateral triangle is $\chi_{3,1}=:\chi_1$. Its right-hand vertex is at the point $1\in\cplx$; we see that $\chi_1-\chi_0$ is a similar triangle shifted so that its right-hand vertex is at the origin. A diagram may help.

To shift it so that its first side is aligned positively along the horizontal $x$-axis we multiply the whole by $(\omega-1)^{-1}=3^{-1}(\omega^2-1)$ to get $3^{-1}(\omega^2-1)(\chi_1-\chi_0)$. This is clear because we want to move the vertex after the base at $0$, namely at $\omega-1$, to the point $1$, and $$(\omega -1)(\omega^2-1)=\omega^3-\omega^2-\omega+1=3.$$ Alternatively, we see immediately that $\overline{\omega-1}=\omega^2-1$ and $|\omega-1|=3$. The triangular building block we need is thus $$3^{-1}(\omega^2-1)(\chi_1-\chi_0).$$ There is an important thing to note about the constructed triangle: it is positively oriented with respect to the base interval from $0$ to $1$. It is on the left as we go from $0$ to $1$. To get the negatively oriented block on the right as we go from $0$ to $1$ we need $$3^{-1}(\omega-1)(\chi_2-\chi_0).$$

In general, to translate a whole triangular figure by a vector $z$ we have to add $z\chi_0$ to it. To rotate by a angle $\alpha$ we have to multiply by the scalar turn $\ee^{\ii\alpha}$, and to scale by a homothety $\lambda > 0$ we have to multiply by the scalar $\lambda$. For instance, if we had not multiplied by $(\omega-1)^{-1}$ just a moment ago, but only used the rotation effected by the unit vector $\{3^{-1/2}(\omega-1)\}^{-1}=3^{-1/2}(\omega^2-1)$ then we would have had to scale the building-block triangle to unit side-length by multiplying with $3^{-1/2}$.

If the segment on which we need to erect a triangle is from $z_j$ to $z_k$, then it is of length $|z_k-z_j|$ and in the direction $\arg(z_k-z_j)$ from the starting point $z_j$. Thus the triangle on the left side of the interval which is to be constructed is $$3^{-1}(\omega^2-1)(z_k-z_j)(\chi_1-\chi_0) + z_j\chi_0,$$ and the triangle on the right side is $$3^{-1}(\omega-1)(z_k-z_j)(\chi_2-\chi_0) + z_j\chi_0.$$

Finally, to find the centroid of a triangle $z=(z_0,z_1,z_2)$ we just have to take the inner product with $\chi_0$, namely $\chi_0 \Dot z$. So the centroid of the left-side resulting triangle in the last paragraph is, using the fact that the basis vectors $\chi_j$ are orthonormal, $$\begin{eqnarray*} \chi_0 \Dot( 3^{-1}(\omega^2-1)(z_k-z_j)(\chi_1-\chi_0) + z_j\chi_0) &=& -3^{-1}(\omega^2-1)(z_k-z_j) + z_j\\ &=& -3^{-1}\{(\omega^2-1)z_k-(\omega^2-1)z_j-3z_j\}\\ &=& -3^{-1}\{(\omega^2-1)z_k-(\omega^2+2)z_j\} . \end{eqnarray*}$$

Theorem 1 (Napoleon) For any nondegenerate triangle in the plane the result of constructing the centroids of equilateral triangles erected externally on the sides of the triangle is three points at the vertices of an equilateral triangle.

Proof. Let the initial triangle be $z=(z_0,z_1,z_2)$, and suppose it positively oriented. Start with externally constructed equilateral triangles. That means we need right-side building blocks. By the above remarks the externally constructed vertices are $$( -3^{-1}\{(\omega-1)z_{j+1}-(\omega+2)z_j\} , j\in \{0,1,2\}),$$ so the triangle is $$3 ^{-1}\{(1-\omega)J z+ (\omega+2)z\}.$$ To show that this is an equilateral triangle we take the inner product with $\chi_2$. We know that the original triangle has its Fourier decomposition $z=\hat z_0\chi_0+\hat z_1\chi_1+\hat z_2\chi_2$, and the basis $(\chi_j,j\in\{0,1,2\})$ is orthonormal. Now we see quickly that the $\chi_j$ are eigenvectors of $J$, namely $J\chi_j = \omega^j\chi_J$. Therefore $Jz=\hat z_0\chi_0+\omega \hat z_1\chi_1+\omega^2 \hat z_2\chi_2$. Thus $$\begin{eqnarray*} \langle\chi_2\Dot3^{-1}\{(1-\omega)J z+ (\omega+2)z\}\rangle &=&3^{-1}\{(1-\omega)\omega^2 \hat z_2+ (\omega+2)\hat z_2\}\\ &=&3^{-1}\{\omega^2-1+\omega +2\}\hat z_2 \\ &=&3^{-1}\{\omega^2+\omega +1\}\hat z_2 \\ &=& 0. \end{eqnarray*}$$ We have shown that constructing the centroids of equilateral triangles externally to the positively oriented initial triangle yields a sequence of points making up the vertices of a positively oriented equilateral triangle.

To deal with left-hand side, i.e. , ‘internal’ equilateral triangles, we just have to do a similar calculation.

Corollary The Napoleon construction provides a geometrical way to find the discrete Fourier transform of a triangle.
Proof. First for the external triangles $$\begin{eqnarray*} \chi_1\Dot(3^{-1}\{(1-\omega)J z+ (\omega+2)z\}) &=&3^{-1}\{(1-\omega)\omega \hat z_1+ (\omega+2)\hat z_1\}\\ &=&3^{-1}\{\omega-\omega^2 +\omega +2\}\hat z_1 \\ &=&3^{-1}\{-\omega^2+2\omega +2\}\hat z_1 \\ &=&3^{-1}\{-3\omega^2\}\hat z_1\\ &=& -\omega^2 \hat z_1, \end{eqnarray*}$$ and $$\begin{eqnarray*} \langle\chi_0|3^{-1}\{(1-\omega)J z+ (\omega+2)z\}\rangle &=&3^{-1}\{(1-\omega) \hat z_0+ (\omega+2)\hat z_0\}\\ &=&\hat z_0 \end{eqnarray*}$$ (which last we really already knew). Geometrically this means that the external Napoleon triangle has equal sides of lengths $\sqrt3|\hat z_1|$, and if we want to work out the argument of $\hat z_1$ then all we have to do is to rotate the first side of it back by $2\pi/3$ and flip.

From the internal Napoleon triangle we get similarly $$\begin{eqnarray*} \langle\chi_2|3^{-1}\{(1-\omega^2)J z+ (\omega^2+2)z\}\rangle &=&3^{-1}\{(1-\omega^2)\omega^2 \hat z_2+ (\omega^2+2)\hat z_2\}\\ &=&3^{-1}\{\omega^2-\omega +\omega^2 +2\}\hat z_2 \\ &=& -\omega \hat z_2, \end{eqnarray*}$$ giving us the value for $\hat z_2$. ▓

A generalization of this results from noticing that one could just as well use $N$ as $3$ above for the number of sides, $\chi_{N,k}$ for the initial $N$-gon and some other $\chi_{N,l}$-gon for the constructed figure on each side and still get the same results with careful manipulation of the indices. It is probably helpful to remark that the $N=4$ case says that constructing squares on the sides of a parallelogram gives four centers of gravity which are the vertices of a square, before the general formulation that follows. Let this theorem indicate that one can go a lot further with these methods.

Theorem 2 (Generalized Napoleon) Let $N$ be an integer greater than $2$, and $k$ and $l$ be integers between $1$ and $N-1$. For any nondegenerate affine image of a regular $(N,k)$-gon in the plane, the result of constructing the centroids of regular $(N,l)$-gons externally upon the sides of the initial $(N,k)$-gon is the set of vertices of a regular $(N,k)$-gon if $k^2=l \pmod N$; if the additional figures are constructed internally then a regular $(N,N-k)$-gon results.

Summary

We have seen that there's a relationship between some elementary geometry of the plane and the Discrete Fourier Transform: Assertions of triangle geometry are statements about the harmonics that remain after a prescribed construction, and Napoleon's Theorem gives a geometrical way of constructing a Discrete Fourier Transform of order $3$. This is just a suggestion of some ramifications of this which include relationships to polynomials, circulant matrices, interpolation and splines, Siebeck's and Marden's theorems on polynomial zeroes, and the Heisenberg-Weyl group as it occurs in signal processing.

Acknowledgements

I would like to thank Bill Casselman and David Austin for many improvements to the exposition, Davide Cervone and Robert Miner for the excellent tool MathJax, and Markus Hohenwarter and his team for the valuable Geogebra package. Mathematical Reviews and the University of Michigan have provided unparalleled access to the literature of mathematics.