Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|

Geometry and the Discrete Fourier Transform

We'll show that there's a relationship between some elementary geometry of the plane and the Discrete Fourier Transform, then explore some ramifications of this for polynomials, circulant matrices and interpolation ...

Patrick D. F. Ion
Mathematical Reviews
ion at ams.orgemail

Email to a friendMail to a friend Print this articlePrint this article

Continuing from: Introduction

Geometry with the Discrete Fourier Transform

The pentagon construction explained

Why does the above work? It can be explained by examining this construction with a really simple example of what can be thought of as a Geometrical Fourier Transform. In this case it's the Discrete Fourier Transform of order 5. Let $\omega_k$ be the simplest primitive $k$th root of unity, with $\ii := \sqrt{-1}$: $$ \omega_k = \cos\frac {2\pi}k+ \sin\frac {2\pi}k \ii. $$ The standard convex regular pentagon can be taken to be the ordered set of points $$ (\omega_5^0,\omega_5^1,\omega_5^2,\omega_5^3,\omega_5^4) =(1,\omega_5^{\strut},\omega_5^2,\omega_5^3,\omega_5^4). $$ The standard regular star pentagon, or pentagram, can be taken to be the ordered set of points $$ (\omega_5^{2\times0},\omega_5^{2\times1},\omega_5^{2\times2}, \omega_5^{2\times3},\omega_5^{2\times4}) =(1,\omega_5^2,\omega_5^4,\omega_5^1,\omega_5^3), $$ which is the result of taking every other point starting from $1$. Note that complex conjugation acts as $\overline{\omega_5^j} = \omega_5^{5-j}$. We'll do the case $n=5$ of the starting construction first, so take $\omega := \omega_5^{\strut}$ until further notice.

Going back to examine the coordinates for $q_i$ 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 of the shape of a pentagon we try to see what components of the various standard types it has. The general fact is that any plane pentagon can be written as a linear superposition, with complex coefficients, of the standard polygonal forms with $5$ points. The 5 basic forms are:

  • a degenerate collection of five points Pentagon chi0
  • the standard regular convex pentagon Pentagon chi1
  • the standard regular star pentagon Pentagon chi2
  • the reversed regular star pentagon Pentagon chi3
  • the reversed regular convex pentagon Pentagon chi4

‘Standard’ means consisting of points on the unit circle, and ‘reversed’ means the standard form described in the opposite orientation. We will also refer to the reversed forms of the figures as their opposites, since they have the opposite orientation. The four non-degenerate types are illustrated below.

