Isomorphism between Polynomials and Vectors over Complex Numbers

In Theorem A-11.5 (§A-11.5), we learned the isomorphic mapping

σ : f (X) \in ℤ_{t} [X] ∕ (X^{n} + 1) \to (f (x_{0}), f (x_{1}), f (x_{2}), \dots, f (x_{n - 1})) \in ℤ_{t}^{n}

, where

x_{0}, x_{1}, x_{2}, \dots, x_{n - 1} \in ℤ

are the (

(μ = 2 n)

-th primitive) roots of the cyclotomic polynomial

X^{n} + 1

, which are

ω, ω^{3}, ω^{5}, \dots, ω^{2 n - 1}

, where

ω

can be any root of

X^{n} + 1

(i.e., since each

ω

is a generator of all roots). In this subsection, we will demonstrate the isomorphism between a vector space and a polynomial ring over complex numbers as follows:

σ_{c} : f (X) \in ℝ [X] ∕ (X^{n} + 1) \to (f (ω), f (ω^{3}), f (ω^{5}), \dots, f (ω^{2 n - 1})) \in {\hat{ℂ}}^{n}

, where

X \in ℂ

, and

ω = e^{𝑖𝜋 ∕ n}

, the root (i.e., the primitive

(μ = 2 n)

-th root) of the cyclotomic polynomial

X^{n} + 1

over complex numbers (Theorem A-8.2.1 in §A-8.2). We define

{\hat{ℂ}}^{n}

to be an

n

