Archive for November, 2008

Building a polynomial from its roots

November 22, 2008

Suppose we are given a set of $n \geq 2$ distinct real numbers $\mathcal{R} = \{r_1, r_2, \ldots, r_n\}$, and we build a monic univariate polynomial (over field $\mathbb{R}$) of degree $n$ whose $n$ distinct roots are the elements of set $\mathcal{R}$

$p_n(x) = \displaystyle\prod_{i=1}^n (x - r_i) = \displaystyle\sum_{m=0}^n a_{m,n} x^m$,

where $a_{m,n} \in \mathbb{R}$ is the coefficient of monomial $x^m$. The second subscript in $a_{m,n}$ tells us that the coefficient corresponds to a polynomial whose degree is $n$.

Problem: for $n \geq 2$, what are the values of the coefficients $\{a_{m,n}\}_{m=0}^{n}$ in terms of the roots $\{r_i\}_{i=1}^n$?

At first glance, this problem seems elementary. However, I had never thought of it and I found it quite interesting. I prefer to think of examples before attempting to see the “big picture”, so let us consider the simplest cases.

_____

Case $n=1$

The monic polynomial of degree $1$ whose root is $r_1$ is

$p_1(x) = x - r_1$

and the coefficients are

$\left[\begin{array}{c}a_{0,1}\\a_{1,1}\end{array}\right] = \left[\begin{array}{c} -r_1\\1\end{array}\right]$.

_____

Case $n=2$

The monic polynomial of degree $2$ whose roots are $r_1, r_2$ is

$\begin{array}{rl} p_2(x) &= (x - r_1) (x - r_2)\\ &= x^2 - (r_1 + r_2) x + r_1 r_2\end{array}$

and the coefficients are

$\left[\begin{array}{c}a_{0,2}\\a_{1,2}\\a_{2,2}\end{array}\right] = \left[\begin{array}{c}r_1 r_2\\-(r_1+r_2)\\1\end{array}\right]$.

_____

Case $n=3$

The monic polynomial of degree $3$ whose roots are $r_1, r_2, r_3$ is

$\begin{array}{rl} p_3(x) &= (x - r_1) (x - r_2) (x - r_3)\\ &= x^3 - (r_1+r_2 + r_3) x^2 + (r_1 r_2 + r_1 r_3 + r_2 r_3) x - r_1 r_2 r_3\\\end{array}$

and the coefficients are

$\left[\begin{array}{c}a_{0,3}\\a_{1,3}\\a_{2,3}\\a_{3,3}\end{array}\right] = \left[\begin{array}{c} - r_1 r_2 r_3\\ r_1 r_2 + r_1 r_3 + r_2 r_3\\ -(r_1+r_2 + r_3)\\1\end{array}\right]$.

_____

The coefficients $\{a_{m,n}\}_{m=0}^{n}$ can be computed in a recursive fashion. Consider the monic polynomials

$p_{k}(x) = \displaystyle\prod_{i=1}^{k} (x - r_i)$

and

$p_{k+1}(x) = \displaystyle\prod_{i=1}^{k+1} (x - r_i) = (x - r_{k+1}) \displaystyle\prod_{i=1}^k (x - r_i)$,

then $p_{k+1} = (x - r_{k+1}) p_k(x)$, and thus

$\begin{array}{rl} p_{k+1}(x) &= (x - r_{k+1})\displaystyle\sum_{m=0}^k a_{m,k} x^m\\ &= \displaystyle\sum_{m=0}^k a_{m,k} x^{m+1} - \displaystyle\sum_{m=0}^k r_{k+1} a_{m,k} x^m.\\\end{array}$

Note that

$\begin{array}{rl} \displaystyle\sum_{m=0}^k a_{m,k} x^{m+1} &= \displaystyle\sum_{m=1}^k a_{m-1,k} x^m + a_{k,k} x^{k+1}\\ \displaystyle\sum_{m=0}^{k} r_{k+1} a_{m,k} x^m &= r_{k+1} a_{0,k} + \displaystyle\sum_{m=1}^k r_{k+1} a_{m,k} x^m\end{array}$

and therefore

$p_{k+1}(x) = a_{k,k} x^{k+1} + \displaystyle\sum_{m=1}^k \left(a_{m-1,k} - r_{k+1} a_{m,k}\right) x^m - r_{k+1} a_{0,k}$.