The coordinates of the five basic forms of a pentagon are: $$ ( 1, 1, 1, 1, 1 ) \,,\quad( 1, \omega_5^\strut, \omega_5^2, \omega_5^3, \omega_5^4 ) \,,\quad( 1, \omega_5^2, \omega_5^4, \omega_5^\strut, \omega_5^3 ) \,,\quad( 1, \omega_5^3, \omega_5^\strut, \omega_5^4, \omega_5^2 ) \,,\quad( 1, \omega_5^4, \omega_5^3, \omega_5^2, \omega_5^\strut ) $$ We shall consider a pentagon $p$ as a function on the cyclic group ${\mathbb Z}/5 {\mathbb Z}$. In fact that's what we began to do as soon as we adopted the convention that the indices were to be viewed modulo $5$. The decomposition of a given pentagon into its standard components is just an example of harmonic analysis for the cyclic group ${\mathbb Z}_{/5} := {\mathbb Z}/5 {\mathbb Z}$. This is known as the Discrete Fourier Transform of order $5$. The 5-dimensional space, ${\mathbb C}{\mathbb Z}_{/5} $, of ${\mathbb C}$-valued functions on ${\mathbb Z}_{/5}$,known as the complex group algebra of ${\mathbb C}{\mathbb Z}_{/5}$ since it has ppointwise function multiplication as well as addition, has as a basis the functions $$\begin{eqnarray} \chi_0&=&( 1, 1, 1, 1, 1 ) \\ \chi_1&=&( 1, \omega_5^\strut, \omega_5^2, \omega_5^3, \omega_5^4 ) \\ \chi_2&=&( 1, \omega_5^2, \omega_5^4, \omega_5^\strut, \omega_5^3 ) \\ \chi_3&=&( 1, \omega_5^3, \omega_5^\strut, \omega_5^4, \omega_5^2 ) \\ \chi_4&=&( 1, \omega_5^4, \omega_5^3, \omega_5^2, \omega_5^\strut ). \end{eqnarray} $$ It is also a space with a natural Hermitian inner product. Namely for $u,v\in{\mathbb C}{\mathbb Z}_{/5}$ $$ \langle u | v\rangle := \frac{1}{|{\mathbb Z}_{/5}|}\sum_{g\in{\mathbb Z}_{/5}} \overline{u(g)}v(g) = \frac{1}{5}\sum_{1\leq j\leq 5}\overline{u_j}v_j. $$ So, if we note that the numbering of the basis functions above is like the characters of ${\mathbb Z}_{/5}$ that they are, using $$ \chi_k = (\omega_5^{k\cdot0},\omega_5^{k\cdot1},\omega_5^{k\cdot2},\omega_5^{k\cdot3}, \omega_5^{k\cdot4})\quad\quad 0\leq k\leq4, $$ then the expansion of an arbitrary function $f\in{\mathbb C}{\mathbb Z}_{/5}$ is $$ f = \sum_{k=0}^{4}\langle\chi_k | f\rangle \chi_k=\sum_{k=0}^{4}\hat f_k \chi_k, $$ where $\hat f_{0}$ is the center of gravity of the value set of $f$, and $\hat f_{1},\hat f_{2},\hat f_{3},\hat f_{4}$ are the coefficients in the expression of the arbitrary pentagon $f$ as a linear sum of standard ones. The $(\chi_k)_{0\le k\le 4}$ form an orthonormal basis, and $\chi_0$ is the trivial (or degenerate) character of the trivial representation. Now we examine the pentagon $q$ that Douglas derived in this connection: 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 for $q_i = -\frac{\sqrt5}5 p_i + \frac{5+\sqrt5}{10} p_{i+2}+ \frac{5+\sqrt5}{10} p_{i+3}$ look at $\hat q_2$, or at

$$ \begin{eqnarray} 5\hat {q_2} &=&5 \langle \chi_2 | q\rangle (-\frac{\sqrt5}5\cdot1 + \frac{5+\sqrt5}{10} \omega_5^{4} + \frac{5+\sqrt5}{10} \omega_5^{1})p_1 +\\ & & (-\frac{\sqrt5}5 \omega_5^{3} + \frac{5+\sqrt5}{10} \omega_5^{2} + \frac{5+\sqrt5}{10} \omega_5^{4})p_2 +\\ & & (-\frac{\sqrt5}5 \omega_5^{1} + \frac{5+\sqrt5}{10} \cdot1 + \frac{5+\sqrt5}{10} \omega_5^{2})p_3 +\\ & & (-\frac{\sqrt5}5 \omega_5^{4} + \frac{5+\sqrt5}{10} \omega_5^{3} + \frac{5+\sqrt5}{10} \cdot1)p_4 +\\ & & (-\frac{\sqrt5}5 \omega_5^{2} + \frac{5+\sqrt5}{10} \omega_5^{1} + \frac{5+\sqrt5}{10} \omega_5^{3})p_5 . \end{eqnarray} $$

The thing to note is that the coefficients of the points $p_i$ are all multiples by powers of $\omega_5$ of the coefficient of $p_1$. Furthermore the coefficient of $p_1$ is a real number since $\overline{\omega_5^{4}} = \omega_5^{1}$. But

$$ \begin{eqnarray} - \frac{\sqrt5}5\cdot1 + \frac{5+\sqrt5}{10} \omega_5^{4} + \frac{1+\sqrt5}{2}\omega_5^{1} = -\frac{\sqrt5}5 + \frac{5+\sqrt5}{10}\left(\omega_5^{4} + \omega_5^{1}\right) = 0 . \end{eqnarray} $$

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

