One of the most wonderful aspects of math is how deep we can get by\nstudying seemingly trivial questions. Consider the roots of unity, where\n"unity" simply means the number 1.
\nStudying the roots of unity usually begins in middle school: what is the\nsquare root of 1? Equivalently, what are the solutions to this equation?
\n[x^2=1]
\nWell, there are two answers: 1 and -1.
\nSimilarly, we can ask the question for higher roots; the third roots are\nsolutions to the equation:
\n[x^3=1]
\nAnd so on. When we’re only dealing with real numbers, that’s pretty much\nthe whole story. For odd-degree roots of 1, the only answer is 1; for\neven-degree roots of 1, the answer is either 1 or -1.
\nWhen we extend our domain to the complex numbers, things become much\nmore interesting.
\nBy the formal\ndefinition, a root of\nunity is any complex number that yields 1 when raised to a positive\ninteger power n.
\nRather than looking at all the possible roots of 1, it’s often more\nuseful to discuss the roots for a specific given n: complex\nnumbers z such that z^n=1.
\nFor example, let’s consider n=2. We’ve already seen that the\nroots are 1 and -1; these are complex numbers with a zero imaginary\npart.
\nHow about n=4? There are four roots: 1, -1, i and\n-i. For n=3, the three roots [1] are 1,\n\\frac{-1+i\\sqrt{3}}{2} and \\frac{-1-i\\sqrt{3}}{2}. It’s\neasy enough to check that these indeed give 1 when raised to the third\npower, but how do we calculate them in the first place?
\nA complex number with magnitude 1 can be represented in polar\ncoordinates [2] as z=e^{i\\theta}. If we raise z to the\nn-th power, we get:
\n[z^n=e^{in\\theta}]
\nThe magnitude of z^n is still 1, which is essential if we want\nz to be a n-th root of unity. Let’s equate z^n\nto 1:
\n[z^n=e^{in\\theta}=1]
\nTo find the solutions to this equation, we’ll first want to represent 1\nitself in polar coordinates. Let’s use another variable for the angle:
\n[1=e^{i\\phi}]
\nWhat is the value of \\phi? Thinking about the unit circle,\n\\phi is any integer multiple of 2\\pi - which we’ll\nexpress as 2\\pi k for k=0,1,2...:
\n[1=e^{i2\\pi k}]
\nBack to z^n:
\n[z^n=e^{in\\theta}=e^{i2\\pi k}]
\nOr:
\n[n\\theta=2\\pi k\\quad\\Rightarrow\\quad \\theta=\\frac{2\\pi k}{n}]
\nSo the n-th roots of unity are [3]:
\n[\\boxed{z_k=e^{i2\\pi k/n}, \\qquad k=0,1,\\dots,n-1}]
\nLet’s begin with n=2. We have the following roots:
\n[\\begin{aligned}\nz_0&=e^{i2\\pi 0/2}=e^0=1
\nz_1&=e^{i2\\pi 1/2}=e^{i\\pi}=\\cos\\pi+i\\sin\\pi=-1\n\\end{aligned}]
For n=3:
\n[\\begin{aligned}\nz_0&=e^{i2\\pi 0/3}=e^0=1
\nz_1&=e^{i2\\pi 1/3}=\\cos\\frac{2\\pi}{3}+i\\sin\\frac{2\\pi}{3}=-\\frac{1}{2}+i\\frac{\\sqrt{3}}{2}
\nz_2&=e^{i2\\pi 2/3}=\\cos\\frac{4\\pi}{3}+i\\sin\\frac{4\\pi}{3}=-\\frac{1}{2}-i\\frac{\\sqrt{3}}{2}\n\\end{aligned}]
As expected. It should be similarly simple to calculate the roots for\nn=4; give it a try.
\nWhat happens when we multiply some root of unity z_k by itself?\nSince the magnitude of the root is 1, multiplying by it is akin to a\nrotation along the unit circle by the root’s angle. For example,\nconsider z_1 from the 3rd roots of unity:
\n[z_1=e^{i2\\pi1/3}]
\nMultiply z_1 by itself:
\n[z_1^2=e^{i2\\pi1/3}\\cdot e^{i2\\pi1/3}=e^{i2\\pi2/3}]
\nIf the angle of z_1 is 2\\pi/3, the angle of\nz_1^2 is 4\\pi/3. Let’s multiply by z_1 once\nmore:
\n[z_1^3=e^{i2\\pi2/3}\\cdot e^{i2\\pi1/3}=e^{i6\\pi/3}=1]
\nThe result is 1, as expected (after all, z_1 is a 3rd root of\nunity).
\nThis visualization shows how roots of unity appear on the unit circle\nand how raising them to powers rotates the roots until finally\nz_k^n=1:
\nRoots *n* \nRoot *k*
\nPower *m*
\nSelect n first; this shows the n-th roots as blue dots\non the unit circle. Now you can click any of the roots, and see its\npowers in the lower plot - drag the slidebar to see the rotations. If\nyou spend some time playing with this, you’ll notice that some roots -\nfor example z_2 when n=6 - go back to 1 when raised to a\nsmaller power than n. We’ll revisit this outcome when we discuss\nthe group-theoretic aspects of roots of unity.
\nAs we’ve seen, the roots of unity are evenly spaced along the unit\ncircle on the complex plane. If we connect the roots with straight lines\nto their immediate neighbors, we’ll notice something interesting:
\nRoots *n*
\nFor different values of n\\ge3, we get the Regular\nPolygons! It’s pretty\neasy to prove this if we connect each root with a straight line to the\norigin. The triangles we get are congruent, because the sides from the\norigin to the roots are all of length 1, and the central angles are all\n2\\pi /n. Therefore, both the sides of the polygons and their\nangles are identical, which makes them regular.
\nSuppose we have the root of unity:
\n[z_k=e^{i2\\pi k/n}]
\nFor some k and n. If we take the reciprocal of\nz_k:
\n[z_k^{-1}=e^{-i2\\pi k/n}]
\nThen:
\n[(z_k^{-1})^n=e^{-in 2\\pi k/n}=e^{-i2\\pi k}=1]
\nSo z_k^{-1} is also an n-th root of unity. While the powers of\nz_k are rotating counter-clockwise\non the unit circle until they land on 1 for the n-th power,\nthe powers of z_k^{-1} similarly rotate\nclockwise.
\nz_k^{-1} also happens to be the complex conjugate of\nz_k:
\n[z_k^{-1}=z_k^*]
\nSo if we have:
\n[z_k=e^{i2\\pi k/n}, \\qquad k=0,1,\\dots,n-1]
\nAs the n-th roots of unity, then:
\n[z_k^*=e^{-i2\\pi k/n}, \\qquad k=0,1,\\dots,n-1]
\nAre also n-th roots of unity. In fact, they are the same roots,\nbecause for any given positive k:
\n[\\begin{aligned}\nz_k^*&=e^{-i2\\pi k/n}
\n&=1\\cdot e^{-i2\\pi k/n}
\n&=e^{i2\\pi}\\cdot e^{-i2\\pi k/n}
\n&=e^{i2\\pi n/n}\\cdot e^{-i2\\pi k/n}
\n&=e^{i2\\pi (n-k)/n}=z_{n-k}\n\\end{aligned}]
So enumerating the conjugate roots is the same as enumerating the roots\nthemselves in the opposite order.
\nLet’s look at the set of z_k (roots of unity) for some\nn:
\n[\\mu_n=\\left{z_k=e^{2\\pi ik/n}:k=0,1,\\dots,n-1\\right}]
\nThis set - along with the multiplication operation - forms a group.\nLet’s prove that.
\nClosure: Assume z,y\\in\\mu_n (so z^n=1 and\ny^n=1). Then:
\n[(zy)^n=z^n y^n=1]
\nTherefore zy\\in\\mu_n.
\nIdentity: The number 1\\in\\mu_n, so it can serve as our\nidentity element for the group.
\nAssociativity: Taken directly from the associativity of the\nmultiplication operation on complex numbers.
\nInverse: We’ve just seen in the section on conjugates that\nz^{-1} is an n-th root of unity when z is. So\nthe inverse exists and is part of the group.
\nBecause the operation we have is just complex multiplication, we can\ntrivially derive additional properties, like commutativity. Therefore,\nthe group \\mu_n is Abelian.
\nFinally, we can show that the group is also cyclic and discuss its\ngenerators.
\nFor slightly simpler notation, let’s denote w=z_1. So the group\ncan be represented as:
\n[\\mu_n=\\left{1, w, w^2,\\dots,w^{n-1}\\right}]
\nThis makes it obvious that the group is cyclic - all its elements can be\nexpressed as integer powers of w. And w is a generator\nfor the group.
\nBut interestingly, w is not the only generator for this group.\nAny w^k can be a generator, as long as k and n\nare co-prime. For example, consider the group \\mu_6:
\n[\\mu_6=\\left{1, w, w^2,w^3,w^4,w^5\\right}]
\nObviously, w is a generator for this group. But w^2\nisn’t! If we raise it to various powers we get:
\n[\\begin{aligned}\n(w^2)^0&=1
\n(w^2)^1&=w^2
\n(w^2)^2&=w^4
\n(w^2)^3&=w^6=1
\n(w^2)^4&=w^8=w^2
\n(w^2)^5&=w^{10}=w^4
\n\\end{aligned}]
Since w^6=1, the powers of w^2 repeat after just three\nsteps, so they only reach three out of six group elements.
\nBut if k and n are co-prime, w^k is a generator;\nin the case of \\mu_6, we can easily verify that w and\nw^5 are the only generators. The roots that are generators for\nthe group are also called the primitive roots.
\nLet’s take the n-roots of unity (n>1), denoted as above\nwith:
\n[\\mu_n=\\left{1, w, w^2,\\dots,w^{n-1}\\right}\\qquad w=e^{2\\pi i/n}]
\nWhat’s the sum of all these roots?
\n[S=1+w+w^2+\\cdots+w^{n-1}=\\sum_{i=0}^{n-1}w^i]
\nThis is just the sum of a geometric series with the first term 1 and\ncommon ratio r=w. Therefore:
\n[S=\\frac{1-w^n}{1-w}=\\frac{1-1}{1-w}=0]
\nIf you look carefully at the visualization shown above - this makes\nsense geometrically. All the roots of unity are evenly spread around the\nunit circle, so viewing them as vectors, all components cancel out.
\nHow about the sum of roots raised to some integer power k? Let’s\ntry this for k=2 (assuming n>2):
\n[S_2=1+w^2+w^4+\\cdots+w^{2(n-1)}]
\nUsing the same geometric series sum formula (with r=w^2), we\nget:
\n[S_2=\\frac{1-w^{2n}}{1-w^2}=\\frac{1-(w^{n})^{2}}{1-w^2}=0]
\nIn general, when k is not divisible by n, the sum is 0.\nBut when k is divisible by n, each power becomes:
\n[w^k=e^{2\\pi ik/n}=1]
\nAnd n of these sum to n. In conclusion:
\n[\\sum_{i=0}^{n-1}w^{ki}=\n\\begin{cases}\nn & k \\equiv 0 \\pmod{n}
\n0 & \\text{otherwise}
\n\\end{cases}]
Let’s consider the powers of roots of unity as vectors. We’ll continue\nusing the notation:
\n[\\mu_n=\\left{1, w, w^2,\\dots,w^{n-1}\\right}\\qquad w=e^{2\\pi i/n}]
\nWe’ll begin with the 0-th power vector - each of the roots raised to\npower 0:
\n[v_0=\\left[1, 1, 1,\\dots,1\\right]]
\nThen power 1 - just the roots themselves:
\n[v_1=\\left[1, w, w^2,\\dots,w^{n-1}\\right]]
\nEach root raised to power 2:
\n[v_2=\\left[1, w^2, w^4,\\dots,w^{2(n-1)}\\right]]
\nAnd so on, until power n-1:
\n[v_{n-1}=\\left[1, w^{n-1}, w^{2(n-1)},\\dots,w^{(n-1)(n-1)}\\right]]
\nTo go full linear algebra mode, we’ll collect these vectors into an\nn\\times n matrix:
\n[V=\\begin{bmatrix}\n1 & 1 & 1 & \\cdots & 1
\n1 & w & w^2 & \\cdots & w^{n-1}
\n1 & w^2 & w^4 & \\cdots & w^{2(n-1)}
\n\\vdots & & & & \\vdots
\n1 & w^{n-1} & w^{2(n-1)} & \\cdots & w^{(n-1)(n-1)}
\n\\end{bmatrix}]
Let’s calculate the inner product of two matrix rows. Recall that when\ncomputing the inner product on vectors over \\mathbb{C}, we\nconjugate the second element:
\n[\\begin{aligned}\n\\langle v_i,v_j\\rangle&=\\sum_{k=0}^{n-1}v_i[k]\\cdot v_j[k]^*
\n&=\\sum_{k=0}^{n-1}w^{ik}\\cdot (w^{jk})^*
\n&=\\sum_{k=0}^{n-1}w^{ik}\\cdot w^{-jk}
\n&=\\sum_{k=0}^{n-1}w^{(i-j)k}
\n\\end{aligned}]
But hold on, we’ve just calculated this exact sum in the previous\nsection. We get:
\n[\\langle v_i,v_j\\rangle=\\sum_{k=0}^{n-1}w^{(i-j)k}=\n\\begin{cases}\nn & (i-j) \\equiv 0 \\pmod{n}
\n0 & \\text{otherwise}
\n\\end{cases}]
Since the vector indices i and j only run over\n[0..n-1], this is equivalent to:
\n[\\langle v_i,v_j\\rangle=\\sum_{k=0}^{n-1}w^{(i-j)k}=\n\\begin{cases}\nn & i=j
\n0 & \\text{otherwise}
\n\\end{cases}]
Which is to say: the vectors v_i and v_j are\nmutually orthogonal when i\\neq j. Since we have a set of n orthogonal vectors\nin \\mathbb{C}^n, these vectors form a basis for\n\\mathbb{C}^n - any vector in this space can be represented as a\nlinear combination of v_i. This fact has far reaching\nconsequences in math and engineering, since it plays a critical part in\nforming the DFT (Discrete Fourier Transform), and V is also\nknown as the Fourier matrix. But this will be a topic for a separate\npost.
\nAnother fun thing to notice before we’re finished here: the matrix\nV happens to be symmetric (this is trivial to check by\nobservation). Therefore, its columns are also mutually orthogonal.
\n| [1] | In general - counting multiplicity - there are exactly n complex roots. This is because we’re essentially finding the solutions to the polynomial z^n-1=0, which has n complex solutions according to the Fundamental theorem of algebra. |
| [2] | For some notes on converting between the different representations of complex numbers, see my post on the Euler formula. |
| [3] | When k=n, \\theta=2\\pi, which is the same as \\theta=0. On a unit circle, the roots start repeating once one full cycle is completed; therefore, there are only n unique roots with k=0,1,\\dots,n-1. |