प्रमाण कि एक Vandermonde Matrix का व्युत्क्रम एक अन्य Vandermonde Matrix होता है

Last updated on May 2, 2026

Inverse Number Theoretic Transform पर पिछले अध्याय में, हमने दावा किया था कि unity के primitive $k$ -th root $\omega$ के लिए Vandermonde matrix $V(\omega)$ का inverse भी एक Vandermonde matrix होता है, जिसे $\frac{1}{k}V(\omega^{-1})$ द्वारा दिया जाता है। अब हम इस तथ्य को सिद्ध करेंगे।

गणित में कम रुचि रखने वाले पाठक बिना किसी नुकसान के इस अध्याय को छोड़ सकते हैं। INTT को समझने के लिए यह आवश्यक नहीं है, बशर्ते वे यह स्वीकार करें कि हमारा प्रस्तावित inverse matrix मान्य है।

Vandermonde matrix को एक ऐसे matrix के रूप में परिभाषित किया जाता है जहां प्रत्येक पंक्ति (row) एक geometric progression (गुणोत्तर श्रेणी) होती है।

पहली पंक्ति $\omega^0$ का geometric progression है, जो $(\omega^0)^0$ से $(\omega)^{k-1}$ तक होता है।
दूसरी पंक्ति $\omega^1$ का geometric progression है, जो $(\omega^1)^{0}$ से $(\omega^1)^{k -1}$ तक होता है।
यह अंतिम पंक्ति तक जारी रहता है, जो $\omega^{k-1}$ का geometric progression है, जो $(\omega^{k-1})^0$ से $(\omega^{k-1})^{k-1}$ तक होता है।

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

इस प्रकार, $V(\omega)$ की पंक्ति $i$ और स्तंभ (column) $j$ में प्रत्येक प्रविष्टि (entry) निम्न द्वारा दी जाती है:

(\omega^i)^j

अधिकतम $k-1$ डिग्री वाले एक polynomial $f(x)$ पर विचार करें, जिसे निम्न प्रकार दिया गया है:

f(x)=a_0+a_1x+a_2x^2+\cdots+ a_{k-1}x^{k-1}

मान लें कि $S$ एक ऐसा सेट है जिसमें एक primitive $k$ -th root द्वारा उत्पन्न unity के $k$ -th roots शामिल हैं:

S=\{\omega^0, \omega^1, \omega^2, \cdots \omega^{k-1}\}

सेट $S$ पर $f(x)$ के मूल्यांकन (evaluations) का vector,

\mathbf{y} = \begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ f(\omega^2) \\ \vdots \\ f(\omega^{k-1}) \end{bmatrix}

coefficient vector $\mathbf{a}$ को $V(\omega)$ से गुणा करके प्राप्त किया जा सकता है:

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

\begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ f(\omega^2) \\ \vdots \\ f(\omega^{k-1}) \end{bmatrix} = \begin{bmatrix}(\omega^0)^0 & (\omega^0)^1 & (\omega^0)^2 & \cdots & (\omega^0)^{k-1} \\(\omega^1)^0 & (\omega^1)^1 & (\omega^1)^{2} & \cdots & (\omega^1)^{k-1} \\ (\omega^2)^0 & (\omega^{2})^1 & (\omega^2)^2 & \cdots & (\omega^2)^{k-1} \\\vdots & \vdots & \vdots & \ddots & \vdots \\ (\omega^{k-1})^0 & (\omega^{k-1})^1 & (\omega^{k-1})^2 & \cdots & (\omega^{k-1})^{k-1} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{k-1} \end{bmatrix}

जहां $a_0, a_1, ..., a_{k-1}$ polynomial $f(x)$ के coefficients हैं।

बाईं ओर की प्रत्येक पंक्ति Vandermonde matrix की $i$ -th पंक्ति और vector $\mathbf{a}$ का inner product है। उदाहरण के लिए, $i$ -th तत्व $f(\omega^i)$ है:

\begin{aligned} f(\omega^i) &= \langle [(\omega^i)^0,(\omega^i)^1, \ldots, (\omega^i)^{k-1}],\mathbf{a} \rangle \\ &= (\omega^i)^0 a_0 + (\omega^i)^1a_1 + \ldots + (\omega^i)^{k-1} a_{k-1} \\ &= \omega^{i0} a_0 \phantom{()} + \omega^{i1}a_1 \phantom{()} + \ldots + \omega^{i(k-1)} a_{k-1} \end{aligned}

इस प्रकार, evaluations को इस रूप में लिखा जा सकता है:

f(\omega^i) = \sum_{j=0}^{k-1} \omega^{ij} a_j

$i\in \{0,1,2,...,k-1\}$ के लिए।

Indices पर ध्यान दें: उपरोक्त समीकरण में, हमारे पास दो indices हैं। Index $i$ यह दर्शाता है कि हम किस evaluation के साथ काम कर रहे हैं, और यह $0,1,2,\ldots, k-1$ मान ले सकता है। इसका मतलब है कि उपरोक्त सूत्र केवल एक समीकरण का प्रतिनिधित्व नहीं करता है, बल्कि $k$ समीकरणों का प्रतिनिधित्व करता है, जो $i$ के प्रत्येक मान के लिए एक है। उदाहरण के लिए, उपरोक्त अंकन (notation) निम्न का एक संक्षिप्त रूप (shorthand) है:

\begin{aligned} f(\omega^0) &= \sum_{j=0}^{k-1} \omega^{0j} a_j \\ f(\omega^1) &= \sum_{j=0}^{k-1} \omega^{1j} a_j \\ \vdots \\ f(\omega^{k-1}) &= \sum_{j=0}^{k-1} \omega^{(k-1)j} a_j \\ \end{aligned}

$\omega^{ij}$ और $a_j$ में index $j$ एक summation index है और इसलिए योग (sum) द्वारा “consumed” (उपभोग) कर लिया जाता है। क्योंकि यह योग द्वारा consumed हो जाता है, यह समीकरण के बाईं ओर दिखाई नहीं देता है। Indices $i$ और $j$ का चुनाव मनमाना (arbitrary) है; हम $m,n,p,q$ या किसी अन्य अक्षर का उपयोग कर सकते थे। सामान्य तौर पर, vector indices के लिए, वर्णमाला के मध्य के अक्षरों का उपयोग करना आम बात है।

अब हम vector $\mathbf{y}$ से vector $\mathbf{a}$ प्राप्त करने के लिए inverse relation खोजना चाहते हैं। दूसरे शब्दों में, हम $\mathbf{a} = V^{-1}(\omega) \cdot \mathbf{y}$ की गणना करना चाहते हैं, जहां $V^{-1}(\omega)$ , $V(\omega)$ का inverse है।

हमारा दावा है कि Vandermonde matrix $V(\omega)$ का inverse भी एक Vandermonde matrix होता है, जिसे $\frac{1}{k}V(\omega^{-1})$ द्वारा दिया जाता है।

पूरी तरह से स्पष्ट करने के लिए, हमारा दावा यह है कि

V^{-1}(\omega) = \frac{1}{k} V({\omega^{-1}})

जहां $\omega$ unity का एक primitive $k$ -th root है।

यदि दावा सही है, तो vector $\mathbf{a}$ की गणना निम्न प्रकार से की जा सकती है:

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

\begin{aligned}\begin{bmatrix}a_0 \\a_1 \\\vdots \\a_i \\\vdots \\a_{k-1}\end{bmatrix}&=\frac{1}{k}\begin{bmatrix}(\omega^0)^0 & (\omega^0)^1 & \cdots & (\omega^0)^{k-1} \\(\omega^{-1})^0 & (\omega^{-1})^1 & \cdots & (\omega^{-1})^{k-1} \\\vdots & \vdots & \ddots & \vdots \\(\omega^{-i})^0 & (\omega^{-i})^1 & \cdots & (\omega^{-i})^{k-1} \\\vdots & \vdots & \ddots & \vdots \\(\omega^{-(k-1)})^0 & (\omega^{-(k-1)})^1 & \cdots & (\omega^{-(k-1)})^{k-1}\end{bmatrix}\begin{bmatrix}f(\omega^0) \\f(\omega^1) \\\vdots \\f(\omega^{k-1})\end{bmatrix}\end{aligned}

