प्रतिलोम संख्या सैद्धांतिक रूपांतरण

Last updated on Apr 29, 2026

पिछले अध्यायों में, हमने Number Theoretic Transform (NTT) का अध्ययन किया, जो एक पॉलीनोमियल (polynomial) का उसके $k$ -th roots of unity पर मूल्यांकन (evaluate) करता है। इसे एक पॉलीनोमियल को उसके कोएफिशिएंट फॉर्म (coefficient form) से उसके पॉइंट-वैल्यू फॉर्म (point-value form) में बदलने के रूप में समझा जा सकता है।

NTT को एक डिग्री- $(k-1)$ पॉलीनोमियल के कोएफिशिएंट वेक्टर को Vandermonde मैट्रिक्स से गुणा करके किया जा सकता है, जिसकी टाइम कॉम्प्लेक्सिटी (time complexity) $\mathcal{O}(k^2)$ होती है। इस ट्रांसफॉर्मेशन के एक तेज़ और रिकर्सिव (recursive) वर्ज़न का उपयोग करना भी संभव और अधिक दिलचस्प है, जो टाइम कॉम्प्लेक्सिटी को $\mathcal{O}(k \log k)$ तक कम कर देता है।

इस अध्याय में, हम NTT के इन्वर्स ट्रांसफॉर्मेशन का अध्ययन शुरू करते हैं, जिसे Inverse Number Theoretic Transform, या INTT कहा जाता है। इसका उपयोग किसी पॉलीनोमियल को उसके पॉइंट-वैल्यू फॉर्म से वापस उसके कोएफिशिएंट फॉर्म में बदलने के लिए किया जा सकता है। इस प्रक्रिया को interpolation कहा जाता है।

Lagrange interpolation पर हमारे लेख में, हम पहले ही interpolation करने की एक विधि देख चुके हैं। Lagrange interpolation और Inverse Number Theoretic Transform के उपयोग के बीच दोहरे अंतर हैं: Lagrange interpolation किसी भी बिंदुओं के सेट (set of points) से किया जा सकता है, जबकि INTT केवल $k$ -th roots of unity के सेट पर ही किया जा सकता है। इसके विपरीत, Lagrange interpolation की टाइम कॉम्प्लेक्सिटी हमेशा $\mathcal{O}(k^2)$ होती है, जबकि INTT को $\mathcal{O}(k \log k)$ टाइम कॉम्प्लेक्सिटी में किया जा सकता है।

इस अध्याय में, हम:

याद करेंगे कि Vandermonde मैट्रिक्स का उपयोग करके इवैल्यूएशन (evaluation) कैसे किया जा सकता है;
एक इन्वर्स ट्रांसफॉर्मेशन प्रस्तावित करेंगे जो Vandermonde मैट्रिक्स का उपयोग करके ही किया जाता है;
दिखाएंगे कि यह इन्वर्स ट्रांसफॉर्मेशन मूल ट्रांसफॉर्मेशन को पूर्ववत (undo) कर देता है। दूसरे शब्दों में, हम दिखाएंगे कि NTT के माध्यम से इवैल्यूएशन, और उसके बाद INTT के माध्यम से interpolation, पॉलीनोमियल को उसके मूल कोएफिशिएंट फॉर्म में वापस ला देता है।

अभी के लिए, हम डिग्री $3$ के पॉलीनोमियल के लिए INTT के साथ काम करेंगे ताकि पाठक गणनाओं (calculations) को अधिक आसानी से समझ सकें।

अगले अध्याय में, हम यह साबित करेंगे कि प्रस्तावित इन्वर्स ट्रांसफॉर्मेशन किसी भी डिग्री के पॉलीनोमियल पर लागू होता है।

रीकैप: कोएफिशिएंट फॉर्म से पॉइंट फॉर्म तक

मान लीजिए कि एक पॉलीनोमियल है

f(x)=a_0+a_1x+a_2x^2+a_3x^3

इस पॉलीनोमियल को कोएफिशिएंट फॉर्म से पॉइंट-वैल्यू फॉर्म में बदलने के लिए, इसे कम से कम $4$ बिंदुओं पर इवैल्यूएट करना आवश्यक है।

उदाहरण के लिए, यदि सेट $S=\{1,\omega, \omega^2, \omega^3\}$ इवैल्यूएशन पॉइंट्स को दर्शाता है, जहाँ $\omega$ एक primitive $4$ th root of unity है, तो इन बिंदुओं पर इवैल्यूएशन इस प्रकार दिए जाते हैं:

\begin{aligned} f(1) &= a_0 &+& a_1 &+& a_2 &+& a_3 \\ f(\omega) &= a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\ f(\omega^2) &= a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\ f(\omega^3) &= a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9 \end{aligned}

इसे निम्नलिखित मैट्रिक्स गुणा (matrix multiplication) द्वारा व्यक्त किया जा सकता है:

\begin{aligned}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}&=\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega & \omega^2 & \omega^3 \\1 & \omega^2 & \omega^4 & \omega^6 \\1 & \omega^3 & \omega^6 & \omega^9\end{bmatrix}\begin{bmatrix}a_0 \\a_1 \\a_2 \\a_3\end{bmatrix} \\ \mathbf{y} &=V(\omega) \cdot \ \mathbf{a} \\ \end{aligned}

जहाँ $V(\omega)$ को Vandermonde मैट्रिक्स कहा जाता है, और $\mathbf{a}$ कोएफिशिएंट्स को दर्शाने वाला कॉलम वेक्टर (column vector) है। आप इनके बारे में विस्तार से जानने के लिए Vandermonde Matrices पर हमारा लेख देख सकते हैं। एक Vandermonde matrix की यह विशेषता होती है कि इसकी प्रत्येक पंक्ति (row) एक geometric progression (गुणोत्तर श्रेणी) बनाती है, जो संख्याओं का एक क्रम है जिसमें प्रत्येक पद पिछले पद को एक निरंतर अनुपात (constant ratio) से गुणा करके प्राप्त किया जाता है।

ऊपर दिए गए मैट्रिक्स $V(\omega)$ में, हम देख सकते हैं कि:

पहली पंक्ति: $[1 \ \ 1\ \ 1\ \ 1]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $1$
दूसरी पंक्ति: $[1 \ \omega\ \omega^2\ \omega^3]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $\omega$
तीसरी पंक्ति: $[1 \ \omega^2\ \omega^4\ \omega^6]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $\omega^2$
चौथी पंक्ति: $[1 \ \omega^3\ \omega^6\ \omega^9]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $\omega^3$

आइए याद करें कि गुणा $\mathbf{y} =V(\omega) \cdot \ \mathbf{a}$ , $f(x)$ के इवैल्यूएशन कैसे देता है:

\mathbf{y}=\begin{bmatrix}f(1)\\[4pt]f(\omega)\\[4pt]f(\omega^2)\\[4pt]f(\omega^3)\end{bmatrix}=\begin{bmatrix}1 & 1 & 1 & 1\\[4pt]1 & \omega & \omega^2 & \omega^3\\[4pt]1 & \omega^2 & \omega^4 & \omega^6\\[4pt]1 & \omega^3 & \omega^6 & \omega^9\end{bmatrix}\begin{bmatrix} a_0\\ a_1\\ a_2\\ a_3 \end{bmatrix}

यदि हम $V(\omega)$ का मैट्रिक्स गुणा पंक्ति-वार (row-wise) तरीके से करते हैं, तो हमें प्राप्त होता है:

\begin{aligned}f(1) = [1\ 1\ 1\ 1]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1\cdot a_0 + 1 \cdot a_1 + 1\cdot a_2 + 1\cdot a_3\\ &= a_0 + a_1 + a_2 + a_3\\[6pt]f(\omega) = [1\ \omega\ \omega^2\ \omega^3]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1 \cdot a_0 + \omega \cdot a_1 + \omega^2 \cdot a_2 + \omega^3 \cdot a_3 \\ &= a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3\\[6pt]f(\omega^2) = [1\ \omega^2\ \omega^4\ \omega^6]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1 \cdot a_0 + \omega^2 \cdot a_1 + \omega^4 \cdot a_2 + \omega^6 \cdot a_3\\ &= a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6 \\[6pt]f(\omega^3) = [1\ \omega^3\ \omega^6\ \omega^9]\cdot\begin{bmatrix}a_0\\ a_1\\ a_2\\ a_3\end{bmatrix} &= 1 \cdot a_0 + \omega^3 \cdot a_1 + \omega^6 \cdot a_2 + \omega^9 \cdot a_3 \\ &= a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9 \end{aligned}

इसलिए, हमें प्राप्त होता है:

\begin{aligned}\mathbf{y}=\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}&=\begin{bmatrix}a_0 &+& a_1 &+& a_2 &+& a_3\\a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9\end{bmatrix} \end{aligned}

इस प्रकार, यदि हमें किसी पॉलीनोमियल का कोएफिशिएंट फॉर्म दिया गया है, जिसे वेक्टर $\mathbf{a}$ द्वारा दर्शाया गया है, तो हम $\mathbf{a}$ को Vandermonde मैट्रिक्स $V(\omega)$ से बाईं ओर गुणा (left-multiplying) करके इसका पॉइंट-वैल्यू फॉर्म प्राप्त कर सकते हैं, जिसे वेक्टर $\mathbf{y}$ द्वारा दर्शाया गया है।

लेकिन क्या होगा यदि हमें इसके बजाय इवैल्यूएशन दिए गए हों, यानी वेक्टर $\mathbf{y}$ , और कोएफिशिएंट्स की गणना करने के लिए कहा जाए, यानी वेक्टर $\mathbf{a}$ ?

यह Vandermonde मैट्रिक्स $V(\omega)$ के इन्वर्स (inverse) का उपयोग करके किया जा सकता है, जिसे $V^{-1}(\omega)$ द्वारा दर्शाया जाता है, निम्नलिखित ऑपरेशन के माध्यम से:

\mathbf{a} = V(\omega)^{-1}\cdot \mathbf{y}

हमारा दावा है कि मैट्रिक्स $V(\omega)^{-1}$ इस प्रकार दिया जाता है

V(\omega)^{-1} =\frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}

ध्यान दें कि $V(\omega)^{-1}$ में भी यह विशेषता है कि इसकी प्रत्येक पंक्ति एक geometric progression बनाती है:

पहली पंक्ति: $[1 \ \ 1\ \ 1\ \ 1]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $1$
दूसरी पंक्ति: $[1 \ \omega^{-1}\ \omega^{-2}\ \omega^{-3}]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $\omega^{-1}$
तीसरी पंक्ति: $[1 \ \omega^{-2}\ \omega^{-4}\ \omega^{-6}]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $\omega^{-2}$
चौथी पंक्ति: $[1 \ \omega^{-3}\ \omega^{-6}\ \omega^{-9}]$ $\rightarrow$ पहला पद: $1$ , सार्व अनुपात: $\omega^{-3}$

इसलिए, इस मामले में Vandermonde मैट्रिक्स का इन्वर्स स्वयं एक और Vandermonde मैट्रिक्स है।

निम्नलिखित अनुभागों में, हम $4$ -th roots of unity का उपयोग करके दिखाएंगे कि इस उदाहरण में हमारा दावा सत्य है। अगले अध्याय में, हम इसे सामान्य रूप से सिद्ध करेंगे।

हम सिद्ध करेंगे कि, $k$ -th roots of unity के मामले में, जब NTT को निम्नलिखित Vandermonde मैट्रिक्स का उपयोग करके प्राप्त किया जाता है,

