Notes on the complex roots of unity

Eli Bendersky Papers

Summary

一篇关于复数单位根的教学笔记,从实数开方出发,介绍用极坐标计算 n 次单位根、其在单位圆上的旋转几何意义,以及与正多边形和群论的联系,并配有可交互的可视化图示。

<link rel="stylesheet" href="https://eli.thegreenplace.net/demos/rootsunity/rootsunity.css"><p>One of the most wonderful aspects of math is how deep we can get by studying seemingly trivial questions. Consider the roots of unity, where &quot;unity&quot; simply means the number 1.</p> <div class="section" id="basics-roots-of-unity-for-real-numbers"> <h2>Basics: roots of unity for real numbers</h2> <p>Studying the roots of unity usually begins in middle school: what is the square root of 1? Equivalently, what are the solutions to this equation?</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/8363334cb309207f9e3589a8f3c0744d3e6d4f42.svg" style="height: 15px;" type="image/svg+xml">\[x^2=1\]</object> <p>Well, there are two answers: 1 and -1.</p> <p>Similarly, we can ask the question for higher roots; the third roots are solutions to the equation:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/27d93743982aa6ccef3b9a7b2418b0c7a79e3d29.svg" style="height: 15px;" type="image/svg+xml">\[x^3=1\]</object> <p>And so on. When we’re only dealing with real numbers, that’s pretty much the whole story. For odd-degree roots of 1, the only answer is 1; for even-degree roots of 1, the answer is either 1 or -1.</p> <p>When we extend our domain to the complex numbers, things become much more interesting.</p> </div> <div class="section" id="basics-roots-of-unity-for-complex-numbers"> <h2>Basics: roots of unity for complex numbers</h2> <p>By the <a class="reference external" href="https://en.wikipedia.org/wiki/Root_of_unity">formal definition</a>, a root of unity is any complex number that yields 1 when raised to a positive integer power <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>.</p> <p>Rather than looking at <em>all</em> the possible roots of 1, it’s often more useful to discuss the roots for a specific given <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>: complex numbers <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/395df8f7c51f007019cb30201c49e884b46b92fa.svg" style="height: 8px;" type="image/svg+xml">z</object> such that <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/233d47313af3fd672046cb090353570bea80d230.svg" style="height: 12px;" type="image/svg+xml">z^n=1</object>.</p> <p>For example, let’s consider <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/2091fb295870e9f79b6d8a10d0f6046b091e6fe5.svg" style="height: 12px;" type="image/svg+xml">n=2</object>. We’ve already seen that the roots are 1 and -1; these are complex numbers with a zero imaginary part.</p> <p>How about <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/a2ca9af97a38440d0a4a221a8fd15cafa7284225.svg" style="height: 12px;" type="image/svg+xml">n=4</object>? There are four roots: 1, -1, <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/042dc4512fa3d391c5170cf3aa61e6a638f84342.svg" style="height: 12px;" type="image/svg+xml">i</object> and <object class="valign-m1 latex-math" data="https://eli.thegreenplace.net/images/math/91edc8362c7518c1b0e4a9a4a7bcb6c02d8e498b.svg" style="height: 13px;" type="image/svg+xml">-i</object>. For <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/c22759b5221a77ba818faab4152fe1744f5b85f9.svg" style="height: 12px;" type="image/svg+xml">n=3</object>, the three roots <a class="footnote-reference" href="#footnote-1" id="footnote-reference-1">[1]</a> are 1, <object class="valign-m6 latex-math" data="https://eli.thegreenplace.net/images/math/11d2d18e93d4619aa83566480f2c0178a74722c3.svg" style="height: 24px;" type="image/svg+xml">\frac{-1+i\sqrt{3}}{2}</object> and <object class="valign-m6 latex-math" data="https://eli.thegreenplace.net/images/math/85dd4eb543bbf24234f229cc28b840dd255d1f7b.svg" style="height: 24px;" type="image/svg+xml">\frac{-1-i\sqrt{3}}{2}</object>. It’s easy enough to check that these indeed give 1 when raised to the third power, but how do we calculate them in the first place?</p> </div> <div class="section" id="calculating-complex-roots-using-polar-coordinates"> <h2>Calculating complex roots using polar coordinates</h2> <p>A complex number with magnitude 1 can be represented in polar coordinates <a class="footnote-reference" href="#footnote-2" id="footnote-reference-2">[2]</a> as <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/e5c489bf8019e99e5ff665dfe1ae42692eacb0e2.svg" style="height: 15px;" type="image/svg+xml">z=e^{i\theta}</object>. If we raise <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/395df8f7c51f007019cb30201c49e884b46b92fa.svg" style="height: 8px;" type="image/svg+xml">z</object> to the <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th power, we get:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/c0dd5345c3031363506dcf8aa301ac4ab67be6bf.svg" style="height: 16px;" type="image/svg+xml">\[z^n=e^{in\theta}\]</object> <p>The magnitude of <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/f59bb9d629aebd3b22a4279036c4ab6f1edbd152.svg" style="height: 12px;" type="image/svg+xml">z^n</object> is still 1, which is essential if we want <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/395df8f7c51f007019cb30201c49e884b46b92fa.svg" style="height: 8px;" type="image/svg+xml">z</object> to be a <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th root of unity. Let’s equate <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/f59bb9d629aebd3b22a4279036c4ab6f1edbd152.svg" style="height: 12px;" type="image/svg+xml">z^n</object> to 1:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/2cedb131b766e28ed575b4c639af1b801ac90bfa.svg" style="height: 16px;" type="image/svg+xml">\[z^n=e^{in\theta}=1\]</object> <p>To find the solutions to this equation, we’ll first want to represent 1 itself in polar coordinates. Let’s use another variable for the angle:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/d5bde7acd6025458eb1d8a39c0c5967bc635a1e4.svg" style="height: 16px;" type="image/svg+xml">\[1=e^{i\phi}\]</object> <p>What is the value of <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/411e715f9ab9075b0a30b4117d209921f0bc2389.svg" style="height: 16px;" type="image/svg+xml">\phi</object>? Thinking about the unit circle, <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/411e715f9ab9075b0a30b4117d209921f0bc2389.svg" style="height: 16px;" type="image/svg+xml">\phi</object> is any integer multiple of <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/0833718ca4569f36e84dbdc7742eaec65e49b150.svg" style="height: 11px;" type="image/svg+xml">2\pi</object> - which we’ll express as <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/0624aa8f4e0fe6434ed03ae36d5a18233194de3e.svg" style="height: 12px;" type="image/svg+xml">2\pi k</object> for <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/35c4afd45b33a5abbbdee3e90d30778062b80d2f.svg" style="height: 16px;" type="image/svg+xml">k=0,1,2...</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/176fbff982dfdfcbb1bb832092fcb086cace2ba5.svg" style="height: 16px;" type="image/svg+xml">\[1=e^{i2\pi k}\]</object> <p>Back to <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/f59bb9d629aebd3b22a4279036c4ab6f1edbd152.svg" style="height: 12px;" type="image/svg+xml">z^n</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/c2c4a94f53dd9ca418a1422f7c65ae71d7780507.svg" style="height: 16px;" type="image/svg+xml">\[z^n=e^{in\theta}=e^{i2\pi k}\]</object> <p>Or:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/51eed9b79786275bef5ab6410ae63e10af891837.svg" style="height: 37px;" type="image/svg+xml">\[n\theta=2\pi k\quad\Rightarrow\quad \theta=\frac{2\pi k}{n}\]</object> <p>So the <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th roots of unity are <a class="footnote-reference" href="#footnote-3" id="footnote-reference-3">[3]</a>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/ea482e5c67ccc3df2f6f7c2e703b64ad51fcfdd1.svg" style="height: 29px;" type="image/svg+xml">\[\boxed{z_k=e^{i2\pi k/n}, \qquad k=0,1,\dots,n-1}\]</object> </div> <div class="section" id="some-basic-examples"> <h2>Some basic examples</h2> <p>Let’s begin with <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/2091fb295870e9f79b6d8a10d0f6046b091e6fe5.svg" style="height: 12px;" type="image/svg+xml">n=2</object>. We have the following roots:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/4f49ddbc4e3bd330b3625fb44755cb06a9db19c5.svg" style="height: 48px;" type="image/svg+xml">\[\begin{aligned} z_0&amp;=e^{i2\pi 0/2}=e^0=1\\ z_1&amp;=e^{i2\pi 1/2}=e^{i\pi}=\cos\pi+i\sin\pi=-1 \end{aligned}\]</object> <p>For <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/c22759b5221a77ba818faab4152fe1744f5b85f9.svg" style="height: 12px;" type="image/svg+xml">n=3</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/d9689d0c44ff53ebf37d3789f27a2bcafa99512f.svg" style="height: 115px;" type="image/svg+xml">\[\begin{aligned} z_0&amp;=e^{i2\pi 0/3}=e^0=1\\ z_1&amp;=e^{i2\pi 1/3}=\cos\frac{2\pi}{3}+i\sin\frac{2\pi}{3}=-\frac{1}{2}+i\frac{\sqrt{3}}{2}\\ z_2&amp;=e^{i2\pi 2/3}=\cos\frac{4\pi}{3}+i\sin\frac{4\pi}{3}=-\frac{1}{2}-i\frac{\sqrt{3}}{2} \end{aligned}\]</object> <p>As expected. It should be similarly simple to calculate the roots for <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/a2ca9af97a38440d0a4a221a8fd15cafa7284225.svg" style="height: 12px;" type="image/svg+xml">n=4</object>; give it a try.</p> </div> <div class="section" id="roots-of-unity-and-rotations-on-the-unit-circle"> <h2>Roots of unity and rotations on the unit circle</h2> <p>What happens when we multiply some root of unity <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/ff098555ccf7ee8fec5b7b700285db4685fbae8e.svg" style="height: 10px;" type="image/svg+xml">z_k</object> by itself? Since the magnitude of the root is 1, multiplying by it is akin to a <em>rotation</em> along the unit circle by the root’s angle. For example, consider <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/e454a1a44b86318c4927590ae2179eb450c5eb14.svg" style="height: 10px;" type="image/svg+xml">z_1</object> from the 3rd roots of unity:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/edcce6a8a2cae27f290f81aa89244c331095bd22.svg" style="height: 20px;" type="image/svg+xml">\[z_1=e^{i2\pi1/3}\]</object> <p>Multiply <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/e454a1a44b86318c4927590ae2179eb450c5eb14.svg" style="height: 10px;" type="image/svg+xml">z_1</object> by itself:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/0687e3e8cce4b4414ac8301f203f76ce08d8c411.svg" style="height: 21px;" type="image/svg+xml">\[z_1^2=e^{i2\pi1/3}\cdot e^{i2\pi1/3}=e^{i2\pi2/3}\]</object> <p>If the angle of <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/e454a1a44b86318c4927590ae2179eb450c5eb14.svg" style="height: 10px;" type="image/svg+xml">z_1</object> is <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/7cc2f9aceb37cdf4cccd82972e376f791367641f.svg" style="height: 18px;" type="image/svg+xml">2\pi/3</object>, the angle of <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/89924baa1435767fb3b7886247adacc1819750fd.svg" style="height: 19px;" type="image/svg+xml">z_1^2</object> is <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/4279bea8cb80aad253df8a6495defb5055cc784f.svg" style="height: 18px;" type="image/svg+xml">4\pi/3</object>. Let’s multiply by <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/e454a1a44b86318c4927590ae2179eb450c5eb14.svg" style="height: 10px;" type="image/svg+xml">z_1</object> once more:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/f559d69ac2245e1524e5793149f8da1150a5495c.svg" style="height: 21px;" type="image/svg+xml">\[z_1^3=e^{i2\pi2/3}\cdot e^{i2\pi1/3}=e^{i6\pi/3}=1\]</object> <p>The result is 1, as expected (after all, <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/e454a1a44b86318c4927590ae2179eb450c5eb14.svg" style="height: 10px;" type="image/svg+xml">z_1</object> is a 3rd root of unity).</p> <p>This visualization shows how roots of unity appear on the unit circle and how raising them to powers rotates the roots until finally <object class="valign-m5 latex-math" data="https://eli.thegreenplace.net/images/math/638bca8891c842399d6782142078083c115b2334.svg" style="height: 17px;" type="image/svg+xml">z_k^n=1</object>:</p> <div class="rootsunity-wrap"> <section aria-label="Roots of unity"> <canvas id="rootsunity-roots" width="440" height="420" role="img"> The nth roots of unity, equally spaced around the unit circle. Use the root selector below. </canvas> <div class="rootsunity-controls"> <label for="rootsunity-degree">Roots <i>n</i> <select id="rootsunity-degree" aria-label="Number of roots n"></select></label> <label for="rootsunity-root">Root <i>k</i> <select id="rootsunity-root" aria-label="Selected root k"></select></label> </div> </section> <section aria-label="Powers of the selected root"> <canvas id="rootsunity-powers" width="440" height="420" role="img"> The powers of the selected root. Use the power slider below. </canvas> <div class="rootsunity-controls"> <label for="rootsunity-power">Power <i>m</i></label> <input id="rootsunity-power" type="range" min="1" max="6" value="1" step="1"> <output id="rootsunity-power-value" for="rootsunity-power"></output> </div> </section> </div><p>Select <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> first; this shows the <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th roots as blue dots on the unit circle. Now you can click any of the roots, and see its powers in the lower plot - drag the slidebar to see the rotations. If you spend some time playing with this, you’ll notice that some roots - for example <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/71f0e21bc266b9df576c4de576a5c1224f52f613.svg" style="height: 10px;" type="image/svg+xml">z_2</object> when <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/fd917de64a52110443142df37dfb4c646c895ca0.svg" style="height: 12px;" type="image/svg+xml">n=6</object> - go back to 1 when raised to a smaller power than <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>. We’ll revisit this outcome when we discuss the group-theoretic aspects of roots of unity.</p> </div> <div class="section" id="geometry-roots-of-unity-and-regular-polygons"> <h2>Geometry: roots of unity and regular polygons</h2> <p>As we’ve seen, the roots of unity are evenly spaced along the unit circle on the complex plane. If we connect the roots with straight lines to their immediate neighbors, we’ll notice something interesting:</p> <div class="rootsunity-wrap"> <section aria-label="Regular polygons from roots of unity"> <canvas id="rootsunity-polygon" width="440" height="420" role="img"> Adjacent nth roots of unity joined to form a regular polygon on the unit circle. </canvas> <div class="rootsunity-controls"> <label for="rootsunity-polygon-degree">Roots <i>n</i> <select id="rootsunity-polygon-degree" aria-label="Number of roots n"></select></label> </div> </section> </div><p>For different values of <object class="valign-m2 latex-math" data="https://eli.thegreenplace.net/images/math/b31027a7d3ac1d87ed01a4ca9e6bc1a3ea6da64d.svg" style="height: 14px;" type="image/svg+xml">n\ge3</object>, we get the <a class="reference external" href="https://en.wikipedia.org/wiki/Regular_polygon">Regular Polygons</a>! It’s pretty easy to prove this if we connect each root with a straight line to the origin. The triangles we get are congruent, because the sides from the origin to the roots are all of length 1, and the central angles are all <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/2ae20eff12708a7686de72a34c9d9753ea6021dd.svg" style="height: 18px;" type="image/svg+xml">2\pi /n</object>. Therefore, both the sides of the polygons and their angles are identical, which makes them regular.</p> </div> <div class="section" id="conjugates-of-roots-of-unity"> <h2>Conjugates of roots of unity</h2> <p>Suppose we have the root of unity:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/17b1c922c581c7418bb2492f31a33a7f6583375c.svg" style="height: 20px;" type="image/svg+xml">\[z_k=e^{i2\pi k/n}\]</object> <p>For some <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/13fbd79c3d390e5d6585a21e11ff5ec1970cff0c.svg" style="height: 12px;" type="image/svg+xml">k</object> and <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>. If we take the reciprocal of <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/ff098555ccf7ee8fec5b7b700285db4685fbae8e.svg" style="height: 10px;" type="image/svg+xml">z_k</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/87fa380c6bbbd66e98caf03714a27b6f4e2fa6bd.svg" style="height: 22px;" type="image/svg+xml">\[z_k^{-1}=e^{-i2\pi k/n}\]</object> <p>Then:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/7835bde1ec507eb137a919c14fba6f827d26cba5.svg" style="height: 22px;" type="image/svg+xml">\[(z_k^{-1})^n=e^{-in 2\pi k/n}=e^{-i2\pi k}=1\]</object> <p>So <object class="valign-m5 latex-math" data="https://eli.thegreenplace.net/images/math/f380a3a6ce31c7a9d7ea90d3407560985f1925b1.svg" style="height: 21px;" type="image/svg+xml">z_k^{-1}</object> is also an n-th root of unity. While the powers of <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/ff098555ccf7ee8fec5b7b700285db4685fbae8e.svg" style="height: 10px;" type="image/svg+xml">z_k</object> are rotating counter-clockwise on the unit circle until they land on 1 for the <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th power, the powers of <object class="valign-m5 latex-math" data="https://eli.thegreenplace.net/images/math/f380a3a6ce31c7a9d7ea90d3407560985f1925b1.svg" style="height: 21px;" type="image/svg+xml">z_k^{-1}</object> similarly rotate <em>clockwise</em>.</p> <p><object class="valign-m5 latex-math" data="https://eli.thegreenplace.net/images/math/f380a3a6ce31c7a9d7ea90d3407560985f1925b1.svg" style="height: 21px;" type="image/svg+xml">z_k^{-1}</object> also happens to be the complex conjugate of <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/ff098555ccf7ee8fec5b7b700285db4685fbae8e.svg" style="height: 10px;" type="image/svg+xml">z_k</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/a23c986d7ecb8cd6172396205e557a2eadfa693b.svg" style="height: 21px;" type="image/svg+xml">\[z_k^{-1}=z_k^*\]</object> <p>So if we have:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/03d9dd24f65e4a24d5845fc97583178de083bb2c.svg" style="height: 20px;" type="image/svg+xml">\[z_k=e^{i2\pi k/n}, \qquad k=0,1,\dots,n-1\]</object> <p>As the <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th roots of unity, then:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/4024b99d712d61bc80741fef823410a8274d4b6e.svg" style="height: 21px;" type="image/svg+xml">\[z_k^*=e^{-i2\pi k/n}, \qquad k=0,1,\dots,n-1\]</object> <p>Are also <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th roots of unity. In fact, they are the same roots, because for any given positive <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/13fbd79c3d390e5d6585a21e11ff5ec1970cff0c.svg" style="height: 12px;" type="image/svg+xml">k</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/38ee91a66813ad1c94b100d153b5f1b5471db5e2.svg" style="height: 135px;" type="image/svg+xml">\[\begin{aligned} z_k^*&amp;=e^{-i2\pi k/n}\\ &amp;=1\cdot e^{-i2\pi k/n}\\ &amp;=e^{i2\pi}\cdot e^{-i2\pi k/n}\\ &amp;=e^{i2\pi n/n}\cdot e^{-i2\pi k/n}\\ &amp;=e^{i2\pi (n-k)/n}=z_{n-k} \end{aligned}\]</object> <p>So enumerating the conjugate roots is the same as enumerating the roots themselves in the opposite order.</p> </div> <div class="section" id="group-theory-the-cyclic-group-of-roots-of-unity"> <h2>Group theory: the cyclic group of roots of unity</h2> <p>Let’s look at the set of <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/ff098555ccf7ee8fec5b7b700285db4685fbae8e.svg" style="height: 10px;" type="image/svg+xml">z_k</object> (roots of unity) for some <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/68715f4c8688f321158f590581a1b85b9d135511.svg" style="height: 32px;" type="image/svg+xml">\[\mu_n=\left\{z_k=e^{2\pi ik/n}:k=0,1,\dots,n-1\right\}\]</object> <p>This set - along with the multiplication operation - forms a <em>group</em>. Let’s prove that.</p> <p><strong>Closure:</strong> Assume <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/a6609eca49b6c48a380ab6d1e4b3daf0a1738998.svg" style="height: 13px;" type="image/svg+xml">z,y\in\mu_n</object> (so <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/233d47313af3fd672046cb090353570bea80d230.svg" style="height: 12px;" type="image/svg+xml">z^n=1</object> and <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/40443a0bbab19712085bea791d8160cdc9af5882.svg" style="height: 15px;" type="image/svg+xml">y^n=1</object>). Then:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/e596605ff5dde17a38f27e0c4e996f9843c4fd0e.svg" style="height: 18px;" type="image/svg+xml">\[(zy)^n=z^n y^n=1\]</object> <p>Therefore <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/7e8908dff37f92c4b190b13cd1b90d5e696296d4.svg" style="height: 13px;" type="image/svg+xml">zy\in\mu_n</object>.</p> <p><strong>Identity:</strong> The number <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/13e13a1debb55228edc4408b38c141bb53fa8ebb.svg" style="height: 15px;" type="image/svg+xml">1\in\mu_n</object>, so it can serve as our identity element for the group.</p> <p><strong>Associativity:</strong> Taken directly from the associativity of the multiplication operation on complex numbers.</p> <p><strong>Inverse:</strong> We’ve just seen in the section on conjugates that <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/f952d2113cc5ef211c8a7a76dad3967568f0f880.svg" style="height: 15px;" type="image/svg+xml">z^{-1}</object> is an <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-th root of unity when <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/395df8f7c51f007019cb30201c49e884b46b92fa.svg" style="height: 8px;" type="image/svg+xml">z</object> is. So the inverse exists and is part of the group.</p> <p>Because the operation we have is just complex multiplication, we can trivially derive additional properties, like commutativity. Therefore, the group <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/d220e0a0d3898265d8faf630c06c2a11f809e294.svg" style="height: 11px;" type="image/svg+xml">\mu_n</object> is <em>Abelian</em>.</p> <p>Finally, we can show that the group is also <em>cyclic</em> and discuss its <em>generators</em>.</p> <p>For slightly simpler notation, let’s denote <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/b83f781eef94665c0c0c8cf2f07fed9c17d2efa3.svg" style="height: 10px;" type="image/svg+xml">w=z_1</object>. So the group can be represented as:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/022cef06d5818c7bb8fd137aabb2a3d612d63536.svg" style="height: 22px;" type="image/svg+xml">\[\mu_n=\left\{1, w, w^2,\dots,w^{n-1}\right\}\]</object> <p>This makes it obvious that the group is cyclic - all its elements can be expressed as integer powers of <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/aff024fe4ab0fece4091de044c58c9ae4233383a.svg" style="height: 8px;" type="image/svg+xml">w</object>. And <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/aff024fe4ab0fece4091de044c58c9ae4233383a.svg" style="height: 8px;" type="image/svg+xml">w</object> is a generator for the group.</p> <p>But interestingly, <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/aff024fe4ab0fece4091de044c58c9ae4233383a.svg" style="height: 8px;" type="image/svg+xml">w</object> is not the only generator for this group. Any <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/4a44049c3a8f53936d8fcc36d815a42f1e142c30.svg" style="height: 15px;" type="image/svg+xml">w^k</object> can be a generator, as long as <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/13fbd79c3d390e5d6585a21e11ff5ec1970cff0c.svg" style="height: 12px;" type="image/svg+xml">k</object> and <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> are co-prime. For example, consider the group <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/1b97b3bbef9188f0b2b3fa65fe281543f777ef36.svg" style="height: 11px;" type="image/svg+xml">\mu_6</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/fc0be2f835f981ed8f20fa07b99b60d0792db10a.svg" style="height: 22px;" type="image/svg+xml">\[\mu_6=\left\{1, w, w^2,w^3,w^4,w^5\right\}\]</object> <p>Obviously, <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/aff024fe4ab0fece4091de044c58c9ae4233383a.svg" style="height: 8px;" type="image/svg+xml">w</object> is a generator for this group. But <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/a4b6f6113d5e75c21bdb387b851a7265f997a9e7.svg" style="height: 15px;" type="image/svg+xml">w^2</object> isn’t! If we raise it to various powers we get:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/4cf480ee125e345551a71688da373bc384bcadb6.svg" style="height: 156px;" type="image/svg+xml">\[\begin{aligned} (w^2)^0&amp;=1\\ (w^2)^1&amp;=w^2\\ (w^2)^2&amp;=w^4\\ (w^2)^3&amp;=w^6=1\\ (w^2)^4&amp;=w^8=w^2\\ (w^2)^5&amp;=w^{10}=w^4\\ \end{aligned}\]</object> <p>Since <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/4fa09a2f081fa4d539caf593f6ef1cdf8a0f0c3b.svg" style="height: 15px;" type="image/svg+xml">w^6=1</object>, the powers of <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/a4b6f6113d5e75c21bdb387b851a7265f997a9e7.svg" style="height: 15px;" type="image/svg+xml">w^2</object> repeat after just three steps, so they only reach three out of six group elements.</p> <p>But if <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/13fbd79c3d390e5d6585a21e11ff5ec1970cff0c.svg" style="height: 12px;" type="image/svg+xml">k</object> and <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> are co-prime, <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/4a44049c3a8f53936d8fcc36d815a42f1e142c30.svg" style="height: 15px;" type="image/svg+xml">w^k</object> is a generator; in the case of <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/1b97b3bbef9188f0b2b3fa65fe281543f777ef36.svg" style="height: 11px;" type="image/svg+xml">\mu_6</object>, we can easily verify that <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/aff024fe4ab0fece4091de044c58c9ae4233383a.svg" style="height: 8px;" type="image/svg+xml">w</object> and <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/4111fef466982e1b6ffce01c01d4254db2a40c24.svg" style="height: 15px;" type="image/svg+xml">w^5</object> are the only generators. The roots that are generators for the group are also called the <em>primitive roots</em>.</p> </div> <div class="section" id="sums-of-roots-of-unity"> <h2>Sums of roots of unity</h2> <p>Let’s take the <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>-roots of unity (<object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/719262cd45830248133d8a9183d18f9b43c1a7cb.svg" style="height: 12px;" type="image/svg+xml">n&gt;1</object>), denoted as above with:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/82c3159e4ad11eea2305a1be4fd309eb96ca2ec0.svg" style="height: 23px;" type="image/svg+xml">\[\mu_n=\left\{1, w, w^2,\dots,w^{n-1}\right\}\qquad w=e^{2\pi i/n}\]</object> <p>What’s the sum of all these roots?</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/95e2fad1ca588ef53366342e0f1cb3a97473ebf5.svg" style="height: 52px;" type="image/svg+xml">\[S=1+w+w^2+\cdots+w^{n-1}=\sum_{i=0}^{n-1}w^i\]</object> <p>This is just the sum of a geometric series with the first term 1 and common ratio <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/7cfc225017016ad50ea7ef500ad286270db16b1e.svg" style="height: 8px;" type="image/svg+xml">r=w</object>. Therefore:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/c6f321c67a305509b4120d745ac7c71228f752ef.svg" style="height: 38px;" type="image/svg+xml">\[S=\frac{1-w^n}{1-w}=\frac{1-1}{1-w}=0\]</object> <p>If you look carefully at the visualization shown above - this makes sense geometrically. All the roots of unity are evenly spread around the unit circle, so viewing them as vectors, all components cancel out.</p> <p>How about the sum of roots raised to some integer power <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/13fbd79c3d390e5d6585a21e11ff5ec1970cff0c.svg" style="height: 12px;" type="image/svg+xml">k</object>? Let’s try this for <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/e5eb05bb23136deb5962f9004ae449e74f7e0547.svg" style="height: 12px;" type="image/svg+xml">k=2</object> (assuming <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d9ec84c4dbd0cb3cb11ec81e619c6441e2f9c96a.svg" style="height: 12px;" type="image/svg+xml">n&gt;2</object>):</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/c0bc9ac12bb892a8ad276272ac6fcdb04b760bdf.svg" style="height: 20px;" type="image/svg+xml">\[S_2=1+w^2+w^4+\cdots+w^{2(n-1)}\]</object> <p>Using the same geometric series sum formula (with <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/19a7d4ca0575d265b7bb21665d1031ae82ac23a2.svg" style="height: 15px;" type="image/svg+xml">r=w^2</object>), we get:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/aef185ae02a5a3fa6fe87d24b5326af854df7aba.svg" style="height: 41px;" type="image/svg+xml">\[S_2=\frac{1-w^{2n}}{1-w^2}=\frac{1-(w^{n})^{2}}{1-w^2}=0\]</object> <p>In general, when <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/13fbd79c3d390e5d6585a21e11ff5ec1970cff0c.svg" style="height: 12px;" type="image/svg+xml">k</object> is not divisible by <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>, the sum is 0. But when <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/13fbd79c3d390e5d6585a21e11ff5ec1970cff0c.svg" style="height: 12px;" type="image/svg+xml">k</object> <em>is</em> divisible by <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>, each power becomes:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/d905642dd5d1ba288340912c53897c9720459cee.svg" style="height: 17px;" type="image/svg+xml">\[w^k=e^{2\pi ik/n}=1\]</object> <p>And <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> of these sum to <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object>. In conclusion:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/80f6898f8f19db5ecfa87b096691cc8c37b5df5f.svg" style="height: 54px;" type="image/svg+xml">\[\sum_{i=0}^{n-1}w^{ki}= \begin{cases} n &amp; k \equiv 0 \pmod{n}\\ 0 &amp; \text{otherwise} \\ \end{cases}\]</object> </div> <div class="section" id="powers-of-roots-of-unity-as-an-orthogonal-basis"> <h2>Powers of roots of unity as an orthogonal basis</h2> <p>Let’s consider the powers of roots of unity as vectors. We’ll continue using the notation:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/82c3159e4ad11eea2305a1be4fd309eb96ca2ec0.svg" style="height: 23px;" type="image/svg+xml">\[\mu_n=\left\{1, w, w^2,\dots,w^{n-1}\right\}\qquad w=e^{2\pi i/n}\]</object> <p>We’ll begin with the 0-th power vector - each of the roots raised to power 0:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/7f1aabba7c282d24ac38976ea8d370e60c446e2e.svg" style="height: 18px;" type="image/svg+xml">\[v_0=\left[1, 1, 1,\dots,1\right]\]</object> <p>Then power 1 - just the roots themselves:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/e5098bb36b15bd6377e5ed73f7b5461ef76297c1.svg" style="height: 22px;" type="image/svg+xml">\[v_1=\left[1, w, w^2,\dots,w^{n-1}\right]\]</object> <p>Each root raised to power 2:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/152ac136c6c0f148beb07a88fb458f3a9ec7d243.svg" style="height: 32px;" type="image/svg+xml">\[v_2=\left[1, w^2, w^4,\dots,w^{2(n-1)}\right]\]</object> <p>And so on, until power <object class="valign-m1 latex-math" data="https://eli.thegreenplace.net/images/math/81f998c5713fded10a77db292e4114ec87997543.svg" style="height: 12px;" type="image/svg+xml">n-1</object>:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/b7809511f4d99148f3689178cd42a42aeb68c57b.svg" style="height: 32px;" type="image/svg+xml">\[v_{n-1}=\left[1, w^{n-1}, w^{2(n-1)},\dots,w^{(n-1)(n-1)}\right]\]</object> <p>To go full linear algebra mode, we’ll collect these vectors into an <object class="valign-m1 latex-math" data="https://eli.thegreenplace.net/images/math/940c9f17d1a1df149e433fd817009f4f3c5e8019.svg" style="height: 12px;" type="image/svg+xml">n\times n</object> matrix:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/de36a955bb0b4d0f2834fc86d990431054481ecd.svg" style="height: 108px;" type="image/svg+xml">\[V=\begin{bmatrix} 1 &amp; 1 &amp; 1 &amp; \cdots &amp; 1 \\ 1 &amp; w &amp; w^2 &amp; \cdots &amp; w^{n-1} \\ 1 &amp; w^2 &amp; w^4 &amp; \cdots &amp; w^{2(n-1)} \\ \vdots &amp; &amp; &amp; &amp; \vdots \\ 1 &amp; w^{n-1} &amp; w^{2(n-1)} &amp; \cdots &amp; w^{(n-1)(n-1)} \\ \end{bmatrix}\]</object> <p>Let’s calculate the inner product of two matrix rows. Recall that when computing the inner product on vectors over <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/706e4005d6760527e1bd99f36d2e91c4f60ad91f.svg" style="height: 12px;" type="image/svg+xml">\mathbb{C}</object>, we conjugate the second element:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/fbd34c6fd92069885c1099bfa2974b6d1ba87587.svg" style="height: 235px;" type="image/svg+xml">\[\begin{aligned} \langle v_i,v_j\rangle&amp;=\sum_{k=0}^{n-1}v_i[k]\cdot v_j[k]^*\\ &amp;=\sum_{k=0}^{n-1}w^{ik}\cdot (w^{jk})^*\\ &amp;=\sum_{k=0}^{n-1}w^{ik}\cdot w^{-jk}\\ &amp;=\sum_{k=0}^{n-1}w^{(i-j)k}\\ \end{aligned}\]</object> <p>But hold on, we’ve just calculated this exact sum in the previous section. We get:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/200abbd5356ef26ed0bf1d40c0e4ebca134c9190.svg" style="height: 54px;" type="image/svg+xml">\[\langle v_i,v_j\rangle=\sum_{k=0}^{n-1}w^{(i-j)k}= \begin{cases} n &amp; (i-j) \equiv 0 \pmod{n}\\ 0 &amp; \text{otherwise} \\ \end{cases}\]</object> <p>Since the vector indices <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/042dc4512fa3d391c5170cf3aa61e6a638f84342.svg" style="height: 12px;" type="image/svg+xml">i</object> and <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/5c2dd944dde9e08881bef0894fe7b22a5c9c4b06.svg" style="height: 16px;" type="image/svg+xml">j</object> only run over <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/3a1270fd6c92e5af5e3dcaab76bcf2f27f048995.svg" style="height: 18px;" type="image/svg+xml">[0..n-1]</object>, this is equivalent to:</p> <object class="align-center" data="https://eli.thegreenplace.net/images/math/dc5783b4ed63090679ee69cbd3564955b870b597.svg" style="height: 54px;" type="image/svg+xml">\[\langle v_i,v_j\rangle=\sum_{k=0}^{n-1}w^{(i-j)k}= \begin{cases} n &amp; i=j\\ 0 &amp; \text{otherwise} \\ \end{cases}\]</object> <p>Which is to say: the vectors <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/f0cd317158e9b3b19134b2c5db4e0861fcd95222.svg" style="height: 11px;" type="image/svg+xml">v_i</object> and <object class="valign-m5 latex-math" data="https://eli.thegreenplace.net/images/math/e20982d9213ce7bd2a82b922940a525f0966b783.svg" style="height: 13px;" type="image/svg+xml">v_j</object> are mutually orthogonal when <object class="valign-m4 latex-math" data="https://eli.thegreenplace.net/images/math/eebecf421c4d33eeab4a0c4da6c20ed8d49e6c6c.svg" style="height: 17px;" type="image/svg+xml">i\neq j</object>. Since we have a set of <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> orthogonal vectors in <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/3b050ca140974a380d383aa92bb4526fb2c62061.svg" style="height: 12px;" type="image/svg+xml">\mathbb{C}^n</object>, these vectors form a <em>basis</em> for <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/3b050ca140974a380d383aa92bb4526fb2c62061.svg" style="height: 12px;" type="image/svg+xml">\mathbb{C}^n</object> - any vector in this space can be represented as a linear combination of <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/f0cd317158e9b3b19134b2c5db4e0861fcd95222.svg" style="height: 11px;" type="image/svg+xml">v_i</object>. This fact has far reaching consequences in math and engineering, since it plays a critical part in forming the DFT (Discrete Fourier Transform), and <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/c9ee5681d3c59f7541c27a38b67edf46259e187b.svg" style="height: 12px;" type="image/svg+xml">V</object> is also known as the <em>Fourier matrix</em>. But this will be a topic for a separate post.</p> <p>Another fun thing to notice before we’re finished here: the matrix <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/c9ee5681d3c59f7541c27a38b67edf46259e187b.svg" style="height: 12px;" type="image/svg+xml">V</object> happens to be <em>symmetric</em> (this is trivial to check by observation). Therefore, its columns are also mutually orthogonal.</p> <hr class="docutils" /> <table class="docutils footnote" frame="void" id="footnote-1" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> <tr><td class="label"><a class="fn-backref" href="#footnote-reference-1">[1]</a></td><td>In general - counting multiplicity - there are exactly <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> complex roots. This is because we’re essentially finding the solutions to the polynomial <object class="valign-m1 latex-math" data="https://eli.thegreenplace.net/images/math/4313a64c645e9272f64540a5ec5e9bd0b6f2ed6b.svg" style="height: 13px;" type="image/svg+xml">z^n-1=0</object>, which has <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> complex solutions according to the Fundamental theorem of algebra.</td></tr> </tbody> </table> <table class="docutils footnote" frame="void" id="footnote-2" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> <tr><td class="label"><a class="fn-backref" href="#footnote-reference-2">[2]</a></td><td>For some notes on converting between the different representations of complex numbers, see my post on <a class="reference external" href="https://eli.thegreenplace.net/2024/notes-on-the-euler-formula/">the Euler formula</a>.</td></tr> </tbody> </table> <table class="docutils footnote" frame="void" id="footnote-3" rules="none"> <colgroup><col class="label" /><col /></colgroup> <tbody valign="top"> <tr><td class="label"><a class="fn-backref" href="#footnote-reference-3">[3]</a></td><td>When <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/4e3e29e8e235c265a2c27015f6f62beaf2241ca6.svg" style="height: 12px;" type="image/svg+xml">k=n</object>, <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/ac0c523a13d2fc48d74f2ee4fc9aa45b7cb8e0ec.svg" style="height: 12px;" type="image/svg+xml">\theta=2\pi</object>, which is the same as <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/a1dffbe89f1ec5a919198de979fca459eb7fdf84.svg" style="height: 12px;" type="image/svg+xml">\theta=0</object>. On a unit circle, the roots start repeating once one full cycle is completed; therefore, there are only <object class="valign-0 latex-math" data="https://eli.thegreenplace.net/images/math/d1854cae891ec7b29161ccaf79a24b00c274bdaa.svg" style="height: 8px;" type="image/svg+xml">n</object> unique roots with <object class="valign-m3 latex-math" data="https://eli.thegreenplace.net/images/math/5354732927c85ee27b18538cebf8d3a3386370d6.svg" style="height: 16px;" type="image/svg+xml">k=0,1,\dots,n-1</object>.</td></tr> </tbody> </table> <script src="https://eli.thegreenplace.net/demos/rootsunity/rootsunity.js"> </script></div>
Original Article
View Cached Full Text