We can write $p_{k+1}(x)$ in the expanded form in terms of the coefficients $\{a_{m,k+1}\}_{m=0}^{k+1}$

$p_{k+1}(x) = a_{k+1,k+1} x^{k+1} + \displaystyle\sum_{m=1}^k a_{m,k+1} x^m + a_{0,k+1}$

and therefore we can write the coefficients $\{a_{m,k+1}\}_{m=0}^{k+1}$ in terms of the coefficients $\{a_{m,k}\}_{m=0}^{k}$, as follows

$a_{m,k+1} = \displaystyle\left\{\begin{array}{rl} - r_{k+1} a_{0,k} & \text{if} \quad{} m = 0\\ a_{m-1,k} - r_{k+1} a_{m,k} & \text{if} \quad{} 1 \leq m \leq k\\ a_{k,k} & \text{if} \quad{} m=k+1\\ \end{array}\right.$

Hence, starting with the zero-degree monic polynomial $p_0(x)$, whose only coefficient is $a_{0,0} = 1$, we can build $p_1(x)$, the monic polynomial of degree $1$ whose root is $r_1$. From $p_1(x)$, and given a second root $r_2$, we can build $p_2(x)$, the monic polynomial of degree $2$ whose roots are $r_1, r_2$. Iterating successively, we can build $p_n(x)$, the monic polynomial of degree $n$ whose roots are $r_1,r_2, \ldots, r_n$.

Representing complex numbers as 2×2 matrices

November 9, 2008

We can represent complex numbers as $2 \times 2$ real matrices, such that arithmetic operations $(+, -, \times, \div)$ on complex numbers become equivalent to arithmetic operations on their matrix representations.

Consider a matrix-valued function $M: \mathbb{C} \rightarrow \mathbb{R}^{2 \times 2}$ defined as

$M(z) = \left[\begin{array}{cc} \Re\{z\} & -\Im\{z\}\\ \Im\{z\} & \Re\{z\}\\ \end{array}\right]$,

where $\Re\{z\}$ and $\Im\{z\}$ are the real and imaginary parts of $z \in \mathbb{C}$, respectively. It can be shown that for all $z_1, z_2 \in \mathbb{C}$, we have that

• $M(z_1 + z_2) = M(z_1) + M(z_2)$.
• $M(z_1 - z_2) = M(z_1) - M(z_2)$.
• $M(z_1 z_2) = M(z_1) M(z_2)$.
• $M(z_1 / z_2) = [M(z_2)]^{-1} M(z_1)$, if $z_2 \neq 0$.

There seems to be an homomorphism here.

__________

Matrix Representation of a Complex Number

Let $z = a + i b$, where $i = \sqrt{-1}$ and $a,b \in \mathbb{R}$, be a complex number. Its matrix representation is

$M(z) = M(a + i b) = \left[\begin{array}{cc} a & -b\\ b & a\\ \end{array}\right] = a \left[\begin{array}{cc} 1 & 0\\ 0 & 1\\ \end{array}\right] + b \left[\begin{array}{cc} 0 & -1\\ 1 & 0\\ \end{array}\right]$.

Let matrices $I_2, Q \in \mathbb{R}^{2 \times 2}$ be

$I_2 = \left[\begin{array}{cc} 1 & 0\\ 0 & 1\\ \end{array}\right], \quad{} Q = \left[\begin{array}{cc} 0 & -1\\ 1 & 0\\ \end{array}\right]$,

then the matrix representation of $z \in \mathbb{C}$ is

$M(z) = M(a + i b) = a I_2 + b Q$.

Note that both $I_2$ and $Q$ are orthogonal matrices, and therefore $Q^{-1} = Q^T$. Since $I_2$ is the $2 \times 2$ identity matrix, we have that $I_2$ and $Q$ commute, i.e., $I_2 Q = Q I_2$.

The matrix representation of the complex conjugate of $z$ is

$M(z^*) = M(a - i b) = a I_2 - b Q = M^T (z)$,

which follows from the fact that matrix $Q$ is skew-symmetric, i.e., $Q^T = -Q$. The complex conjugate of a complex number can thus be computed by transposing its matrix representation. Since $Q^T = Q^{-1}$ and $Q^T = - Q$, we have $Q^2 = - I_2$.

The square of the magnitude of a complex number, $|z|^2 = zz^*$, is equal to the determinant of its matrix representation, as follows

$\det(M(z)) = \det(M(a + i b)) = \begin{vmatrix} a & -b \\ b & a\\ \end{vmatrix} = a^2 + b^2 = |z|^2$.

A complex number written in the cartesian form, $z = a + i b$, can be converted to its polar form, $z = \rho e^{i \theta}$, where $\rho = \sqrt{a^2 + b^2}$ and $\theta = \arg(z)$. Given a complex number in the polar form $z = \rho e^{i \theta}$, its cartesian form is

$z = \rho (\cos(\theta) + i \sin(\theta))$,

and its matrix representation is

$M(z) = \rho \left[\begin{array}{cc} \cos(\theta) & -\sin(\theta)\\ \sin(\theta) & \cos(\theta)\\ \end{array}\right] = \rho R(\theta)$,

where

$R(\theta) = \left[\begin{array}{cc} \cos(\theta) & -\sin(\theta)\\ \sin(\theta) & \cos(\theta)\\ \end{array} \right]$

is a rotation matrix that rotates a vector in $\mathbb{R}^2$ by a counterclockwise angle $\theta$ radians, leaving the vector’s $\|\cdot\|_2$ unchanged. Matrix $R(\theta)$ is orthogonal, and thus $R^{-1} (\theta) = R^T (\theta)$. Given that

$\sin(-\theta) = - \sin(\theta), \quad{} \cos(-\theta) = \cos(\theta)$,

we have $R(-\theta) = R^T (\theta) = R^{-1}$. As $\det(R(\theta)) = 1$ for any value of $\theta$, we can conclude that $R(\theta) \in \text{SO}(2)$.

Finally, note that $Q = R(\frac{\pi}{2})$, i.e., matrix $Q$ rotates a vector in $\mathbb{R}^2$ $\pi/2$ radians counter-clockwise. If we multiply a complex number by $i$, we rotate it by a counterclockwise angle of $\pi/2$ radians

$i z = i \rho e^{i \theta} = \rho e^{i (\theta + \frac{\pi}{2})}$,

and in terms of matrix representations, this is equivalent to multiplying $M(z)$ by matrix $Q$. It does not matter if we multiply by $Q$ on the left or on the right, because matrices $I_2$ and $Q$ do commute.

__________

Arithmetic Operations

Let $z_1 = a_1 + i b_1$ and $z_2 = a_2 + i b_2$ be two complex numbers. Their addition/subtraction is thus

$z_1 \pm z_2 = (a_1 \pm a_2) + i (b_1 \pm b_2)$,

and from the rules of matrix addition / subtraction it can easily be shown  that $M(z_1) \pm M(z_2) = M(z_1 \pm z_2)$.

It’s easier to compute products of complex numbers if we write them in the polar form, i.e., $z_1 = \rho_1 e^{i \theta_1}$ and $z_2 = \rho_2 e^{i \theta_2}$. The product is thus $z_1 z_2 = \rho_1 \rho_2 e^{i (\theta_1 + \theta_2)}$. The product of the matrix representations is

$M(z_1) M(z_2) = \rho_1 R(\theta_1) \rho_2 R(\theta_2) = \rho_1 \rho_2 R(\theta_1 + \theta_2) = M(z_1 z_2)$,

since $R(\theta_1) R(\theta_2) = R(\theta_1 + \theta_2)$. Dividing $z_1 \in \mathbb{C}$ by $z_2 \in \mathbb{C} \setminus \{0\}$ yields

$\displaystyle\frac{z_1}{z_2} = \frac{\rho_1}{\rho_2} e^{i (\theta_1 - \theta_2)}$,

whose corresponding matrix representation is

$\displaystyle M(z_1 / z_2) = \frac{\rho_1}{\rho_2} R(\theta_1 - \theta_2)$.

Note that

$M^{-1} (z_2) M(z_1) = \displaystyle \frac{\rho_1}{\rho_2} R(-\theta_2) R(\theta_1) = \frac{\rho_1}{\rho_2} R(\theta_1 - \theta_2)$

and therefore $M^{-1} (z_2) M(z_1) = M(z_1 / z_2)$.

We can conclude that arithmetic operations on complex numbers are equivalent to arithmetic operations on the matrices representing such complex numbers.

I have absolutely no idea what use this matrix representation could possibly have, but it’s quite interesting nonetheless.

__________

Related: