Vandermonde Matrix with Roots of Cyclotomic Polynomial over Complex Numbers

In this subsection, we will build a Vandermonde matrix (§A-10.2) with the

n

distinct roots of the

μ

-th cyclotomic polynomial over complex numbers (where

μ

is a power of 2) as follows:

$⟨$ Theorem A-11.4 $⟩$ Vandermonde Matrix with the Roots of (power-of-2)-th Cyclotomic Polynomial over Complex Numbers

Suppose we have an $n \times n$ (where $n$ is a power of 2) Vandermonde matrix comprised of $n$ distinct roots of the $μ$ -th cyclotomic polynomial (explained in Theorem A-8.2.1 in §A-8.2), where $μ$ is a power of 2 and $n = \frac{μ}{2}$ . In other words, $V = 𝑉𝑎𝑛𝑑𝑒𝑟 (x_{0}, x_{1}, \dots, x_{n - 1})$ , where each $x_{j} = {(e^{𝑖𝜋 ∕ n})}^{2 j - 1}$ for $1 \leq j \leq n$ (i.e., the primitive $μ$ -th roots of unity). Then, the following holds:

$V \cdot V^{T} = [\begin{matrix} 0 & \dots & 0 & 0 & n \\ 0 & \dots & 0 & n & 0 \\ 0 & \dots & n & 0 & 0 \\ ⋮ & ... & ⋮ & ⋮ & ⋮ \\ n & 0 & 0 & \dots & 0 \end{matrix}] = n \cdot I_{n}^{R}$

And $V^{- 1} = \frac{V^{T} \cdot I_{n}^{R}}{n}$

Proof.

1.

Given

ω = e^{𝑖𝜋 ∕ n}

, each

x_{j} = {(ω)}^{2 j - 1}

. Thus, we can expand as follows:

$V \cdot V^{T} = [\begin{matrix} 1 & (ω) & {(ω)}^{2} & \dots & {(ω)}^{n - 1} \\ 1 & (ω^{3}) & {(ω^{3})}^{2} & \dots & {(ω^{3})}^{n - 1} \\ 1 & (ω^{5}) & {(ω^{5})}^{2} & \dots & {(ω^{5})}^{n - 1} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ 1 & (ω^{2 n - 1}) & {(ω^{2 n - 1})}^{2} & \dots & {(ω^{2 n - 1})}^{n - 1} \end{matrix}] \cdot [\begin{matrix} 1 & 1 & 1 & \dots & 1 \\ (ω) & (ω^{3}) & (ω^{5}) & \dots & (ω^{2 n - 1}) \\ {(ω)}^{2} & {(ω^{3})}^{2} & {(ω^{5})}^{2} & \dots & {(ω^{2 n - 1})}^{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ {(ω)}^{n - 1} & {(ω^{3})}^{n - 1} & {(ω^{5})}^{n - 1} & \dots & {(ω^{2 n - 1})}^{n - 1} \end{matrix}]$

$= [\begin{matrix} \sum_{k = 0}^{n - 1} ω^{2 k} & \sum_{k = 0}^{n - 1} ω^{4 k} & \sum_{k = 0}^{n - 1} ω^{6 k} & \dots & \sum_{k = 0}^{n - 1} ω^{2 𝑛𝑘} \\ \sum_{k = 0}^{n - 1} ω^{4 k} & \sum_{k = 0}^{n - 1} ω^{6 k} & \sum_{k = 0}^{n - 1} ω^{8 k} & \dots & \sum_{k = 0}^{n - 1} ω^{2 k (n + 1)} \\ \sum_{k = 0}^{n - 1} ω^{6 k} & \sum_{k = 0}^{n - 1} ω^{8 k} & \sum_{k = 0}^{n - 1} ω^{10 k} & \dots & \sum_{k = 0}^{n - 1} ω^{2 k (n + 2)} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ \\ \sum_{k = 0}^{n - 1} ω^{2 𝑛𝑘} & \sum_{k = 0}^{n - 1} ω^{2 (n + 1) k} & \sum_{k = 0}^{n - 1} ω^{2 (n + 2) k} & \dots & \sum_{k = 0}^{n - 1} ω^{2 (n + n - 1) k} \end{matrix}]$

2.

The

V \cdot V^{T}

matrix’s anti-diagonal elements are

\sum_{k = 0}^{n - 1} ω^{2 𝑛𝑘}

. We can derive the following:

$\sum_{k = 0}^{n - 1} ω^{2 𝑛𝑘} = \sum_{k = 0}^{n - 1} {(e^{𝑖𝜋 ∕ n})}^{2 𝑛𝑘} = \sum_{k = 0}^{n - 1} e^{2 𝜋𝑘𝑖} = \sum_{k = 0}^{n - 1} (\cos (2 𝜋𝑘) + i \sin (2 𝜋𝑘)) = \sum_{k = 0}^{n - 1} (1 + 0) = n$

This means that the The $V \cdot V^{T}$ matrix’s anti-diagonal elements are $n$ .

3.

Next, we will prove that the

V \cdot V^{T}

matrix has 0 for all positions except for the anti-diagonal ones. In other words, we will prove the following:

$\sum_{k = 0}^{n - 1} ω^{2 k} = \sum_{k = 0}^{n - 1} ω^{4 k} = \sum_{k = 0}^{n - 1} ω^{6 k} = \dots = \sum_{k = 0}^{n - 1} ω^{2 (n - 1) k} = \sum_{k = 0}^{n - 1} ω^{2 (n + 1) k} = \dots = \sum_{k = 0}^{n - 1} ω^{2 (2 n - 1) k} = 0$

For this proof, we will leverage the Geometric Sum formula $\sum_{i = 0}^{n - 1} x^{i} = \frac{x^{n} - 1}{x - 1}$ :

$⟨$ Theorem A-11.4.1 $⟩$ Geometric Sum Formula

Let the geometric sum $S_{n} = 1 + x + x^{2} + \dots + x^{n - 1}$

Then, $x \cdot S_{n} = x + x^{2} + x^{3} + \dots + x^{n}$

$x \cdot S_{n} - S_{n} = (x + x^{2} + x^{3} + \dots + x^{n}) - (1 + x + x^{2} + \dots + x^{n - 1}) = x^{n} - 1$

$S_{n} \cdot (x - 1) = x^{n} - 1$

$S_{n} = \frac{x^{n} - 1}{x - 1}$ # with the constraint that $x \neq 1$

Leveraging the Geometric Sum formula $\sum_{i = 0}^{n - 1} x^{i} = \frac{x^{n} - 1}{x - 1}$ ,

$\sum_{k = 0}^{n - 1} ω^{2 𝑚𝑘} = \frac{{(ω^{2 m})}^{n} - 1}{ω^{2 m} - 1} = \frac{{(ω^{2 n})}^{m} - 1}{ω^{2 m} - 1} = \frac{1 - 1}{ω^{2 m} - 1} = 0$ for $1 \leq m \leq (2 n - 1)$ # since $𝖮𝗋𝖽 (ω) = 2 n$

Therefore,

4.

Based on the proof of step 2 and 3,

V \cdot V^{T} = [\begin{matrix} 0 & \dots & 0 & 0 & n \\ 0 & \dots & 0 & n & 0 \\ 0 & \dots & n & 0 & 0 \\ ⋮ & ... & ⋮ & ⋮ & ⋮ \\ n & 0 & 0 & \dots & 0 \end{matrix}] = n \cdot I_{n}^{R}

5.

Given

V \cdot V^{T} = n \cdot I_{n}^{R}

$V^{- 1} \cdot V \cdot V^{T} = V^{- 1} \cdot n \cdot I_{n}^{R}$

$V^{T} = V^{- 1} \cdot n \cdot I_{n}^{R}$

$V^{T} \cdot I_{n}^{R} = V^{- 1} \cdot n \cdot I_{n}^{R} \cdot I_{n}^{R}$

$V^{T} \cdot I_{n}^{R} = V^{- 1} \cdot n$ # since $I_{n}^{R} \cdot I_{n}^{R} = I_{n}$

$V^{- 1} = \frac{V^{T} \cdot I_{n}^{R}}{n}$

□

Later in the CKKS scheme (§D-3), we will use

V^{- 1}

to encode a complex vector into a real number vector, and

V^{T}

to decode a real number vector into a complex vector (§D-3.2).

Condition for

𝛍

: It’s worthwhile to note that the property

V \cdot V^{T} = n \cdot I_{n}^{R}

does not hold if

μ

(denoting the

μ

-th cyclotomic polynomial) is not a power of 2. In particular, step 3 of the proof does not hold anymore if

μ

is not a power of 2:

\sum_{k = 0}^{n - 1} ω^{2 k} \neq \sum_{k = 0}^{n - 1} ω^{4 k} \neq \sum_{k = 0}^{n - 1} ω^{6 k} \neq \dots \neq \sum_{k = 0}^{n - 1} ω^{2 (n - 1) k} \neq \sum_{k = 0}^{n - 1} ω^{2 (n + 1) k} \neq \dots \neq \sum_{k = 0}^{n - 1} ω^{2 (2 n - 1) k} \neq 0

A-11.4 Vandermonde Matrix with Roots of Cyclotomic Polynomial over Complex Numbers