$$ \begin{eqnarray} 5\hat { q_3} = 5\ \langle \chi_3 | q\rangle = 5\ \overline{\langle \overline q,\chi_2\rangle} = 0 . \end{eqnarray} $$

This is because the reason that $\langle \chi_3 | q\rangle = 0$ has little to do with the properties of the $q_i$ as complex numbers, but was entirely the result of the interaction between the $5$th roots of unity, and the real coefficients in the specific make-up of the $q_i$ starting from arbitrary complex numbers $p_i$. If this is unconvincing, then a similar argument to the previous one goes through but involves the verification $$ - \frac{\sqrt5}5\cdot1 + \frac{5+\sqrt5}{10} \omega_5^{1} + \frac{5+\sqrt5}{10}\omega_5^{4} = 0. $$ 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, as will be discussed below. We could have convinced ourselves geometrically that the coefficients vanish by looking at the diagrams for the pentagon in the unit circle, but it seemed useful to do the simple algebra. Next consider the other similarly constructed pentagon $r$, the one whose points are given by $$ r_i = \frac{\sqrt5}5 p_i + \frac{5-\sqrt5}{10} p_{i+2}+ \frac{5-\sqrt5}{10} p_{i+3}. $$ For this case we examine correspondingly the components ${\hat r}_1$ and ${\hat r}_4$. Again we can group the coefficients of the points $p_i$, and see that they are all multiples of any one of them. For instance, the coefficient of $p_1$ is $$ \frac{\sqrt5}5\cdot1 + \frac{5-\sqrt5}{10} \omega_5^{2} + \frac{5-\sqrt5}{10} \omega_5^{3}= \frac{\sqrt5}5 + \frac{5-\sqrt5}{10}\frac{-1-\sqrt5}{2} = 0, $$ just as before, up to a couple of sign changes. Also as before, we can conclude that ${\hat r}_1 = {\hat r}_4 = 0$, and say that the polygon $r$ is the affine image of a regular pentagram.

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$.

Now consider the case of a linear sum of a regular $n$-gon and its opposite, say the case of the convex pentagon where we had $n=5$ . The points are of the form $A \omega^k + B \omega^{-k}$. But $\omega^{-1}=\bar \omega$, so these points are affine images of the points of the standard convex pentagon with parameters $$ (\lambda,\mu,\nu) = (A, B, 0). $$ That's what we have above as the result of Douglas's construction with a similar consideration for the affine image of a standard pentagram.

The general Discrete Fourier Transform

Let us fix notation for the general case of what we used in the foregoing explanation. We consider an $N$-gon $p$, for a natural number $N>0$, as a function on the cyclic group $\intg_{/N} = \intg / N\intg $. We define $\omega_N := \ee^{\ii 2 \pi/N}$. Then we wish to decompose the $N$-dimensional space, $\cplx\intg_{/N}$, of $\cplx$-valued functions on $\intg_{/N}$, with respect to the basis of characters (putting a $cdot$ for the product in the exponents for emphasis) $$(\chi_k)_{k\in \intg} \quad{\rm where} \quad \chi_k = (\omega_N^{k\cdot j})_{0\le j \le N} = (\omega_N^{k\cdot0}, \omega_N^{k\cdot1},\dots, \omega_N^{k\cdot N-1}),$$ which are orthonormal for the natural Hermitian inner product, namely for $u,v\in\cplx\intg_{/N}$ $$ \langle u | v\rangle = \frac{1}{|\intg_{/N}|}\sum_{g\in\intg_{/N}} \overline{u(g)}v(g) = \frac{1}{N}\sum_{0\leq j< N-1}\overline{u_j}v_j, $$ and $$ \langle \chi_j | \chi_k\rangle = \loglb j==k\logrb = \begin{cases}1 \text{ if } j=k | k\cr 0 \text{ otherwise.}\end{cases} $$ The expansion of an arbitrary function $f=(f_1,\dots,f_N)\in\cplx\intg_{/N}$ is $$f = \sum_{k=0}^{N-1}\langle\chi_k | f\rangle \chi_k=\sum_{k=0}^{N-1}\hat f_k \chi_k,$$ where $\hat f_{0}$ is the center of gravity (a.k.a. centroid, barycenter or mean) of the value set of $f$, $$ \hat f_{0} = \frac{1}{N} (f_1 + \cdots + f_n) $$ and $\hat f_{1},\dots,\hat f_{N-1}$ are the coefficients in the expression of the arbitrary function $f$, an $N$-gon, as a linear sum of standard ones.

