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 by the Geometric Sum formula (Theorem A-12.4.1). As shown in the proof step 3 of Theorem A-12.4, each element is of the form ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{k=0}^{n-1}{({\omega }^{2m})}^k$ for some integer $m$ (where $2m$ is not a multiple of $2n$). Let $r={\omega }^{2m}$. Then:

$\underset{k=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{r}^k={\displaystyle \frac{r^n-1}{r-1}}={\displaystyle \frac{{({\omega }^{2m})}^n-1}{{\omega }^{2m}-1}}={\displaystyle \frac{{({\omega }^n)}^{2m}-1}{{\omega }^{2m}-1}}$

$$

Since $\omega$ is a root of $X^n+1$, we know ${\omega }^n\equiv -1modp$. Thus:

${\displaystyle \frac{{(-1)}^{2m}-1}{{\omega }^{2m}-1}}={\displaystyle \frac{1-1}{{\omega }^{2m}-1}}=0$

$$

Therefore, the sum is 0 for all off-anti-diagonal positions.

$$

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.4). This means that the formula $V^{-1}={\displaystyle \frac{V^T\cdot I_n^R}{n}}$ in Theorem A-12.4 (in §A-12.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$

□