Component $a_i$ , $\frac{1}{k}V(\omega^{-1})$ की $i$ -th पंक्ति और vector $\mathbf{y}$ के बीच का inner product है:

\begin{aligned} a_i &= \frac{1}{k} \begin{bmatrix} (\omega^{-i})^0 & (\omega^{-i})^1 & \cdots & (\omega^{-i})^{k-1} \end{bmatrix} \cdot \begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ \vdots \\ f(\omega^{k-1}) \end{bmatrix} \\ &=\frac{1}{k}(\omega^{-i})^0 f(\omega^0) + \frac{1}{k}(\omega^{-i})^1 f(\omega^1) + \ldots + \frac{1}{k}(\omega^{-i})^{k-1} f(\omega^{k-1}) \\&=\frac{1}{k}\omega^{-i0} f(\omega^0)\phantom{()} + \frac{1}{k}\omega^{-i1} f(\omega^1)\phantom{()} + \ldots + \frac{1}{k}\omega^{-i(k-1)} f(\omega^{k-1}) \end{aligned}

इस ऑपरेशन को निम्नलिखित योग (sum) के रूप में लिखा जा सकता है:

\begin{aligned} a_i &= \sum_{m=0}^{k-1} \frac{1}{k} \omega^{-im} f(\omega^m) \end{aligned}

$i\in\{0,1,2,...,k-1\}$ के लिए।

शैक्षणिक कारणों (pedagogical reasons) से, हम अपने दावे को - कि Vandermonde matrix $V(\omega)$ का inverse एक अन्य Vandermonde matrix है, जिसे $\frac{1}{k}V(\omega^{-1})$ द्वारा दिया जाता है - दो अलग-अलग तरीकों से सिद्ध करेंगे।

सबसे पहले, हम दिखाएंगे कि $V(\omega)$ और $\frac{1}{k}V(\omega^{-1})$ का matrix multiplication identity matrix $\mathbb{I}$ देता है, अर्थात,

V(\omega) \cdot \frac{1}{k}V(\omega^{-1}) = \mathbb{I}

फिर, हम दिखाएंगे कि यदि हम पहले $\mathbf{y}$ प्राप्त करने के लिए $V(\omega)$ को $\mathbf{a}$ से गुणा करते हैं, और फिर $\frac{1}{k}V(\omega^{-1})$ को $V(\omega)\mathbf{a}$ से गुणा करते हैं, तो हम वापस $\mathbf{a}$ प्राप्त कर लेते हैं।

ये दोनों प्रमाण अनिवार्य रूप से समान हैं, बस दो अलग-अलग तरीकों से व्यक्त किए गए हैं।

इसका प्रमाण कि $V(\omega) \cdot \frac{1}{k}V(\omega^{-1}) = \mathbb{I}$

हम सिद्ध करेंगे कि $V(\omega)$ का $\frac{1}{k} V(\omega^{-1})$ के साथ matrix multiplication, identity matrix देता है।

यह प्रमाण roots of unity की orthogonality property पर निर्भर करता है, जिसे एक summation के रूप में व्यक्त किया जाता है। इसलिए, हम पहले matrix multiplication को summation form में लिखते हैं ताकि हम इस orthogonality property का उपयोग कर सकें।

Index notation में $V(\omega) \cdot \frac{1}{k}V(\omega^{-1})$ का गुणन (multiplication)

याद करें कि पंक्ति $i$ और स्तंभ $m$ में $V(\omega)$ की matrix entry निम्न द्वारा दी जाती है:

\omega^{im}

नोट: यहां पंक्तियों और स्तंभों की नंबरिंग (numbering) $1$ के बजाय $0$ से मानी गई है।