There can be a requirement, in the course of an argument, to emphasize the number of points involved, $N$, as well as the order, $k$ of a character. In that case we shall write, as needed, $$ \chi_{N,k} = (\omega_N^{k\cdot j})_{0\le j < N} = (\omega_N^{k\cdot j}, j\in{\bar N}) = (\omega_N^{k\cdot0}, \omega_N^{k\cdot1},\dots, \omega_N^{k\cdot N-1}),$$ where we have written $\bar N = 0..N-1$ for an integer interval; similarly we may write $\langle u | v\rangle_N$.

It is clear then that $\chi_{N,1}$ lists the vertices of the standard convex regular positively oriented $N$-gon inscribed on the unit circle. Similarly $\chi_{N,N-1}$ gives the standard negatively oriented unit $N$-gon. The combination $\lambda \chi_{N,1} +\mu \chi_{N,N-1}$ with $\lambda, \mu\in\cplx$ then gives a general affine convex $N$-gon.

When $ 1 < k < N-1$ the $N$-gon given by $\chi_{N,k}$ will have a multiplicity if $k|N$ ($k$ divides $N$) and that will be $N/k$. Otherwise it will be sort of ‘star’ polygon if $k$ is prime to $N$, i.e., $(k,N)=1$, their greatest common divisor is 1. For instance, $\chi_{6,3}$ is the standard hexagon's horizontal equator (a ‘di-gon’) described back and forth 3 times. $\chi_{6,4}$ is the standard unit equilateral triangle $\chi_{3,1}$ listed twice in reverse, or you can think of it as $\chi_{3,2}$ twice.

Triangle geometry

Since the claim is that much classical plane geometry has a natural expression from the point of view outlined above, we start by looking at the standard types of triangles and their natural expressions in this Discrete Fourier Transform notation. Consider first of all triangles whose centroids are at the origin; after all, it is easy enough to move any triangle into this simplifying position by a translation, and all interesting theorems of plane geometry are invariant under translations.

The first example is the simple average of a standard equilateral triangle and its reverse, namely $\sfrac12(\chi_1+\chi_2)$. The points are thus $(1,-\sfrac12,-\sfrac12)$; this is a degenerate triangle of points with the second and third vertices coincident at $-\sfrac12$. It is a digon with a double point at the left-hand end.

Triangle and anti-triangle averaged

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

$$\begin{eqnarray*} \sfrac12(\lambda\chi_1+\chi_2)=b\sfrac12\left(\lambda+1,-\sfrac12(\lambda+1)+ \sfrac{\sqrt3}2(\lambda-1)\ii,-\sfrac12(\lambda+1)-\sfrac{\sqrt3}2(\lambda-1)\ii\right) \end{eqnarray*} $$

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 of vertices $A$, $B$ and $C$ is the average of the two triangles with indexed vertices.

