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.

Tags:,
Posted in Mathematics | Leave a Comment »

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:

Tags:, , ,
Posted in Mathematics | 9 Comments »

Follow

Get every new post delivered to your Inbox.

Join 47 other followers