Vandermonde Matrix with Roots of Cyclotomic Polynomial over Complex Numbers

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

n

distinct roots of the

μ

-th cyclotomic polynomial over complex numbers (where

μ

is a power of 2) as follows:

$⟨$ Theorem A-12.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 $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-12.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

𝛍

: The identity

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

relies only on

𝖮𝗋𝖽 (ω) = 2 n

(step 3), so it holds for any

μ = 2 n

(i.e., any even number). The nodes

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

are likewise the

n

roots of

X^{n} + 1

for any

n

, since

{(ω^{2 j - 1})}^{n} = ω^{2 𝑛𝑗} \cdot ω^{- n} = 1 \cdot (- 1) = - 1

Nevertheless, the reason we take

μ

to be a power of 2 does not come from this theorem, but from the FHE schemes themselves. In practice, CKKS, BFV, and BGV are most commonly instantiated over the power-of-2 cyclotomic ring

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

with

n

a power of 2, because this choice makes

X^{n} + 1 = Φ_{2 n} (X)

irreducible over rational numbers (which holds precisely when

n

is a power of 2), and also enables efficient negacyclic-NTT multiplication and a clean Ring-LWE security reduction. Once

n

(hence

μ = 2 n

) is fixed as a power of 2, the nodes are automatically the primitive

μ

-th roots of unity: by Theorem A-7.2.4 (§A-7.2),

ω^{k}

is a primitive

μ

-th root iff

\gcd (μ, k) = 1

, and every odd exponent

1, 3, \dots, 2 n - 1

is coprime to

μ = 2 n

iff

2 n

has no odd prime factor—i.e. iff

2 n

is a power of 2. So

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

being exactly the primitive

(μ = 2 n)

-th roots is a consequence of the power-of-2 ring choice. Meanwhile, as far as

μ

is an even number,

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

still holds.

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