V(\omega)=\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega & \omega^{2} & \cdots & \omega^{k-1} \\1 & \omega^{2} & \omega^{4} & \cdots & \omega^{2(k-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{k-1} & \omega^{2(k-1)} & \cdots & \omega^{(k-1)(k-1)}\end{bmatrix},

तो इन्वर्स मैट्रिक्स $V(\omega)^{-1}$ को $\omega$ की प्रत्येक पावर (power) को $\frac{1}{\omega}$ से बदलकर और $k$ के फैक्टर से विभाजित करके प्राप्त किया जा सकता है, जो इस प्रकार है

V(\omega)^{-1}=\frac{1}{k}\begin{bmatrix}1 & 1 & 1 & \cdots & 1 \\1 & \omega^{-1} & \omega^{-2} & \cdots & \omega^{-(k-1)} \\1 & \omega^{-2} & \omega^{-4} & \cdots & \omega^{-2(k-1)} \\\vdots & \vdots & \vdots & \ddots & \vdots \\1 & \omega^{-(k-1)} & \omega^{-2(k-1)} & \cdots & \omega^{-(k-1)(k-1)}\end{bmatrix}.

इन्वर्स Vandermonde मैट्रिक्स को जब किसी दिए गए पॉलीनोमियल के roots of unity पर इवैल्यूएशन के वेक्टर से गुणा किया जाता है, तो यह उस पॉलीनोमियल का कोएफिशिएंट वेक्टर लौटाता है।

$V(\omega)^{-1} \cdot \mathbf{y}$ का इवैल्यूएशन

यह प्रदर्शित करने के लिए कि $V(\omega)^{-1}$ और $\mathbf{y}$ के बीच मैट्रिक्स गुणा हमें वापस कोएफिशिएंट वेक्टर $\mathbf{a}$ देता है, आइए अपने पहले के उदाहरण का उपयोग करें, जहाँ $f(x)=a_0+a_1x+a_2x^2+a_3x^3$ , $S=\{1,\omega,\omega^2,\omega^3\}$ और $k=4$ है।

याद करें कि $\mathbf{y}$ , जो $S$ के बिंदुओं पर $f(x)$ के इवैल्यूएशन का वेक्टर है, इस प्रकार दिया गया है:

\begin{aligned}\mathbf{y}=\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix}&=\begin{bmatrix}a_0 &+& a_1 &+& a_2 &+& a_3\\a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9\end{bmatrix} \end{aligned}

आइए $V(\omega)^{-1}$ और $\mathbf{y}$ के बीच मैट्रिक्स गुणा करें:

\begin{aligned} \tilde{\mathbf{a}} &= V(\omega)^{-1}\cdot \mathbf{y} \\ \begin{bmatrix}\tilde{a_0} \\\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix}&= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}f(1) \\f(\omega) \\f(\omega^2) \\f(\omega^3)\end{bmatrix} \end{aligned}

हमारा उद्देश्य यह दिखाना है कि उपरोक्त मैट्रिक्स गुणा से प्राप्त वेक्टर $\tilde{\mathbf{a}}$ , $f(x)$ के कोएफिशिएंट वेक्टर $\mathbf{a}$ के बराबर है।

वेक्टर $\mathbf{y}$ से इवैल्यूएशन $f(1),f(\omega),f(\omega^2)$ और $f(\omega^3)$ को प्रतिस्थापित (substitute) करके, हम कोएफिशिएंट्स $\tilde{\mathbf{a}}$ की गणना इस प्रकार कर सकते हैं:

\begin{aligned} \tilde{\mathbf{a}} &= V(\omega)^{-1}\cdot \mathbf{y} \\ \begin{bmatrix}\tilde{a_0} \\\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix} &= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}a_0 &+& a_1 &+& a_2 &+& a_3\\a_0 &+& a_1\omega &+& a_2\omega^2 &+& a_3\omega^3 \\a_0 &+& a_1\omega^2 &+& a_2\omega^4 &+& a_3\omega^6 \\a_0 &+& a_1\omega^3 &+& a_2\omega^6 &+& a_3\omega^9\end{bmatrix} \end{aligned}

अब हम दिखाते हैं कि वेक्टर $\tilde{\mathbf{a}}$ और ${\mathbf{a}}$ बराबर हैं। दूसरे शब्दों में, हम यह दिखाना चाहते हैं कि

\begin{aligned} \tilde{a_0} &= a_0, \\ \tilde{a_1} &= a_1, \\ \tilde{a_2} &= a_2, \\ \tilde{a_3} &= a_3. \\ \end{aligned}

कोएफिशिएंट्स $\tilde{a_0},\tilde{a_1},\tilde{a_2}$ और $\tilde{a_3}$ की गणना

आइए दाईं ओर (RHS) पंक्ति-दर-पंक्ति मैट्रिक्स गुणा करें ताकि यह देखा जा सके कि बाईं ओर (LHS) संबंधित कोएफिशिएंट्स कैसे प्राप्त होते हैं। कोएफिशिएंट $\tilde{a_0}$ के लिए, हम $V(\omega)^{-1}$ की पहली पंक्ति का वेक्टर $\mathbf{y}$ के साथ डॉट प्रोडक्ट (dot product) लेते हैं:

\begin{aligned} \begin{bmatrix}\color{red}\tilde{a_0} \\\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix} &= \frac{1}{4}\begin{bmatrix}\color{red}1 & \color{red}1 & \color{red}1 & \color{red}1 \\1 & \omega^{-1} & \omega^{-2} & \omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}\color{red}f(1) \\ \color{red}f(\omega) \\\color{red}f(\omega^2) \\\color{red}f(\omega^3)\end{bmatrix} \\ \end{aligned}

