Root of Unity - Periodicity

Periodicity

If z is a primitive nth root of unity, then the sequence of powers

…, z−1, z0, z1, …

is n-periodic (because z j+n = z j·zn = z j·1 = z j for all values of j), and the n sequences of powers

s_k: …, zk·(−1), zk·0, zk·1, …

for k = 1, …, n are all n-periodic (because zk·(j+n) = zk·j). Furthermore, the set {s₁, …, s_n} of these sequences is a basis of the linear space of all n-periodic sequences. This means that any n-periodic sequence of complex numbers

…, x₋₁, x₀, x₁, …

can be expressed as a linear combination of powers of a primitive nth root of unity:

x_j = ∑_k X_k·zk·j = X₁·z1·j + ··· + X_n·zn·j

for some complex numbers X₁, …, X_n and every integer j.

This is a form of Fourier analysis. If j is a (discrete) time variable, then k is a frequency and X_k is a complex amplitude.

Choosing for the primitive nth root of unity

z = e2πi/n = cos(2π/n) + i·sin(2π/n)

allows x_j to be expressed as a linear combination of cos and sin:

x_j = ∑_k A_k·cos(2π·j·k/n) + ∑_k B_k·sin(2π·j·k/n).

This is a discrete Fourier transform.