Roots of Unity Filter Part 1 - Complex Numbers

Note

This is a three part series I wrote back in 2019 on a technique applicable to certain competitive math problems: roots of unity filters. The first two parts are just a recap of complex numbers and roots of unity respectively. If you're already comfortable with both of these topics, feel free to skip to Part 3.

Overview

Definition

A complex number is a number zz that can be expressed in the form z=a+biz = a + bi, where aa and bb are real numbers, and i=−1i = \sqrt{-1}.

aa and bb are known as the real and imaginary components of zz respectively.

All complex numbers can be graphed on the coordinate plane, where the x-axis represents the real component of the complex number, while the y-axis represents the imaginary component of the complex number.

For instance, the complex number 1+2i1 + 2i can be graphed as shown below:

(1, 2) on Coordinate Plane

The method of representing a complex number as z=a+biz = a + bi is known as rectangular form since we use a rectangular coordinate system. When we graph a complex number zz, we can derive actually derive a different way of representing that complex number: polar form.

To express a complex number in polar form, we use the angle θ\theta it makes with the positive x-axis and the positive distance rr from the origin. If we have a complex number z=a+biz = a + bi, then we can derive these two parameters with a bit of trigonometry. The angle θ\theta is known as the argument of zz, or arg(z)\text{arg}(z). The distance rr is known as the magnitude of zz, or ∣z∣\lvert z \rvert.

Theorem

For a complex number z=a+biz = a + bi, the angle θ\theta that zz makes with the positive x-axis can be expressed as:

θ=arg(z)=atan(ba) \theta = \text{arg}(z) = \text{atan}\left( \dfrac{b}{a} \right)

The magnitude rr can be expressed as:

r=∣z∣=a2+b2 r = |z| = \sqrt{a^2 + b^2}

However, we can also go from polar form back to rectangular form with the following relationship:

Theorem

For a complex number zz with argument θ\theta and magnitude rr can be expressed in rectangular form z=a+biz = a + bi with:

a=rcos⁡(θ)a = r \cos(\theta)
b=rsin⁡(θ)b = r \sin(\theta)

This implies that zz can be expressed in the following manner, which i sknown as the polar form of zz.

z=a+bi=r(cos⁡(θ)+isin⁡(θ))=rcis(θ) z = a + bi = r(\cos(\theta) + i \sin(\theta)) = r \text{cis}(\theta)

We use cis(θ)\text{cis}(\theta) as a shorthand for writing cos⁡(θ)+isin⁡(θ)\cos(\theta) + i \sin(\theta)

There is one final form of a complex number, the complex exponential form. The proof for this relationship is beyond the scope of this document, but there are plenty of excellent tutorials by people like 3Blue1Brown who have covered this topic in detail.

Theorem

For a complex number zz with argument θ\theta and magnitude rr can be expressed as:

z=reiθz = re^{i \theta}

de Moivre's Theorem

One super important theorem about complex numbers and their exponents is de Moivre's Theorem.

Theorem

z=rcis(θ)z = r\text{cis}(\theta)
zn=rncis(nθ)z^n = r^n\text{cis}(n\theta)

This theorem can be proven by considering the complex exponential form of zz.

z=rcis(θ)=reiθz = r\text{cis}(\theta)=re^{i\theta}
zn=rn(eiθ)n=rneinθz^n = r^n(e^{i\theta})^n = r^ne^{in\theta}
zn=rncis(nθ)z^n = r^n\text{cis}(n\theta)

Arithmetic Operations

Complex numbers, much like real numbers, can be added, subtracted, and multiplied. The rules for applying these arithmetic operations to complex numbers are the same as what one would expect as long as it is remembered that i2=−1i^2 = -1 when doing multiplication.

Example

(1+2i)+(3+4i)=4+6i(1 + 2i) + (3 + 4i) = 4 + 6i
(1+2i)−(3+4i)=−2−2i(1 + 2i) - (3 + 4i) = -2 - 2i
(1+2i)∗(3+4i)=(3−8)+(6+4)i=−5+10i(1 + 2i) * (3 + 4i) = (3 - 8) + (6 + 4)i = -5 + 10i

Multiplication

When multiplying complex numbers, we obtain an interesting property regarding the magnitude and angle of the resulting product.

Theorem

When zz and ww are two complex numbers, we can obtain the following information about their product z∗wz * w:

∣z∗w∣=∣z∣∗∣w∣|z * w| = |z| * |w|
arg(z∗w)=arg(z)+arg(w)\text{arg}(z * w) = \text{arg}(z) + \text{arg}(w)

We can prove this pretty easily once again with the complex exponential form:

z=rzeiθz,w=rweiθwz = r_ze^{i\theta_z}, w = r_we^{i\theta_w}
∣z∣=rz,∣w∣=rw|z| = r_z, |w| = r_w
arg(z)=θz,arg(w)=θw\text{arg}(z) = \theta_z, \text{arg}(w) = \theta_w
z∗w=rzeiθz∗rweiθw=rzrwei(θz+θw)z * w = r_ze^{i\theta_z} * r_we^{i\theta_w} = r_zr_we^{i(\theta_z+\theta_w)}
∣z∗w∣=rz∗rw=∣z∣∗∣w∣|z * w| = r_z * r_w = |z| * |w|
arg(z∗w)=θz+θw=arg(z)+arg(w)\text{arg}(z * w) = \theta_z + \theta_w = \text{arg}(z) + \text{arg}(w)