उदाहरण के लिए, $V(\omega)$ की पंक्ति $1$ और स्तंभ $2$ में entry $(\omega^1)^2$ है, जैसा कि नीचे लाल रंग में highlight किया गया है:

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

इसके अलावा, पंक्ति $m$ और स्तंभ $j$ में $\frac{1}{k} V(\omega^{-1})$ की matrix entry निम्न द्वारा दी जाती है:

\frac{1}{k} \omega^{-mj}

उदाहरण के लिए, $\frac{1}{k} V(\omega^{-1})$ की पंक्ति $2$ और स्तंभ $0$ में entry $(\omega^{-2})^0$ है, जैसा कि नीचे highlight किया गया है:

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

इसलिए, जब दो matrices $V(\omega)$ और $\frac{1}{k} V(\omega^{-1})$ को गुणा किया जाता है, तो पंक्ति $i$ और स्तंभ $j$ में परिणामी तत्व $V(\omega)$ की पंक्ति $i$ (लाल) को $\frac{1}{k} V(\omega^{-1})$ के स्तंभ $j$ (नीला) के साथ गुणा करके प्राप्त किया जाता है:

V(\omega)\cdot \frac{1}{k} V(\omega^{-1}) = \begin{bmatrix}(\omega^0)^0 & (\omega^0)^1 & (\omega^0)^2 & \cdots & (\omega^0)^{k-1} \\(\omega^1)^0 & (\omega^1)^1 & (\omega^1)^{2} & \cdots & (\omega^1)^{k-1} \\\vdots & \vdots & \vdots & \ddots & \vdots \\ \color{red}(\omega^i)^0 & \color{red}(\omega^{i})^1 & \color{red}(\omega^i)^2 & \color{red}\cdots & \color{red}(\omega^i)^{k-1} \\\vdots & \vdots & \vdots & \ddots & \vdots \\ (\omega^{k-1})^0 & (\omega^{k-1})^1 & (\omega^{k-1})^2 & \cdots & (\omega^{k-1})^{k-1} \end{bmatrix} \frac{1}{k}\begin{bmatrix}(\omega^0)^0 & (\omega^0)^1 & \cdots \color{blue}(\omega^0)^j & \cdots & (\omega^0)^{k-1} \\(\omega^{-1})^0 & (\omega^{-1})^1 & \cdots \color{blue}(\omega^{-1})^{j} & \cdots & (\omega^{-1})^{k-1} \\ (\omega^{-2})^0 & (\omega^{-2})^1 & \cdots \color{blue}(\omega^{-2})^j & \cdots & (\omega^{-2})^{k-1} \\\vdots & \vdots & \color{blue}\vdots & \ddots & \vdots \\ (\omega^{-(k-1)})^0 & (\omega^{-(k-1)})^1 & \cdots \color{blue}(\omega^{-(k-1)})^j & \cdots & (\omega^{-(k-1)})^{k-1} \end{bmatrix}

Matrix $V(\omega) \cdot \frac{1}{k} V(\omega^{-1})$ की प्रत्येक entry, जिसे हम $M_{ij}$ द्वारा निरूपित करते हैं, तब निम्न प्रकार दी जाती है:

\begin{aligned}M_{ij} &= \color{red}{(\omega^i)^0}\,\color{blue}{(\omega^0)^j} + \color{red}{(\omega^i)^1}\,\color{blue}{(\omega^{-1})^j} + \cdots + \color{red}{(\omega^i)^{k-1}}\,\color{blue}{(\omega^{-(k-1)})^j}\\[6pt]&= \color{red}{\omega^{i0}}\,\color{blue}{\omega^{0j}} + \color{red}{\omega^{i1}}\,\color{blue}{\omega^{-1j}} + \cdots + \color{red}{\omega^{i(k-1)}}\,\color{blue}{\omega^{-(k-1)j}}\\[6pt]&= \sum_{m=0}^{k-1} \color{red}{\omega^{im}}\,\frac{1}{k}\color{blue}{\omega^{-mj}}\\[6pt]&= \frac{1}{k}\sum_{m=0}^{k-1} (\omega^{m})^{\,i-j}\end{aligned}