-dimensional special vector space whose second-half elements of each vector are reverse-ordered conjugates of the first-half elements (e.g.,

(v_{0}, v_{1}, \dots, v_{\frac{n}{2} - 1}, {\bar{v}}_{\frac{n}{2} - 1}, \dots, {\bar{v}}_{1}, {\bar{v}}_{0})

A-11.7.1 Isomorphism between

ℂ^{\frac{n}{2}}

and

{\hat{ℂ}}^{n}

In this section, we treat both

ℂ^{\frac{n}{2}}

and

{\hat{ℂ}}^{n}

as vector spaces of complex vectors, where the mapping between them is defined as

ϕ : ℂ^{\frac{n}{2}} \to {\hat{ℂ}}^{n}

as follows:

ϕ (z_{0}, z_{1}, \dots, z_{\frac{n}{2} - 1}) = (z_{0}, z_{1}, \dots, z_{\frac{n}{2} - 1}, \bar{z_{\frac{n}{2} - 1}}, \dots, \bar{z_{1}}, \bar{z_{0}})

In other words,

{\hat{ℂ}}^{n}

is a conjugate extension of

ℂ^{\frac{n}{2}}

such that the first-half elements of

{\hat{ℂ}}^{n}

are identical to those of

ℂ^{\frac{n}{2}}

, and the second-half elements of

{\hat{ℂ}}^{n}

are reverse-ordered conjugates of

ℂ^{\frac{n}{2}}

Now, we will demonstrate that the mapping

ϕ

between

ℂ^{\frac{n}{2}}

and

{\hat{ℂ}}^{n}

is an isomorphism.

Bijective: The mapping

ϕ

is trivially bijective. Every vector in

ℂ^{\frac{n}{2}}

uniquely maps to a vector in

{\hat{ℂ}}^{n}

by appending its reverse-ordered complex conjugates. Conversely, any vector in

{\hat{ℂ}}^{n}

can uniquely map back to

ℂ^{\frac{n}{2}}

by simply dropping the second half of its elements, establishing a perfect one-to-one correspondence.

Homomorphic: We will demonstrate that

ϕ

preserves homomorphism over addition

(+)

and element-wise vector multiplication

(⊙)

. Given two vectors

\vec{u}, \vec{v} \in ℂ^{\frac{n}{2}}

Therefore, the mapping

ϕ : ℂ^{\frac{n}{2}} \to {\hat{ℂ}}^{n}

is an isomorphism.

Vector Space of Complex Vectors with either Real or Complex Scalars

By mathematical definition, a vector space must satisfy closure under scalar multiplication: for any vector $\vec{v}$ in the space and any scalar $c$ from the scalar field, the product $c \cdot \vec{v}$ must also lie in the same vector space. Under this requirement, $ℂ^{\frac{n}{2}}$ is naturally a vector space of complex vectors with complex scalars (though the same is true with real scalars, since complex includes real). On the other hand, ${\hat{ℂ}}^{n}$ is a vector space of complex vectors strictly with real scalars.

To see why, recall that a vector $\vec{v} = (v_{0}, v_{1}, \dots, v_{n - 1}) \in {\hat{ℂ}}^{n}$ must satisfy the Hermitian-symmetry constraint: $v_{n - 1 - k} = \bar{v_{k}}$ for all $k$ . Consider an example with $n = 4$ :

\vec{v} = (1 + i, 2 + 2 i, 2 - 2 i, 1 - i) \in {\hat{ℂ}}^{4}

Now, let us multiply $\vec{v}$ by the complex scalar $c = i$ :

i \cdot \vec{v} = (- 1 + i, - 2 + 2 i, 2 + 2 i, 1 + i)

For this result to still lie in ${\hat{ℂ}}^{4}$ , the third entry must be the conjugate of the second entry. But $\bar{- 2 + 2 i} = - 2 - 2 i$ , which is not equal to $2 + 2 i$ . So $i \cdot \vec{v} \notin {\hat{ℂ}}^{4}$ , and closure fails.

More generally, for any $\vec{v} \in {\hat{ℂ}}^{n}$ and any scalar $c$ , the product $c \cdot \vec{v}$ preserves Hermitian symmetry if and only if $\bar{c} = c$ ; that is, if and only if $c$ is a real number. Therefore, ${\hat{ℂ}}^{n}$ is a valid vector space only when restricted to real scalars, and this is why ${\hat{ℂ}}^{n}$ is a vector space of complex vectors strictly with real scalars.

Throughout this book, we will regard both $ℂ^{\frac{n}{2}}$ and ${\hat{ℂ}}^{n}$ as vector spaces of complex vectors with real scalars.

Isomorphism of Vector Spaces: For a mapping between vector spaces to be an isomorphism, it has to be not only bijective and homomorphic over the $(+,⋅)$ operations, but also homomorphic over scalar multiplication. Therefore, we need to prove that $ϕ (c \cdot \vec{u}) = c \cdot ϕ (\vec{u})$ . This is always true in our case because the scalar $c$ is a real number, meaning it is unaffected by complex conjugation (i.e., $\bar{c} = c$ , and thus $\bar{c \cdot u_{k}} = c \cdot \bar{u_{k}}$ ).

Dimension of Vector Spaces: The dimension of a vector space is defined by how many scalars it takes to fully describe it. Therefore, the dimension of $ℂ^{\frac{n}{2}}$ is $n$ because it has $\frac{n}{2}$ elements where each element requires 2 scalars to describe (one real and one imaginary part). The dimension of ${\hat{ℂ}}^{n}$ is also $n$ because the first $\frac{n}{2}$ elements requires $\frac{n}{2} \cdot 2$ scalars to describe, and the latter $\frac{n}{2}$ elements are simply reverse-ordered conjugates of the former $\frac{n}{2}$ elements.

A-11.7.2 Isomorphism between

{\hat{ℂ}}^{n}

and

ℝ [X] ∕ (X^{n} + 1)

Now, we will demonstrate that

σ_{c}

is an isomorphism (i.e., bijective and homomorphic) between

{\hat{ℂ}}^{n}

and

ℝ [X] ∕ (X^{n} + 1)

by applying the same reasoning as described in the beginning of §A-11.6.

Bijective: Based on Euler’s formula

e^{𝑖𝜃} = \cos 𝜃 + i \cdot \sin 𝜃

(§A-12.3), we can derive the following arithmetic relations:

ω = \bar{ω^{2 n - 1}}, ω^{3} = \bar{ω^{2 n - 3}}, \dots, ω^{n - 1} = \bar{ω^{n + 1}}

. In other words, the one-half roots are conjugates of the other-half roots. This can also be pictorially understood based on a complex plane in Figure 5, where red arrows represent the roots of the 8th cyclotomic polynomial

X^{4} + 1

, comprising imaginary number and real number components. As shown in this figure, one half of the red arrows (i.e., roots) are a reflection of the other half on the

x

-axis (i.e., real number axis). This means that we can express these roots as an

n

-dimensional vector whose elements are the roots of

X^{n} + 1

, such that its second-half elements are a reverse-ordered conjugate of the first-half elements. Based on this vector design, the

σ_{c}

mapping can be re-written as follows:

σ_{c} (f (X)) = (f (ω), f (ω^{3}), f (ω^{5}), \dots, f (ω^{n - 1}), f (\bar{ω^{n - 1}}), f (\bar{ω^{n - 3}}), \dots, f (\bar{ω^{3}}), f (\bar{ω}))

Since

f (\bar{X}) = \bar{f (X)}

(because

f (X)

has strictly real coefficients), we can rewrite

σ_{c}

as:

σ_{c} (f (X)) = (f (ω), f (ω^{3}), f (ω^{5}), \dots, f (ω^{n - 3}), f (ω^{n - 1}), \bar{f (ω^{n - 1})}, \bar{f (ω^{n - 3})}, \dots, \bar{f (ω^{3})}, \bar{f (ω)})

This structure of vector exactly aligns with the definition of

{\hat{ℂ}}^{n}

: the second half of the elements of the

n

-dimensional vector

\vec{\hat{v}}

is a reverse-ordered conjugate of the first half.

For bijectiveness, we also need to demonstrate that every

f (X) \in ℝ [X] ∕ (X^{n} + 1)

is mapped to some

\vec{\hat{v}} \in {\hat{ℂ}}^{n}

, and no two different

f_{1} (X), f_{2} (X) \in ℝ [X] ∕ (X^{n} + 1)

map to the same

\vec{\hat{v}} \in {\hat{ℂ}}^{n}

. The first requirement is satisfied because each polynomial

f (X) \in ℝ [X] ∕ (X^{n} + 1)

can be evaluated at the

n

distinct roots of

X^{n} + 1

to a valid number. The second requirement is also satisfied because in the

(n - 1)

-degree polynomial ring, each list of

n

distinct

(x, y)

coordinates (where we fix the

X

values as the

n

distinct roots of

X^{n} + 1

{ω, ω^{3}, \dots, ω^{2 n - 1}}

) can be mapped only to a single polynomial within the

(n - 1)

-degree polynomial ring, as proved by Lagrange Polynomial Interpolation (Theorem A-10 in §A-10).

Homomorphic:

σ_{c}

is homomorphic, because based on the reasoning shown in §A-11.6, the relations

σ_{c} (f_{a} (X) + f_{b} (X)) = σ_{c} (f_{a} (X)) + σ_{c} (f_{b} (X))

and

σ_{c} (f_{a} (X) \cdot f_{b} (X)) = σ_{c} (f_{a} (X)) ⊙ σ_{c} (f_{b} (X))

mathematically hold regardless of whether the type of

X

is a modulo integer or a complex number. Additionally, for any real scalar

c \in ℝ

σ_{c} (c \cdot f (X)) = c \cdot σ_{c} (f (X))

holds because scaling the polynomial and then evaluating it is the same as evaluating it and then scaling the result.

Since

σ_{c}

is both bijective and homomorphic over the

(+,⋅)

operations, it is an isomorphism.

$⟨$ Theorem A-11.7 $⟩$ Isomorphism between Polynomials and Vectors over Complex Numbers

The following mapping $σ_{c}$ between polynomials and vectors over complex numbers is an isomorphism:

$σ_{c} : f (X) \in ℝ [X] ∕ (X^{n} + 1) \to (f (ω), f (ω^{3}), f (ω^{5}), \dots, f (ω^{2 n - 1})) \in {\hat{ℂ}}^{n} (≅ ℂ^{\frac{n}{2}})$

, where $ω = e^{𝑖𝜋 ∕ n}$ , the root (i.e., the primitive $(μ = 2 n)$ -th root) of the cyclotomic polynomial $X^{n} + 1$ over complex numbers, and ${\hat{ℂ}}^{n}$ is an $n$ -dimensional vector space of complex vectors (with real scalars) whose second-half elements are reverse-ordered conjugates of the first-half elements.

A-11.7 Isomorphism between Polynomials and Vectors over Complex Numbers

A-11.7.1 Isomorphism between ℂn 2 and ℂ^n

A-11.7.2 Isomorphism between ℂ^n and ℝ[X]∕(Xn + 1)

A-11.7.1 Isomorphism between $ℂ^{\frac{n}{2}}$ and ${\hat{ℂ}}^{n}$

A-11.7.2 Isomorphism between ${\hat{ℂ}}^{n}$ and $ℝ [X] ∕ (X^{n} + 1)$