Larger triangle and anti-triangle 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} \sfrac12(\ee^{\ii \alpha}\chi_1+\ee^{-\ii \alpha}\chi_2)= (\cos \alpha, -\sfrac12\cos \alpha-\sfrac{\sqrt3}2\sin \alpha, -\sfrac12\cos \alpha+\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 axis that the triangles are rotated; it goes from $0$ to $2 \pi$. The linear green triangle of vertices $A$, $B$ and $C$ is the average of the triangles with indexed vertices. Note that the vertices $A_1$, $B_1$ and $C_1$ are positively oriented (counter-clockwise) and $A_2$, $B_2$ and $C_2$ are negatively oriented.

Larger triangle and anti-triangle averaged

The fully general case is then the addition of two arbitrarily sized and rotated standard triangles and this is illustrated below.

The sliders are $\lambda$ controlling the size and $\alpha$ controlling its angle of rotation of the image of the reddish standard triangle labelled $A_1, B_1, C_1$. Then $\mu$ and $\beta$ are the corresponding controls for the blue reversed standard triangle labelled $A_2, B_2, C_2$. We average the two component triangles only to make the diagram more compact; the result is the green triangle labeled $A_3, B_3, C_3$. 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. We average the two component triangles to make a green one only to make the diagram more compact.

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; the centre of gravity is $\nu \ee^{\ii \gamma}\chi_0$.

General scaled and rotated triangle and anti-triangle averaged

One can spend quite some time playing with figures for these polygon superpositions but we'll just offer a couple more for enthusiasts here.

Quadrilateral geometry
Pentagon geometry

Proof of Napoleon's Theorem

Let us start by seeing how to express the construction steps in the simple Napoleon theorem with the help of the characters we introduced. We need to be able 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.

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 to it $z\chi_0$. 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 in the construction, 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 $\langle\chi_0 | z\rangle$. 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*} \langle\chi_0 | 3^{-1}(\omega^2-1)(z_k-z_j)(\chi_1-\chi_0) + z_j\chi_0\rangle &=& -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 the triangle positively oriented. Start with externally constructed equilateral triangles. That means 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 \bar 3), $$ so the triangle is $$3 ^{-1}\{(1-\omega)J z+ (\omega+2)z\}, $$ where $J$ is the cyclic permutation $$ J: (z_0,z_1,z_2) \mapsto (z_1,z_2,z_0) . $$ To show that this is an equilateral triangle it suffices to 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 hence that $Jz=\hat z_0\chi_0+\omega \hat z_1\chi_1+\omega^2 \hat z_2\chi_2$; and the basis $(\chi_j,j\in\bar3)$ is orthonormal. Thus \begin{eqnarray*} \langle\chi_2|3^{-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*} Therefore 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 drawing left-hand side, i.e. , ‘internal’ equilateral triangles, and taking their centroids we just have to do a similar calculation. Since we may suspect that the resulting vertices will have the reverse orientation we will take the inner product with $\chi_1$. By remarks above the internally constructed vertices are $$ ( -3^{-1}\{(\omega^2-1)z_{j+1}-(\omega^2+2)z_j\} , j\in \bar 3), $$ so the triangle is $$ 3^{-1}\{(1-\omega^2)J z+ (\omega^2+2)z\}. $$ Thus \begin{eqnarray*} \langle\chi_1|3^{-1}\{(1-\omega^2)J z+ (\omega^2+2)z\}\rangle &=&3^{-1}\{(1-\omega^2)\omega \hat z_1+ (\omega^2+2)\hat z_1\}\\ &=&3^{-1}\{\omega-1+\omega^2 +2\}\hat z_1 \\ &=& 0, \end{eqnarray*} as suspected. We have the vertices of a reverse equilateral triangle. ▓

Corollary The Napoleon construction provides a geometrical way to find the discrete Fourier transform of a triangle.
Proof. We evaluate the other coefficients for the constructed triangles. First for the external triangles \begin{eqnarray*} \langle\chi_1|3^{-1}\{(1-\omega)J z+ (\omega+2)z\}\rangle &=&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$. ▓

The generalized form of this just results from noticing that one could 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 of those which are the vertices of a square, before the general formulation that follows.

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.

The matrix point of view

We have been considering a triple of vertices as a function on $\ints_{/3}$. The cyclic permutation, $(0,1,2)\mapsto (1,2,0)$, and is the generator, call it $J$, of the group $\ints_{/3}$. Extended to act on functions, this maps $(z_0,z_1,z_2)\mapsto (z_1,z_2,z_0)$, thus moving the points by one index around the putative curve. If we write our coordinates out as column vectors (so as to end up with matrix actions on the left, which is probably more common) then we can write \[ \left(\begin{array}{c} z_1\\ z_2\\ z_0 \end{array}\right) = \left(\begin{array}{ccc} 0&1&0\\ 0&0&1\\ 1&0&0 \end{array}\right) \left(\begin{array}{c} z_0\\ z_1\\ z_2 \end{array}\right), \] or (using Matlab notation in which ‘,’ is a horizontal spacer and ‘;’ is a vertical spacer) the result is $Jz$ with $z:=(z_0;z_1;z_2)$ and $J:= (0,1,0;0,0,1;1,0,0)$.