अब हमें यह दिखाना होगा कि entries $M_{ij}$ identity matrix की entries के बराबर हैं। ऐसा करने के लिए, हम roots of unity की orthogonality का उपयोग करते हैं।

याद करें: Roots of unity की Orthogonality

Roots of unity की orthogonality पर आधारित अध्याय में, हमने दिखाया था कि

\sum_{m=0}^{k-1} (\omega^{m})^{i-j}=\begin{cases}k, & \text{if } i\equiv j \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

संक्षेप में कहें तो, उपरोक्त सूत्र हमें दो स्थितियों में summation का परिणाम देता है: (1) जब $i\equiv j$ और (2) जब $i \not\equiv j$ । हम नीचे दोनों स्थितियों का उपयोग करेंगे।

स्थिति 1: जब $i\equiv j$

हम गणना करना चाहते हैं:

M_{ij} = \frac{1}{k}\sum_{m=0}^{k-1} (\omega^{m})^{\,i-j}

जब $i\equiv j$ हो। Roots of unity की orthogonality कहती है कि, जब $i\equiv j$ ,

\sum_{m=0}^{k-1} (\omega^{m})^{\,i-j} = k

$M_{ij}$ के लिए इस परिणाम का उपयोग करने पर, हमें प्राप्त होता है:

\begin{aligned} M_{ij} &= \frac{1}{k} \boxed{\sum_{m=0}^{k-1} (\omega^{m})^{\,i-j}} \\ &= \frac{1}{k} k = 1 \end{aligned}

इस प्रकार, diagonal terms (जैसे $M_{00}, M_{11}, M_{22},...,M_{(k-1)(k-1)}$ ) के लिए, हमारे पास है:

\begin{aligned} M_{ij} &= 1 && \text{when }i = j \end{aligned}

स्थिति 2: जब $i \not\equiv j$

अब हम गणना करना चाहते हैं:

M_{ij} = \frac{1}{k}\sum_{m=0}^{k-1} (\omega^{m})^{\,i-j}

जब $i\not\equiv j$ हो। Roots of unity की orthogonality कहती है कि, जब $i\not\equiv j$ ,

\sum_{m=0}^{k-1} (\omega^{m})^{\,i-j} = 0

$M_{ij}$ के लिए इस परिणाम का उपयोग करने पर, हमारे पास है:

\begin{aligned} M_{ij} &= \frac{1}{k} \boxed{\sum_{m=0}^{k-1} (\omega^{m})^{\,i-j}} \\ &= \frac{1}{k} 0 = 0 \end{aligned}

इसलिए, किसी भी non-diagonal terms (जैसे $M_{10}, M_{01}, M_{12}, \dots$ ) के लिए, हमारे पास $M_{ij} = 0$ है।

Matrix $M$

उपरोक्त स्थितियों (1) और (2) को ध्यान में रखते हुए, हमें प्राप्त होता है कि matrix $M = (M_{ij})$ है:

M =\begin{pmatrix}1 & 0 & \cdots & 0 \\0 & 1 & \cdots & 0 \\\vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 1\end{pmatrix}

जो बिल्कुल identity matrix $\mathbb{I}$ है। इस प्रकार, matrices $V(\omega)$ और $\frac{1}{k} V(\omega^{-1})$ एक दूसरे के inverses हैं, क्योंकि

V(\omega) \cdot \left(\frac{1}{k} V(\omega^{-1})\right) = M = \mathbb{I}

Vector $\mathbf{y}$ के साथ $\frac{1}{k}V(\omega^{-1})$ का Matrix multiplication वापस vector $\mathbf{a}$ देता है

यह दिखाने का दूसरा तरीका कि $\frac{1}{k} V(\omega^{-1})$ , $V(\omega)$ का inverse है, यह दिखाना है कि यह बाद वाले (latter) को invert करता है।

अर्थात, यदि हम पहले $\mathbf{y}$ प्राप्त करने के लिए $V(\omega)$ को $\mathbf{a}$ पर लागू करते हैं,

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

