Proof. $$

1.

$V\cdot V^T$ is expanded as follows:

$V\cdot V^T=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill (\omega )\hfill & \hfill {(\omega )}^2\hfill & \hfill \cdots \hfill & \hfill {(\omega )}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^3)\hfill & \hfill {({\omega }^3)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^3)}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^5)\hfill & \hfill {({\omega }^5)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^5)}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{2n-1})\hfill & \hfill {({\omega }^{2n-1})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^{n-1}\hfill \end{array}\right]\cdot \left[\begin{array}{ccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill \\ \hfill (\omega )\hfill & \hfill ({\omega }^3)\hfill & \hfill ({\omega }^5)\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{2n-1})\hfill \\ \hfill {(\omega )}^2\hfill & \hfill {({\omega }^3)}^2\hfill & \hfill {({\omega }^5)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {(\omega )}^{n-1}\hfill & \hfill {({\omega }^3)}^{n-1}\hfill & \hfill {({\omega }^5)}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^{n-1}\hfill \end{array}\right]$

$$

$=\left[\begin{array}{ccccc}\hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2k}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{4k}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{6k}\hfill & \hfill \cdots \hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2\mathit{𝑛𝑘}}\hfill \\ \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{4k}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{6k}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{8k}\hfill & \hfill \cdots \hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2k(n+1)}\hfill \\ \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{6k}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{8k}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{10k}\hfill & \hfill \cdots \hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2k(n+2)}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2\mathit{𝑛𝑘}}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2(n+1)k}\hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2(n+2)k}\hfill & \hfill \cdots \hfill & \hfill \underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2(n+n-1)k}\hfill \end{array}\right]$

$$

, where $\omega$ (i.e., the primitive $(\mu =2n)$-th root of unity) has the order $2n$.

$$

2.

Note that the $V\cdot V^T$ matrix’s anti-diagonal elements are $\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2\mathit{𝑛𝑘}}$. It can be seen that ${\omega }^{2n}\equiv 1modp$, because ${\mathsf{\text{𝖮𝗋𝖽}}}_p(\omega )=2n$. Thus, the $V\cdot V^T$ matrix’s every anti-diagonal element is $\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}1=n$.

$$

3.

Next, we will prove that the $V\cdot V^T$ matrix has $0$ for all other positions than the anti-diagonal ones. In other words, we will prove the following:

$\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2k}=\sum _{k=0}^{n-1}{\omega }^{4k}=\sum _{k=0}^{n-1}{\omega }^{6k}=\cdots =\sum _{k=0}^{n-1}{\omega }^{2(n-1)k}=\sum _{k=0}^{n-1}{\omega }^{2(n+1)k}=\cdots =\sum _{k=0}^{n-1}{\omega }^{2(2n-1)k}=0$

$$

The above is true, because in the particular case of the $(\mu =2n)$-th cyclotomic polynomial $X^n+1$ (where $n$ is a power of 2), ${\omega }^i+{\omega }^{i+\frac{n}{2}}\equiv 0modp$ for each integer $i$ where $0\le i\le n-1$. Therefore, in the element $\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2k}$, its one-half terms add with its other-half terms and their final summation becomes $0$. This is the same for all other following elements:

$\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{4k},\sum _{k=0}^{n-1}{\omega }^{6k},\cdots ,\sum _{k=0}^{n-1}{\omega }^{2(n-1)k},\sum _{k=0}^{n-1}{\omega }^{2(n+1)k},\cdots ,\sum _{k=0}^{n-1}{\omega }^{2(2n-1)k}$

$$

4.

According to step 1 and 2, the $V\cdot V^T$ matrix has $n$ on its anti-diagonal positions and $0$ for all other positions.

5.

Now we will derive the formula for $V^{-1}$. 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$

$$

Now, there is one caveat: modulo operation does not support direct number division (as explained in §A-1.2.2). This means that the formula $V^{-1}={\displaystyle \frac{V^T\cdot I_n^R}{n}}$ in Theorem A-11.4 (in §A-11.4) is inapplicable in our case, because our modulo $p$ arithmetic does not allow direct division of $V^T\cdot I_n^R$ by $n$. Therefore, we instead multiply $V^T\cdot I_n^R$ by the inverse of $n$ (i.e., $n^{-1}$). We continue as follows:

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

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

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

□