With this theorem, we can make multiplying numbers in polar form very easy, since all we have to do is multiply the magnitudes and add the arguments.

Example

3cis(π4)∗4cis(3π4)=12cis(π)=−123\text{cis}\left(\frac{\pi}{4}\right) * 4\text{cis}\left(\frac{3\pi}{4}\right) = 12 \text{cis}(\pi) = -12

Note that applying this principle to exponentiation is what led us to de Moivre's theorem earlier.

Division

Division of complex numbers is a bit more interesting, and there are two ways to approach it. The first involves complex conjugates to make the denominator real, similar to how one would rationalize a denominator with radicals in it. We will go over conjugates in-depth soon.

Example

1+2i3+4i=1+2i3+4i∗3−4i3−4i=11+10i32+42=11+10i25\dfrac{1 + 2i}{3 + 4i} = \dfrac{1 + 2i}{3 + 4i} * \dfrac{3 - 4i}{3 - 4i} = \dfrac{11 + 10i}{3^2 + 4^2} = \dfrac{11 + 10i}{25}

The other method is to use de Moivre's theorem above with regards to the argument and the magnitude. If we have two complex numbers zz and ww and we want to perform zw\frac{z}{w}, we can write it as z∗w−1z * w^{-1}.

We can then see from de Moivre's theorem that w−1w^{-1} will be the same as ww but it will have a magnitude of 1∣w∣\frac{1}{\lvert w \rvert} and an argument of −arg(w)-\text{arg}(w). Then, we just need to multiply the two numbers with the same process as above.

As a result, you can think of division as dividing the magnitudes and subtracting the arguments.

Example

8cis(3π4)÷4cis(π2)=2cis(π4)8\text{cis}\left(\frac{3\pi}{4}\right) \div 4\text{cis}\left(\frac{\pi}{2}\right) = 2\text{cis}\left(\frac{\pi}{4}\right)

Conjugates

Definition

The conjugate of a complex number z=a+biz = a + bi is denoted as zˉ=a−bi\bar{z} = a - bi

There are a few important theorems that you can use with complex conjugates.

Theorem

z∗zˉ=∣z∣2z * \bar{z} = |z|^2

We can prove this pretty easily by considering the rectangular form of z=a+biz = a + bi.

z∗zˉ=(a+bi)∗(a−bi)=a2+b2=a2+b22=∣z∣2z * \bar{z} = (a + bi) * (a - bi) = a^2 + b^2 = \sqrt{a^2 + b^2}^2 = |z|^2

Theorem

rcis(θ)‾=rcis(−θ)\overline{r\text{cis}(\theta)} = r\text{cis}(-\theta)

We can also prove this by realizing that the complex conjugate just reflects the complex coordinate over the x-axis, which in turn just multiplies the angle by −1-1.

Theorem

The complex conjugate operator is distributive.

z+w‾=zˉ+wˉ\overline{z + w} = \bar{z} + \bar{w}
z−w‾=zˉ−wˉ\overline{z - w} = \bar{z} - \bar{w}
z∗w‾=zˉ∗wˉ\overline{z * w} = \bar{z} * \bar{w}
zw‾=zˉwˉ\overline{\dfrac{z}{w}} = \dfrac{\bar{z}}{\bar{w}}
za‾=zˉa\overline{z^a} = \bar{z}^a

We can prove all of these pretty easily with rectangular coordinates, so they are omitted.

Theorem

If a complex number zz is a root of a polynomial with real coefficients, then zˉ\bar{z} is also a root of that polynomial.

We can prove this by applying the operations above while also making use of the fact that the conjugate of a real number aa is equal to aa.

P(x)=anxn+an−1xn−1+...+a1x+a0=∑i=0naixiP(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0 = \sum_{i = 0}^{n}a_ix^i
P(z)=∑i=0naizi=0P(z) = \sum_{i = 0}^{n}a_iz^i = 0
P(zˉ)=∑i=0naizˉi=∑i=0naizi‾=∑i=0naiˉzi‾=∑i=0naizi‾=∑i=0naizi‾P(\bar{z}) = \sum_{i = 0}^{n}a_i\bar{z}^i = \sum_{i = 0}^{n}a_i\overline{z^i} = \sum_{i = 0}^{n}\bar{a_i}\overline{z^i} = \sum_{i = 0}^{n}\overline{a_iz^i} = \overline{\sum_{i = 0}^{n}a_iz^i}
P(zˉ)=0ˉ=0P(\bar{z}) = \bar{0} = 0

Side Note

With complex exponentials, you can actually derive the formulas for sine and cosine addition. Additionally, you can derive the formulas for the sine and cosine of large multiples of angles with de Moivre's theorem. Look forward to another post that will go over this in depth!