और फिर $\mathbf{y}$ पर $\frac{1}{k}V(\omega^{-1})$ लागू करते हैं, तो हम $\mathbf{a}$ वापस प्राप्त कर लेते हैं:

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

हम बिल्कुल यही दिखाएंगे।

पहला transformation: $\mathbf{y} = V(\omega) \cdot \mathbf{a}$

पहला transformation निम्नलिखित matrix operation के माध्यम से coefficients के vector $\mathbf{a}$ को evaluations के vector $\mathbf{y}$ में ले जाता है:

\begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ f(\omega^2) \\ \vdots \\ f(\omega^{k-1}) \end{bmatrix} = \begin{bmatrix}(\omega^0)^0 & (\omega^0)^1 & (\omega^0)^2 & \cdots & (\omega^0)^{k-1} \\(\omega^1)^0 & (\omega^1)^1 & (\omega^1)^{2} & \cdots & (\omega^1)^{k-1} \\ (\omega^2)^0 & (\omega^{2})^1 & (\omega^2)^2 & \cdots & (\omega^2)^{k-1} \\\vdots & \vdots & \vdots & \ddots & \vdots \\ (\omega^{k-1})^0 & (\omega^{k-1})^1 & (\omega^{k-1})^2 & \cdots & (\omega^{k-1})^{k-1} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{k-1} \end{bmatrix}

जैसा कि हम पहले ही देख चुके हैं, इस matrix operation को indices का उपयोग करके लिखा जा सकता है:

f(\omega^i) = \sum_{j=0}^{k-1} \omega^{ij} a_j

दूसरा transformation: $\mathbf{\tilde{a}} = \frac{1}{k}V(\omega^{-1}) \mathbf{y}$

अब हम vector $\mathbf{y}$ पर एक दूसरा transformation करते हैं, जिसके परिणामस्वरूप एक vector $\mathbf{\tilde{a}}$ प्राप्त होता है:

\begin{bmatrix} \tilde{a}_0 \\ \tilde{a}_1 \\ \tilde{a}_2 \\\vdots \\ \tilde{a}_{k-1} \end{bmatrix}= \frac{1}{k}\begin{bmatrix}(\omega^0)^0 & (\omega^0)^1 & (\omega^0)^2 & \cdots & (\omega^0)^{k-1} \\(\omega^{-1})^0 & (\omega^{-1})^1 & (\omega^{-1})^{2} & \cdots & (\omega^{-1})^{k-1} \\ (\omega^{-2})^0 & (\omega^{-2})^1 & (\omega^{-2)^2 & \cdots & (\omega^{-2})^{k-1} \\\vdots & \vdots & \vdots & \ddots & \vdots \\ (\omega^{-(k-1)})^0 & (\omega^{-(k-1)})^1 & (\omega^{-(k-1)})^2 & \cdots & (\omega^{-(k-1)})^{k-1} \end{bmatrix} \begin{bmatrix} f(\omega^0) \\ f(\omega^1) \\ f(\omega^2) \\\vdots \\ f(\omega^{k-1}) \end{bmatrix}

यदि हम यह दिखा सकें कि $\mathbf{a} = \mathbf{\tilde{a}}$ , तो दूसरा transformation पहले वाले का inverse होगा।

उपरोक्त matrix operation को index form में इस प्रकार लिखा जा सकता है:

\tilde{a}_j = \sum_{m=0}^{k-1} \frac{1}{k} \omega^{-jm} f(\omega^m)

अब $f(\omega^i)$ के लिए expression (व्यंजक) को substitute (प्रतिस्थापित) करें। याद करें कि

f(\omega^i) = \sum_{j=0}^{k-1} \omega^{ij} a_j

जहां $i$ सिर्फ एक index है जिसे हम $m$ , या किसी अन्य अक्षर से बदल सकते हैं। इस प्रकार, $\tilde{a}_j$ के परिणाम में $f(\omega^m)$ को प्रतिस्थापित करने पर, हमारे पास है:

\begin{aligned} \tilde{a}_j &= \sum_{m=0}^{k-1} \frac{1}{k} \omega^{-jm} f(\omega^m) \\ &= \sum_{m=0}^{k-1} \frac{1}{k} \omega^{-jm} \left(\sum_{i=0}^{k-1} \omega^{mi} a_i \right) \end{aligned}

Double sum के रूप में फिर से लिखना:

\begin{aligned} \tilde{a}_j &= \sum_{i=0}^{k-1} \sum_{m=0}^{k-1} \frac{1}{k} \omega^{-jm} \omega^{mi} a_i \\ &= \sum_{i=0}^{k-1} \frac{1}{k} \left( \sum_{m=0}^{k-1} \omega^{m(i-j)} \right) a_i \end{aligned}

कोष्ठक (parentheses) में मौजूद पद (term) बिल्कुल orthogonality relation है:

\sum_{m=0}^{k-1} (\omega^{m})^{i-j}=\begin{cases}k, & \text{if } i\equiv j \pmod{k},\\[6pt]0, & \text{otherwise}.\end{cases}

प्रमाण को जारी रखने के लिए, हम स्थिति (1), जहां $i=j$ , और स्थिति (2), जहां $i \neq j$ का अध्ययन कर सकते थे, लेकिन हम एक अलग तरीके से आगे बढ़ेंगे। हम Kronecker delta नामक एक प्रतीक का परिचय देंगे।

Kronecker delta, $\delta_{ij}$ , इस मामले में $i$ और $j$ 2 indices वाला एक प्रतीक है, जो $i=j$ होने पर $1$ होता है और अन्यथा $0$ होता है:

\delta_{ij} =\begin{cases}1 & \text{if } i = j \\0 & \text{if } i \ne j\end{cases}

Kronecker delta को identity matrix की entries के रूप में समझा जा सकता है।

Kronecker delta का उपयोग करते हुए, हम orthogonality property को इस प्रकार लिख सकते हैं:

\sum_{m=0}^{k-1} (\omega^{m})^{i-j} = k \delta_{ij}

$\tilde{a}_j$ के expression में Kronecker delta का उपयोग करने पर, हमारे पास है:

\begin{aligned} \tilde{a}_j &= \sum_{i=0}^{k-1} \frac{1}{k} \left( \sum_{m=0}^{k-1} \omega^{m(i-j)} \right) a_i \\ &= \sum_{i=0}^{k-1} \frac{1}{k} \left( k\delta_{ij} \right) a_i \\ &= \sum_{i=0}^{k-1} \frac{1}{\cancel{k}} \left( \cancel{k}\delta_{ij} \right) a_i \\ &= \sum_{i=0}^{k-1} \delta_{ij} a_i \end{aligned}

Summation का विस्तार (expanding) करने पर, उपरोक्त expression को इस प्रकार लिखा जा सकता है:

\tilde{a}_j = \delta_{0j} a_0 + \delta_{1j} a_1 + \delta_{2j} a_2 + ... + \delta_{(k-1)j}a_{k-1}

Kronecker delta property के अनुसार, summation में केवल एक पद nonzero (अशून्य) होता है। उदाहरण के लिए, $j=2$ के लिए, केवल $\delta_{22}$ nonzero है। इस प्रकार, हमारे पास है:

\begin{aligned} \tilde{a}_2 &= \delta_{02} a_0 + \delta_{12} a_1 + \delta_{22} a_2 + \cdots + \delta_{(k-1)2} a_{k-1} \\ &= \cancel{\delta_{02} a_0} + \cancel{\delta_{12} a_1} + \delta_{22} a_2 + \cdots + \cancel{\delta_{(k-1)2} a_{k-1}} \\ &= a_2 \end{aligned}

यह किसी भी $j$ के लिए सत्य है, इसलिए हम कह सकते हैं कि

\tilde{a}_j = a_j

किसी भी $j$ के लिए।

यह दर्शाता है कि transformation $\frac{1}{k} V(\omega^{-1})$ , transformation $V(\omega)$ का inverse है।

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