First note $J^3=1$, so that $J$'s eigenvalue list is $(1,\omega,\omega^2)$. Then note that we know from above the corresponding eigenvectors to be $(\chi_0\tr, \chi_1\tr,\chi_2\tr)$ (${}\tr$ is the notation for the transpose); for instance, $J \chi_1\tr = (\omega;\omega^2; 1) = \omega (1;\omega;\omega^2) = \omega \chi_1$. Thus we can see an explicit diagonalization of $J$ using $(\chi_0;\chi_1;\chi_2)$ \[ \left(\begin{array}{ccc} 0&1&0\\ 0&0&1\\ 1&0&0 \end{array}\right) = \frac{1}{3}\left(\begin{array}{ccc} 1&1&1\\ 1&\omega&\omega^2\\ 1&\omega^2&\omega \end{array}\right) \left(\begin{array}{ccc} 1&0&0\\ 0&\omega&0\\ 0&0&\omega^2 \end{array}\right) \left(\begin{array}{ccc} 1&1&1\\ 1&\omega^2&\omega\\ 1&\omega&\omega^2 \end{array}\right) ,\] or with $U\st := \frac{1}{\sqrt3}(\chi_0;\chi_1;\chi_2)$ we have $U J U\st = (1\!:\!\omega\!:\!\omega^2)$; here we have used ‘:’ as a diagonal separator to supplement our horizontal and vertical ones, and ${}\st$ denotes Hermitian conjugation. We note $U$ is unitary: $U\st U = 1$. We can recognize $U\st$ as the (normalized) matrix of the discrete Fourier transform above, since it clear that \[ \tfrac{1}{\sqrt 3} U\st (z_0;z_1;z_2) = (f_0;f_1;f_2). \] We could have written the Fourier transform equations in matrix form before as \[ 3 \left(\begin{array}{c} f_0\\f_1\\f_2\end{array}\right)= \left(\begin{array}{lll} 1&1&1\\ 1&\omega^2&\omega\\ 1&\omega&\omega^2 \end{array}\right) \left(\begin{array}{c} z_0\\z_1\\z_2\end{array}\right), \] and \[ 3\left(\begin{array}{c} z_0\\z_1\\z_2\end{array}\right) = \left(\begin{array}{lll} 1&1&1\\ 1&\omega&\omega^2\\ 1&\omega^2&\omega \end{array}\right) \left(\begin{array}{c} f_0\\f_1\\f_2\end{array}\right). \] If we single out the presence of the $3\times3$ Vandermonde matrix $V=(\chi_0;\chi_1;\chi_2)$ in these formulas, we can write them as \[ 3 z = V\st f \quad {\rm and} \quad 3f=Vz, \] and we have $U=\sfrac1{\sqrt3}V$.

A polynomial point of view

The whole matter above could be viewed as part of algebra, not geometry. Let us explore some of the formalism as a derivative of what is found in papers of F. Chapoton for which he, in turn, references Curtis and Reiner.

We are looking at the cyclic group $\ints_{/N}$ and the associated group algebra $\cplx\ints_{/N}$. If we take the generator of the cyclic group to be $t$ then it is well-known that $\cplx\ints_{/N} = \cplx[J]/\langle J^N - 1\rangle$. $J$ is the generator of the cyclic group, $\cplx[J]$ is the algebra of complex polynomials in $J$ and $\langle J^N - 1\rangle$ is the ideal generated by the relation $J^N = 1$. If $d$ is a divisor of $N$ then the space $\cplx[J]/\langle J^N - 1\rangle$ will be a module for $\cplx\ints_{/N}$ under the obvious action of multiplication of each term by $J^k \mapsto J^{kd}$; call this module $M_{N,d}$. Then $M_{N,N}$ is the regular representation on the group algebra, and $M_{N,1}$ the trivial representation. The character of $M_{N,d}$ is \[ \chi_{N,d}(t^k) = \begin{cases}d \text{ if } d | k\cr 0 \text{ otherwise.}\end{cases} \] We denote by $K_0(\cplx\ints_{/N})$ the Grothendieck group of the category of $\cplx\ints_{/N}$-modules of finite rank. The rank of this Abelian group is the number of divisors of $N$ and the equivalence classes in $K_0(\cplx\ints_{/N})$ of the standard modules $M_{N,d}$ form a basis of it.