Cached at: 10/18/26, 06:36 AM

# Notes on the complex roots of unity Source: [https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity](https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity) One of the most wonderful aspects of math is how deep we can get by studying seemingly trivial questions\. Consider the roots of unity, where "unity" simply means the number 1\. ## Basics: roots of unity for real numbers Studying the roots of unity usually begins in middle school: what is the square root of 1? Equivalently, what are the solutions to this equation? Well, there are two answers: 1 and \-1\. Similarly, we can ask the question for higher roots; the third roots are solutions to the equation: And so on\. When we’re only dealing with real numbers, that’s pretty much the whole story\. For odd\-degree roots of 1, the only answer is 1; for even\-degree roots of 1, the answer is either 1 or \-1\. When we extend our domain to the complex numbers, things become much more interesting\. ## Basics: roots of unity for complex numbers By the[formal definition](https://en.wikipedia.org/wiki/Root_of_unity), a root of unity is any complex number that yields 1 when raised to a positive integer power \. Rather than looking at*all*the possible roots of 1, it’s often more useful to discuss the roots for a specific given : complex numbers such that \. For example, let’s consider \. We’ve already seen that the roots are 1 and \-1; these are complex numbers with a zero imaginary part\. How about ? There are four roots: 1, \-1, and \. For , the three roots[\[1\]](https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity#footnote-1)are 1, and \. It’s easy enough to check that these indeed give 1 when raised to the third power, but how do we calculate them in the first place? ## Calculating complex roots using polar coordinates A complex number with magnitude 1 can be represented in polar coordinates[\[2\]](https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity#footnote-2)as \. If we raise to the \-th power, we get: The magnitude of is still 1, which is essential if we want to be a \-th root of unity\. Let’s equate to 1: To find the solutions to this equation, we’ll first want to represent 1 itself in polar coordinates\. Let’s use another variable for the angle: What is the value of ? Thinking about the unit circle, is any integer multiple of \- which we’ll express as for : Back to : Or: So the \-th roots of unity are[\[3\]](https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity#footnote-3): ## Some basic examples Let’s begin with \. We have the following roots: For : As expected\. It should be similarly simple to calculate the roots for ; give it a try\. ## Roots of unity and rotations on the unit circle What happens when we multiply some root of unity by itself? Since the magnitude of the root is 1, multiplying by it is akin to a*rotation*along the unit circle by the root’s angle\. For example, consider from the 3rd roots of unity: Multiply by itself: If the angle of is , the angle of is \. Let’s multiply by once more: The result is 1, as expected \(after all, is a 3rd root of unity\)\. This visualization shows how roots of unity appear on the unit circle and how raising them to powers rotates the roots until finally : The nth roots of unity, equally spaced around the unit circle\. Use the root selector below\.Roots*n*Root*k* The powers of the selected root\. Use the power slider below\.Power*m* Select first; this shows the \-th roots as blue dots on the unit circle\. Now you can click any of the roots, and see its powers in the lower plot \- drag the slidebar to see the rotations\. If you spend some time playing with this, you’ll notice that some roots \- for example when \- go back to 1 when raised to a smaller power than \. We’ll revisit this outcome when we discuss the group\-theoretic aspects of roots of unity\. ## Geometry: roots of unity and regular polygons As we’ve seen, the roots of unity are evenly spaced along the unit circle on the complex plane\. If we connect the roots with straight lines to their immediate neighbors, we’ll notice something interesting: Adjacent nth roots of unity joined to form a regular polygon on the unit circle\.Roots*n* For different values of , we get the[Regular Polygons](https://en.wikipedia.org/wiki/Regular_polygon)\! It’s pretty easy to prove this if we connect each root with a straight line to the origin\. The triangles we get are congruent, because the sides from the origin to the roots are all of length 1, and the central angles are all \. Therefore, both the sides of the polygons and their angles are identical, which makes them regular\. ## Conjugates of roots of unity Suppose we have the root of unity: For some and \. If we take the reciprocal of : Then: So is also an n\-th root of unity\. While the powers of are rotating counter\-clockwise on the unit circle until they land on 1 for the \-th power, the powers of similarly rotate*clockwise*\. also happens to be the complex conjugate of : So if we have: As the \-th roots of unity, then: Are also \-th roots of unity\. In fact, they are the same roots, because for any given positive : So enumerating the conjugate roots is the same as enumerating the roots themselves in the opposite order\. ## Group theory: the cyclic group of roots of unity Let’s look at the set of \(roots of unity\) for some : This set \- along with the multiplication operation \- forms a*group*\. Let’s prove that\. **Closure:**Assume \(so and \)\. Then: Therefore \. **Identity:**The number , so it can serve as our identity element for the group\. **Associativity:**Taken directly from the associativity of the multiplication operation on complex numbers\. **Inverse:**We’ve just seen in the section on conjugates that is an \-th root of unity when is\. So the inverse exists and is part of the group\. Because the operation we have is just complex multiplication, we can trivially derive additional properties, like commutativity\. Therefore, the group is*Abelian*\. Finally, we can show that the group is also*cyclic*and discuss its*generators*\. For slightly simpler notation, let’s denote \. So the group can be represented as: This makes it obvious that the group is cyclic \- all its elements can be expressed as integer powers of \. And is a generator for the group\. But interestingly, is not the only generator for this group\. Any can be a generator, as long as and are co\-prime\. For example, consider the group : Obviously, is a generator for this group\. But isn’t\! If we raise it to various powers we get: Since , the powers of repeat after just three steps, so they only reach three out of six group elements\. But if and are co\-prime, is a generator; in the case of , we can easily verify that and are the only generators\. The roots that are generators for the group are also called the*primitive roots*\. Let’s take the \-roots of unity \(\), denoted as above with: What’s the sum of all these roots? This is just the sum of a geometric series with the first term 1 and common ratio \. Therefore: If you look carefully at the visualization shown above \- this makes sense geometrically\. All the roots of unity are evenly spread around the unit circle, so viewing them as vectors, all components cancel out\. How about the sum of roots raised to some integer power ? Let’s try this for \(assuming \): Using the same geometric series sum formula \(with \), we get: In general, when is not divisible by , the sum is 0\. But when*is*divisible by , each power becomes: And of these sum to \. In conclusion: ## Powers of roots of unity as an orthogonal basis Let’s consider the powers of roots of unity as vectors\. We’ll continue using the notation: We’ll begin with the 0\-th power vector \- each of the roots raised to power 0: Then power 1 \- just the roots themselves: Each root raised to power 2: And so on, until power : To go full linear algebra mode, we’ll collect these vectors into an matrix: Let’s calculate the inner product of two matrix rows\. Recall that when computing the inner product on vectors over , we conjugate the second element: But hold on, we’ve just calculated this exact sum in the previous section\. We get: Since the vector indices and only run over , this is equivalent to: Which is to say: the vectors and are mutually orthogonal when \. Since we have a set of orthogonal vectors in , these vectors form a*basis*for \- any vector in this space can be represented as a linear combination of \. This fact has far reaching consequences in math and engineering, since it plays a critical part in forming the DFT \(Discrete Fourier Transform\), and is also known as the*Fourier matrix*\. But this will be a topic for a separate post\. Another fun thing to notice before we’re finished here: the matrix happens to be*symmetric*\(this is trivial to check by observation\)\. Therefore, its columns are also mutually orthogonal\. --- [\[1\]](https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity#footnote-reference-1)In general \- counting multiplicity \- there are exactly complex roots\. This is because we’re essentially finding the solutions to the polynomial , which has complex solutions according to the Fundamental theorem of algebra\.[\[2\]](https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity#footnote-reference-2)For some notes on converting between the different representations of complex numbers, see my post on[the Euler formula](https://eli.thegreenplace.net/2024/notes-on-the-euler-formula/)\.[\[3\]](https://eli.thegreenplace.net/2026/notes-on-the-complex-roots-of-unity#footnote-reference-3)When , , which is the same as \. On a unit circle, the roots start repeating once one full cycle is completed; therefore, there are only unique roots with \.

Similar Articles

Terence Tao explains 6 essential mathematical concepts [video]

Hacker News Top

This article summarizes the six fundamental concepts of mathematics explained by mathematician Terence Tao in a Big Think interview, including numbers, algebra, geometry, probability, and more, exploring their historical development and applications.

Mathematical Origami

Hacker News Top

Mathigon 介绍一个关于数学折纸的互动学习页面,涵盖柏拉图立体、阿基米德立体等多面体主题,并链接到 Polypad 上的 3D 模型探索工具。

Sum-product, unit distances, and number fields

Hacker News Top

Thomas Bloom provides an expository blog post on recent counterexamples to the Erdős unit distance conjecture and sum-product conjecture over the reals, including an OpenAI-assisted disproof of the unit distance conjecture and a collaborative disproof of the sum-product conjecture, sketching the constructions and intuition behind them.

Calculus with Julia

Hacker News Top

A set of open-source notes for learning calculus using the Julia programming language, emphasizing graphical, numerical, and algebraic approaches with self-graded exercises.