A complex number is a number that includes an imaginary part. An imaginary number is a solution to the equation $\sqrt{-1}$, often denoted by the letter $i$. $i = \sqrt{-1}$ This of course has no solution in the real number space and so imaginary numbers are mathematician's way of dealing with this type of solution. Complex numbers have a surprising number of applications in computer science and engineering, such as the [[discrete Fourier transform]], which decomposes a signal into component wave parts. Complex numbers are typically expressed as a [[vector]] with two parts, one real an one imaginary in the form $x + yi$ > [!NOTE] Notation > [[Python]] and other applications in engineering and robotics use the letter $j$ rather than $i$ to denote imaginary numbers. ## complex plane Complex numbers can be visualized in the **complex plane**. #diagram ## arithmetic To add (or subtract) two imaginary numbers, simply add (or subtract) the two real parts and the two imaginary parts. $(x_1 + y_1i) + (x_2 + y_2i) = (x_1 + x_2) + (y_1 + y_2) i$ To multiply two imaginary numbers, use algebraic multiplication to create a polynomial complex number. $(x_1 + y_1i)(x_2 + y_2i) = x_1 x_2 + x_1y_2i + x_2 y_1i + y_1 y_2 i^2$ Because $i^2 = -1$ this simplifies to $x_1 x_2 + x_1y_2i + x_2 y_1i + y_1 y_2 i^2 = (x_1 x_2 - y_1 y_2) + (x_1 y_2 + x_2 y_1)i$ To divide two complex numbers requires the complex conjugate of the denominator. Given two complex numbers $z_1$ and $z_2$ $\frac{z_1}{z_2} = \frac{z_1 \bar z_2}{z_2 \bar z_2} = \frac{1}{|z_2|^2}z_1 \bar z_2$ Note we are simply multiplying the numerator and denominator by $\bar z_2$ to derive this formula. ## complex conjugate The complex conjugate is a complex number that, when multiplied by the original complex number, returns a real number with no imaginary part. Given a complex number $z = x + yi$ the conjugate $\bar z = x-yi$. $z \bar z = (x + yi)(x - yi) = x^2 - y^2i^2 = x^2 + y^2$ In the complex plane, the complex conjugate is a reflection of the complex number about the real axis. #diagram ## modulus The modulus (or absolute value) of a complex number is the length of the vector. For a complex number $z = x + yi$ the modulus, denoted as $|z|$ is $|z| = \sqrt{x^2 + y^2}$ The modulus can also be calculated as the multiplication of a vector and its complex conjugate. $|z| = \sqrt{z \bar z}$ ## radian form The complex number in form $x + yi$ is in rectilinear form. This can also be written in the form of radians with a length (modulus) and angle (also called phase or argument). #diagram Expressing complex numbers in radian form can simplify multiplication. To multiply two complex numbers, multiply the moduli and add the phases. $(r_1, \theta_1) (r_2, \theta_2) = r_1 r_2, \ \theta_1 + \theta_2$ ## de Moivre's theorem Using de Moivre's theorem we can express complex numbers using [[Euler's number]] $e$. $z = r e^{i \theta} = r (\cos \theta + \sin \theta i)$ where the real number part $x = r \cos \theta$ and the imaginary part $y = r \sin \theta$. #diagram Multiplication in this form is $z_1 z_2 = (r_1 r_2)e^{(\theta_1 + \theta_2)i}$ which helps with intuition of why the phase of the vectors are added when multiplying two complex numbers. ## root of unity A root of unity, sometimes called de Moivre number, is a complex number that yields $1$ when raised to some positive integer power $n$. $\omega$ is said to be an $n^{th}$ root of unity if $\omega^n = 1$. It can be shown that $\omega_n = e^{2 \pi / n}$. Thus the modulus of a root of unity is always $1$ and the number of roots of unity is $2 \pi / n$ for a polynomial of degree $n$. Gauss showed that any polynomial of degree $n$ has exactly $n$ roots. For example, $x^2 = 1$ has two solutions, $(1, -1)$. What about $x^4$? The solution includes $(1, -1)$, but there must be two additional solutions. As it turns out, the additional solutions are complex and include $(i, -i)$. What about $x^3 = 1$? We can use the roots of unity and de Moivre's theorem to solve for the complex parts of this solution. The first root of unity is $\omega_3$, the second is $\omega_3^2$ and the third is $\omega_3^3$. $w_3 = e^{2 \pi / 3} = cos(\frac{2 \pi}{3}) + sin(\frac{2 \pi}{3})i = \frac{-1}{2} + \frac{\sqrt{3}}{2}i$ $w_3^2 = e^{(2 \pi / 3) * 2} = cos(\frac{4 \pi}{3}) + sin(\frac{4 \pi}{3})i = \frac{-1}{2} - \frac{\sqrt{3}}{2}i$ $w_3^3 = e^{(2 \pi / 3) * 3} = cos(\frac{6 \pi}{3}) + sin(\frac{6 \pi}{3})i = 1 + 0i$ We find that $1$ is a solution, as expected and there are two complex solutions, one at $2 \pi /3 = 120 ^o$ and another at $4 \pi / 3 = 240^o$. The original root $\omega_n$ is called the **generator root** and the $k^{th}$ root of unity is $\omega_n^k$ . Interestingly, the roots of unity rotate in $n/k$ steps assuming that $k$ divides $n$. That is to say, each root of unity has a frequency. This provides a way to interpret sequences in terms of their roots of unity, which is the basis of the [[discrete Fourier transform]]. - most beautiful equation, Eulers formula (YT video) ## complex numbers in python ```python import(cmath) # Create a complex number z1 = complex(1, 1) # complex number 1 + j z1 = 1.0 + 1.0j # alt format for complex number 1 + j # Convert to polar (r1, ang1) = cmath.polar(z1) ``` ```python import(math) def get_roots_of_unity(n): assert n >= 2 angles = [2.0 * math.pi * k/n for k in range(n)] lst = [math.cos(ang) + math.sin(ang)*1j for ang in angles] return lst # Watch out for floating point errors! ``` ## discrete Fourier transform Given an array $[a_0, a_1, a_2, \dots, a_{n-1}]$ (often called a "signal"), and the corresponding polynomial function $f(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1}$ a discrete Fourier transform (DFT) converts the original array to the Fourier series $[A_0, A_1, \dots, A_{n-1}]$ for each $A_k = f(\omega_n^k)$ where $\omega^k_n$ is the $k^{th}$ root of unity for an array of size $n$. The inverse Fourier transform returns the original array using the conjugate generator. The polynomial function $F(x) = \frac1n \Big (A_0 + A_1x + A_2x^2 + \dots + A_n x^n \Big)$ returns the original array $[a_0, a_1, a_2, \dots, a_{n-1}]$ for each $A_k = F(\bar \omega_n^k)$. In other words, use the complex conjugate of $\omega^k_n$ in the opposite process of the DFT to recover the original array in the inverse Fourier transform. The interpretation of the Fourier coefficient is then $a_i = \sum_{k=0}^{n-1} A_k(\bar \omega_n^i)^k$ Each $\bar \omega_n^i$ can be said to rotate at some frequency $n / i$. $A_0$ never rotates, and in fact represents the average value of the dataset. Each $A_n$ up to $n/2$ rotates counterclockwise at a unique frequency. Each $A_n$ where $n > n/2$ is simply a reflection around the real axis of the frequency $n/2$. ## fast Fourier transform A naive implementation of the [[discrete Fourier transform]] would take $\Theta(n^2)$ time. The fast Fourier transform (FFT) is a [[divide-and-conquer]] algorithm to complete a DFT in $\theta(n \lg n)$. Using the same idea, the inverse Fourier transform can also be completed in the same time. ```python from numpy.fft import fft, ifft, fftfreq N = len(data) my_fft = fft(data) frequencies = fftfreq(N, 1/rate) ```