Let us break off generality and consider the simplest cases which we have already looked at under the guise of plane geometry. For $N=2$ we have the two-element group $\cplx\ints_{/2}$ and a single non-trivial representation on $\cplx[J]/\langle J^2-1\rangle = \{a + b J \colon a,b\in \cplx\}=\cplx^2$. The generator acts by \[ J: a+bJ \mapsto aJ + b \] or \[ J: \left( \begin{array}{c} a\\ b\\ \end{array} \right) \mapsto \left( \begin{array}{c} b\\ a\\ \end{array} \right) = \left( \begin{array}{cc} 0& 1\\ 1& 0\ \end{array} \right) \left( \begin{array}{c} a\\ b\\ \end{array} \right) \]

For the next prime $N=3$ we have the three-element group $\cplx\ints_{/3}$ and a single non-trivial representation on $\cplx[J]/\langle J^3-1\rangle = \{a + b t + c t^2\colon a,b,c\in \cplx\}=\cplx^3$. The generator acts by \[ J: a+b J+c J^2 \mapsto a J^2 + b + c J \] or \[ J: \left( \begin{array}{c} a\\ b\\ c\\ \end{array} \right) \mapsto \left( \begin{array}{c} b\\ c\\ a\\ \end{array} \right) = \left( \begin{array}{c} 0& 1& 0\\ 0& 0&1\\ 1& 0&0\\ \end{array} \right) \left( \begin{array}{c} a\\ b\\ c\\ \end{array} \right) \] This was the regular representation $M_{3,3}$. The module $M_{3,2}$ gives an equivalent representation, and $M_{3,1}$ is, as ever, the trivial representation $ J \mapsto \text{Id}$.

For the $N=4$ we have the four-element group $\cplx\ints_{/4}$ and a composite $N$. There is still the regular representation on $\cplx[J]/\langle J^4-1\rangle = \{a + b J + c J^2+d J^3\colon a,b,c,d\in \cplx\}=\cplx^4$, and there the generator acts as usual by \[ J: a+b J+c J^2 + d J^3 \mapsto a J^3 + b + c J + d J^2 \] with matrix \[ J: \left( \begin{array}{c} a\\ b\\ c\\ d\\ \end{array} \right) \mapsto \left( \begin{array}{c} b\\ c\\ d\\ a\\ \end{array} \right) = \left( \begin{array}{c} 0& 1& 0& 0\\ 0& 0&1&0\\ 0& 0&0&1\\ 1& 0& 0&0\\ \end{array} \right) \left( \begin{array}{c} a\\ b\\ c\\ d\\ \end{array} \right) \] But there is also the representation $M_{4,2}$ for which $J$ acts by \[ t: a+b J+c J^2 + d J^3 \mapsto a J^2 + b J^3 + c + d J \] with \[ J: \left( \begin{array}{c} a\\ b\\ c\\ d\\ \end{array} \right) \mapsto \left( \begin{array}{c} c\\ d\\ a\\ b\\ \end{array} \right) = \left( \begin{array}{c} 0& 0& 1& 0\\ 0& 0&0&1\\ 1& 0&0&0\\ 0&1& 0&0\\ \end{array} \right) \left( \begin{array}{c} a\\ b\\ c\\ d\\ \end{array} \right) \]

Continued by:

Interpolation with the Discrete Fourier Transform

Patrick D. F. Ion
Mathematical Reviews
ion at ams.orgemail icon


Powered by MathJax, an Open Source project enabling browser display of MathML and TeX and supported by the AMS.