\begin{aligned} &\quad \quad\text{ \ \ } V(\omega)^{-1} \text{ की पहली पंक्ति का } \mathbf{y} \text{ के साथ डॉट प्रोडक्ट}\\ \tilde{a_0}&= \frac{1}{4}\big(1\cdot f(1)+1\cdot f(\omega)+1\cdot f(\omega^2)+1\cdot f(\omega^3)\big) \\[6pt] &=\frac{1}{4}\Big(1\cdot \underbrace{(a_0+a_1+a_2+a_3)}_{f(1)} \\ &\qquad\; + 1\cdot \underbrace{(a_0+a_1\omega+a_2\omega^2+a_3\omega^3)}_{f(\omega)}\\ &\qquad\; + 1\cdot \underbrace{(a_0+a_1\omega^2+a_2\omega^4+a_3\omega^6)}_{f(\omega^2)}\\ &\qquad\; + 1\cdot \underbrace{(a_0+a_1\omega^3+a_2\omega^6+a_3\omega^9)}_{f(\omega^3)}\Big)\\[6pt] &=\frac{1}{4}\Big(4a_0 \;+\; a_1(1+\omega+\omega^2+\omega^3) \\ &\qquad\; +\; a_2(1+\omega^2+\omega^4+\omega^6) \\ &\qquad\; +\; a_3(1+\omega^3+\omega^6+\omega^9)\Big) \end{aligned}

पिछले अध्याय से याद करें कि, चूंकि $\omega$ एक primitive $4$ -th root of unity है, इसलिए योग (sum)

\sum_{k=0}^3 \omega^{mk}

शून्य के बराबर होता है जब भी $m$ , $4$ का गुणज (multiple) नहीं होता है। स्पष्ट रूप से,

\sum_{k=0}^3 \omega^{mk} = \omega^{m\cdot 0} + \omega^{m\cdot 1} + \omega^{m\cdot 2} + \omega^{m\cdot 3} \\= 1 + \omega^m + \omega^{2m} + \omega^{3m}=0\\

इस कॉन्सेप्ट को विस्तार से समझने के लिए, कृपया Orthogonality of Roots of Unity पर लेख देखें।
$m$ के उन मानों को प्रतिस्थापित करने पर जो $4$ के गुणज नहीं हैं, हमें निम्नलिखित सर्वसमिकाएँ (identities) प्राप्त होती हैं:

\begin{aligned} \text{for } m&=1 &\rightarrow& 1+\omega+\omega^2+\omega^3=0, \quad \\\text{for }m&=2&\rightarrow&1+\omega^2+\omega^4+\omega^6=0 , \quad \\\text{for }m&=3&\rightarrow&1+\omega^3+\omega^6+\omega^9=0, \quad \\ \text{for }m&=-1&\rightarrow&1+\omega^{-1}+\omega^{-2}+\omega^{-3}=0, \quad \\\text{for }m&=-2&\rightarrow&1+\omega^{-2}+\omega^{-4}+\omega^{-6}=0, \quad \\\text{for }m&=-3&\rightarrow&1+\omega^{-3}+\omega^{-6}+\omega^{-9}=0, \quad \end{aligned}

इसलिए, $a_1$ , $a_2$ , और $a_3$ से गुणा होने वाले सभी पद शून्य (vanish) हो जाते हैं, और बचता है:

\begin{aligned} \tilde{a_0}&=\frac{1}{4}\Big(4a_0 \;&+&\; a_1\underbrace{(1+\omega+\omega^2+\omega^3)}_{=\,0} \\ &\qquad\; &+&\; a_2\underbrace{(1+\omega^2+\omega^4+\omega^6)}_{=\,0} \\ &\qquad\; &+&\; a_3\underbrace{(1+\omega^3+\omega^6+\omega^9)}_{=\,0}\Big) \\ \tilde{a_0}&=\frac{1}{4}\cdot 4a_0 \\ &= a_0\\ \end{aligned}

इसी तरह, $\tilde{a_1}$ की गणना करने के लिए, हम $V(\omega)^{-1}$ की दूसरी पंक्ति का $\mathbf{y}$ के साथ डॉट प्रोडक्ट लेते हैं:

\begin{aligned} \begin{bmatrix}\tilde{a_0} \\\color{red}\tilde{a_1} \\\tilde{a_2} \\\tilde{a_3}\end{bmatrix} &= \frac{1}{4}\begin{bmatrix}1 & 1 & 1 & 1 \\\color{red}1 & \color{red}\omega^{-1} & \color{red}\omega^{-2} & \color{red}\omega^{-3} \\1 & \omega^{-2} & \omega^{-4} & \omega^{-6} \\1 & \omega^{-3} & \omega^{-6} & \omega^{-9}\end{bmatrix}\begin{bmatrix}\color{red}f(1) \\ \color{red}f(\omega) \\\color{red}f(\omega^2) \\\color{red}f(\omega^3)\end{bmatrix} \\ \end{aligned}

\begin{aligned} &\qquad V(\omega)^{-1} \text{ की दूसरी पंक्ति का } \mathbf{y} \text{ के साथ डॉट प्रोडक्ट} \\ \tilde{a_1} &= \frac{1}{4}\big(1\cdot f(1) + \omega^{-1}f(\omega) + \omega^{-2}f(\omega^2) + \omega^{-3}f(\omega^3)\big) \\[6pt] \end{aligned}

इवैल्यूएशन $f(1), f(\omega), f(\omega^2)$ और $f(\omega^3)$ के व्यंजकों (expressions) को प्रतिस्थापित करने पर, हमें प्राप्त होता है:

\begin{aligned} \tilde{a_1} &= \frac{1}{4}\Big( 1(a_0+a_1+a_2+a_3) \\ &\qquad + \omega^{-1}(a_0 + a_1\omega + a_2\omega^2 + a_3\omega^3) \\ &\qquad + \omega^{-2}(a_0 + a_1\omega^2 + a_2\omega^4 + a_3\omega^6) \\ &\qquad + \omega^{-3}(a_0 + a_1\omega^3 + a_2\omega^6 + a_3\omega^9) \Big) \\[6pt] \end{aligned}

$a_0,a_1,a_2$ और $a_3$ के फैक्टर्स (factors) प्राप्त करने के लिए पदों को समूहित (grouping) करने पर मिलता है:

\begin{aligned} \tilde{a_1} &= \frac{1}{4}\Big( a_0(1+\omega^{-1}+\omega^{-2}+\omega^{-3}) \\ &\qquad + a_1(1+\omega^{-1}\omega+\omega^{-2}\omega^2+\omega^{-3}\omega^3) \\ &\qquad + a_2(1+\omega^{-1}\omega^2+\omega^{-2}\omega^4+\omega^{-3}\omega^6) \\ &\qquad + a_3(1+\omega^{-1}\omega^3+\omega^{-2}\omega^6+\omega^{-3}\omega^9) \Big) \\[6pt] &= \frac{1}{4}\Big( a_0(1+\omega^{-1}+\omega^{-2}+\omega^{-3}) + 4a_1 \\ &\qquad + a_2(1+\omega^{1}+\omega^{2}+\omega^{3}) \\ &\qquad + a_3(1+\omega^{2}+\omega^{4}+\omega^{6}) \Big) \end{aligned}

फिर से, $a_0,a_2,a_3$ के फैक्टर्स से जुड़े कोष्ठक (parentheses) के भीतर के पद शून्य हो जाते हैं, जिससे बचता है:

\begin{aligned} \tilde{a_1}&=\frac{1}{4}\cdot 4a_1 = a_1\\ \end{aligned}

अपने आप $\tilde{a_2}$ और $\tilde{a_3}$ के लिए गुणा का विस्तार (expand) करने का प्रयास करें और देखें कि वे उसी तर्क के अनुसार कैसे सरल होते हैं जिसका हमने ऊपर उपयोग किया है। आप पाएंगे कि $\tilde{a_2}=a_2$ और $\tilde{a_3} = a_3$ है, जैसा कि अपेक्षित था।

यह इस प्रदर्शन को पूरा करता है कि $V(\omega)^{-1} \cdot \mathbf{y} = \mathbf{a}$ है। इसके साथ, हमने दिखाया है कि $k=4$ के मामले में Vandermonde मैट्रिक्स का इन्वर्स भी एक Vandermonde मैट्रिक्स होता है। $k$ के सामान्य मान (general value) के लिए मामला अगले अध्याय में सिद्ध किया जाएगा।

यह लेख हमारी ZK Book में Number Theoretic Transform पर आधारित एक श्रृंखला का हिस्सा है।