लाप्लास विस्तार

This article is about the expression of a determinant in terms of minors. For the approximation of radial potentials, see Laplace expansion (potential).

रैखिक बीजगणित में, पियरे-साइमन लाप्लास के नाम पर लाप्लास विस्तार, जिसे कॉफ़ैक्टर विस्तार भी कहा जाता है, एक के निर्धारक की अभिव्यक्ति है n × n मैट्रिक्स (गणित) B माइनर (रैखिक बीजगणित) के भारित योग के रूप में, जो कुछ के निर्धारक हैं (n − 1) × (n − 1) की उपमात्रियाँ B. विशेष रूप से, प्रत्येक के लिए i,

$${\begin{aligned}\det(B)&=\sum _{j=1}^{n}(-1)^{i+j}B_{i,j}M_{i,j},\end{aligned}}$$

कहाँ पे $B_{i,j}$ का प्रवेश है iवीं पंक्ति और jका स्तम्भ B, तथा $M_{i,j}$ को हटाकर प्राप्त सबमैट्रिक्स का निर्धारक है iवीं पंक्ति और jका स्तम्भ B.

शब्द $(-1)^{i+j}M_{i,j}$ का सहकारक (रैखिक बीजगणित) कहलाता है $B_{i,j}$ में B.

लाप्लास विस्तार अक्सर सबूतों में उपयोगी होता है, उदाहरण के लिए, मेट्रिसेस के आकार पर पुनरावृत्ति की अनुमति देता है। यह अपनी सादगी के लिए उपदेशात्मक रुचि का भी है, और निर्धारक को देखने और गणना करने के कई तरीकों में से एक है। गॉसियन एलिमिनेशन की तुलना में, बड़े मेट्रिसेस के लिए, यह जल्दी से गणना करने में अक्षम हो जाता है।

उदाहरण

मैट्रिक्स पर विचार करें

$B={\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}}.$

इस मैट्रिक्स के निर्धारक की गणना इसकी किसी एक पंक्ति या स्तंभ के साथ लाप्लास विस्तार का उपयोग करके की जा सकती है। उदाहरण के लिए, पहली पंक्ति के साथ एक विस्तार से पैदावार होती है:

${\begin{aligned}|B|&=1\cdot {\begin{vmatrix}5&6\\8&9\end{vmatrix}}-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+3\cdot {\begin{vmatrix}4&5\\7&8\end{vmatrix}}\\[5pt]&=1\cdot (-3)-2\cdot (-6)+3\cdot (-3)=0.\end{aligned}}$

दूसरे स्तंभ के साथ लाप्लास विस्तार से समान परिणाम प्राप्त होता है:

${\begin{aligned}|B|&=-2\cdot {\begin{vmatrix}4&6\\7&9\end{vmatrix}}+5\cdot {\begin{vmatrix}1&3\\7&9\end{vmatrix}}-8\cdot {\begin{vmatrix}1&3\\4&6\end{vmatrix}}\\[5pt]&=-2\cdot (-6)+5\cdot (-12)-8\cdot (-6)=0.\end{aligned}}$

यह सत्यापित करना आसान है कि परिणाम सही है: मैट्रिक्स व्युत्क्रमणीय मैट्रिक्स है क्योंकि इसके पहले और तीसरे कॉलम का योग दूसरे कॉलम का दोगुना है, और इसलिए इसका निर्धारक शून्य है।

प्रमाण

मान लीजिए $B$ एक n × n मैट्रिक्स है और $i,j\in \{1,2,\dots ,n\}.$ स्पष्टता के लिए हम की प्रविष्टियों को भी लेबल करते हैं $B$ जो इसकी रचना करता है $i,j$ मामूली मैट्रिक्स $M_{ij}$ जैसा

$(a_{st})$ के लिये $1\leq s,t\leq n-1.$ के विस्तार में शर्तों पर विचार करें $|B|$ है कि $b_{ij}$ एक कारक के रूप में। प्रत्येक का रूप है

$\operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{i,j}\cdots b_{n,\tau (n)}=\operatorname {sgn} \tau \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}$

कुछ सम और विषम क्रमपरिवर्तन के लिए τ ∈ S_n साथ $\tau (i)=j$, और एक अद्वितीय और स्पष्ट रूप से संबंधित क्रमपरिवर्तन $\sigma \in S_{n-1}$ जो समान छोटी प्रविष्टियों का चयन करता है τ. इसी प्रकार प्रत्येक विकल्प σ संगत निर्धारित करता है τ यानी पत्राचार $\sigma \leftrightarrow \tau$ के बीच आपत्ति है $S_{n-1}$ तथा $\{\tau \in S_{n}\colon \tau (i)=j\}.$ क्रमचय का प्रयोग#परिभाषा और अंकन|कॉची का दो-पंक्ति संकेतन, के बीच स्पष्ट संबंध $\tau$ तथा $\sigma$ रूप में लिखा जा सकता है

$\sigma ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))\end{pmatrix}}$

कहाँ पे $(\leftarrow )_{j}$ चक्र संकेतन के लिए एक अस्थायी आशुलिपि संकेतन है $(n,n-1,\cdots ,j+1,j)$. यह ऑपरेशन j से बड़े सभी सूचकांकों को घटाता है ताकि प्रत्येक सूचकांक सेट {1,2,...,n-1} में फिट हो सके

क्रमपरिवर्तन τ से प्राप्त किया जा सकता है σ निम्नलिखित नुसार। परिभाषित करना $\sigma '\in S_{n}$ द्वारा $\sigma '(k)=\sigma (k)$ के लिये $1\leq k\leq n-1$ तथा $\sigma '(n)=n$. फिर $\sigma '$ रूप में अभिव्यक्त किया जाता है

$\sigma '={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}$

अब, ऑपरेशन जो लागू होता है $(\leftarrow )_{i}$ पहले और फिर आवेदन करें $\sigma '$ है (बी से पहले ए को लागू करने की सूचना समकक्ष है दो-पंक्ति संकेतन में B की ऊपरी पंक्ति में A का व्युत्क्रम लगाने के लिए)

$\sigma '(\leftarrow )_{i}={\begin{pmatrix}1&2&\cdots &i+1&\cdots &n&i\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &(\leftarrow )_{j}(\tau (i+1))&\cdots &(\leftarrow )_{j}(\tau (n))&n\end{pmatrix}}$

कहाँ पे $(\leftarrow )_{i}$ के लिए अस्थायी आशुलिपि संकेतन है $(n,n-1,\cdots ,i+1,i)$.

ऑपरेशन जो लागू होता है $\tau$ पहले और फिर लागू होता है $(\leftarrow )_{j}$ है

$(\leftarrow )_{j}\tau ={\begin{pmatrix}1&2&\cdots &i&\cdots &n-1&n\\(\leftarrow )_{j}(\tau (1))&(\leftarrow )_{j}(\tau (2))&\cdots &n&\cdots &(\leftarrow )_{j}(\tau (n-1))&(\leftarrow )_{j}(\tau (n))\end{pmatrix}}$

ऊपर दो इस प्रकार बराबर हैं,

$(\leftarrow )_{j}\tau =\sigma '(\leftarrow )_{i}$

$\tau =(\rightarrow )_{j}\sigma '(\leftarrow )_{i}$

कहाँ पे $(\rightarrow )_{j}$ का विलोम है $(\leftarrow )_{j}$ जो है $(j,j+1,\cdots ,n)$.

इस प्रकार

$\tau \,=(j,j+1,\ldots ,n)\sigma '(n,n-1,\ldots ,i)$

चूंकि दो चक्र अंकन क्रमशः के रूप में लिखे जा सकते हैं $n-i$ तथा $n-j$ स्थानान्तरण (गणित),

$\operatorname {sgn} \tau \,=(-1)^{2n-(i+j)}\operatorname {sgn} \sigma '\,=(-1)^{i+j}\operatorname {sgn} \sigma .$

और नक्शे के बाद से $\sigma \leftrightarrow \tau$ विशेषण है,

${\begin{aligned}\sum _{i=1}^{n}\sum _{\tau \in S_{n}:\tau (i)=j}\operatorname {sgn} \tau \,b_{1,\tau (1)}\cdots b_{n,\tau (n)}&=\sum _{i=1}^{n}\sum _{\sigma \in S_{n-1}}(-1)^{i+j}\operatorname {sgn} \sigma \,b_{ij}a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}\sum _{\sigma \in S_{n-1}}\operatorname {sgn} \sigma \,a_{1,\sigma (1)}\cdots a_{n-1,\sigma (n-1)}\\&=\sum _{i=1}^{n}b_{ij}(-1)^{i+j}M_{ij}\end{aligned}}$

जिससे परिणाम निकलता है। इसी प्रकार, यदि बाहरी योग के सूचकांक को इसके साथ बदल दिया जाता है, तो परिणाम होता है $j$.

पूरक नाबालिगों द्वारा एक निर्धारक का लाप्लास विस्तार

लाप्लास के कॉफ़ेक्टर विस्तार को निम्नानुसार सामान्यीकृत किया जा सकता है।

उदाहरण

मैट्रिक्स पर विचार करें

$A={\begin{bmatrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{bmatrix}}.$

इस मैट्रिक्स के निर्धारक की गणना पहले दो पंक्तियों के साथ लाप्लास के कॉफ़ेक्टर विस्तार का उपयोग करके की जा सकती है। सबसे पहले ध्यान दें कि इसमें दो अलग-अलग संख्याओं के 6 सेट हैं {1, 2, 3, 4}, अर्थात् चलो $S=\left\{\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}\right\}$ उपरोक्त सेट हो।

होने के लिए पूरक सहकारकों को परिभाषित करके

$b_{\{j,k\}}={\begin{vmatrix}a_{1j}&a_{1k}\\a_{2j}&a_{2k}\end{vmatrix}},$

$c_{\{p,q\}}={\begin{vmatrix}a_{3p}&a_{3q}\\a_{4p}&a_{4q}\end{vmatrix}},$

और उनके क्रमपरिवर्तन का चिह्न होना

$\varepsilon ^{\{j,k\},\{p,q\}}=\operatorname {sgn} {\begin{bmatrix}1&2&3&4\\j&k&p&q\end{bmatrix}},{\text{ where }}p\neq j,q\neq k.$

ए के निर्धारक के रूप में लिखा जा सकता है

$|A|=\sum _{H\in S}\varepsilon ^{H,H^{\prime }}b_{H}c_{H^{\prime }},$

कहाँ पे $H^{\prime }$ का पूरक सेट है $H$.

हमारे स्पष्ट उदाहरण में यह हमें देता है

${\begin{aligned}|A|&=b_{\{1,2\}}c_{\{3,4\}}-b_{\{1,3\}}c_{\{2,4\}}+b_{\{1,4\}}c_{\{2,3\}}+b_{\{2,3\}}c_{\{1,4\}}-b_{\{2,4\}}c_{\{1,3\}}+b_{\{3,4\}}c_{\{1,2\}}\\[5pt]&={\begin{vmatrix}1&2\\5&6\end{vmatrix}}\cdot {\begin{vmatrix}11&12\\15&16\end{vmatrix}}-{\begin{vmatrix}1&3\\5&7\end{vmatrix}}\cdot {\begin{vmatrix}10&12\\14&16\end{vmatrix}}+{\begin{vmatrix}1&4\\5&8\end{vmatrix}}\cdot {\begin{vmatrix}10&11\\14&15\end{vmatrix}}+{\begin{vmatrix}2&3\\6&7\end{vmatrix}}\cdot {\begin{vmatrix}9&12\\13&16\end{vmatrix}}-{\begin{vmatrix}2&4\\6&8\end{vmatrix}}\cdot {\begin{vmatrix}9&11\\13&15\end{vmatrix}}+{\begin{vmatrix}3&4\\7&8\end{vmatrix}}\cdot {\begin{vmatrix}9&10\\13&14\end{vmatrix}}\\[5pt]&=-4\cdot (-4)-(-8)\cdot (-8)+(-12)\cdot (-4)+(-4)\cdot (-12)-(-8)\cdot (-8)+(-4)\cdot (-4)\\[5pt]&=16-64+48+48-64+16=0.\end{aligned}}$

ऊपर के रूप में, यह सत्यापित करना आसान है कि परिणाम सही है: मैट्रिक्स व्युत्क्रमणीय मैट्रिक्स है क्योंकि इसके पहले और तीसरे कॉलम का योग दूसरे कॉलम का दोगुना है, और इसलिए इसका निर्धारक शून्य है।

सामान्य कथन

होने देना $B=[b_{ij}]$ सेम n × n मैट्रिक्स और $S$ के समुच्चय k-तत्व का सबसेट {1, 2, ... , n}, $H$ इसमें एक तत्व। फिर का निर्धारक $B$ के साथ बढ़ाया जा सकता है k पंक्तियों द्वारा पहचाना गया $H$ निम्नलिखित नुसार:

$|B|=\sum _{L\in S}\varepsilon ^{H,L}b_{H,L}c_{H,L}$

कहाँ पे $\varepsilon ^{H,L}$ द्वारा निर्धारित क्रमपरिवर्तन का संकेत है $H$ तथा $L$, के बराबर $(-1)^{\left(\sum _{h\in H}h\right)+\left(\sum _{\ell \in L}\ell \right)}$, $b_{H,L}$ का वर्ग माइनर $B$ से हटाकर प्राप्त किया $B$ पंक्तियों और स्तंभों में सूचकांकों के साथ $H$ तथा $L$ क्रमशः, और $c_{H,L}$ (का पूरक कहा जाता है $b_{H,L}$) परिभाषित किया गया है $b_{H',L'}$ , $H'$ तथा $L'$ का पूरक होना $H$ तथा $L$ क्रमश।

यह उपरोक्त प्रमेय के साथ मेल खाता है जब $k=1$. किसी भी नियत के लिए यही बात लागू होती है k कॉलम।

कम्प्यूटेशनल व्यय

लाप्लास विस्तार उच्च-आयाम मैट्रिसेस के लिए कम्प्यूटेशनल रूप से अक्षम है, बड़े ओ नोटेशन में समय जटिलता के साथ O(n!). वैकल्पिक रूप से, LU अपघटन के रूप में त्रिकोणीय मैट्रिक्स में एक अपघटन का उपयोग निर्धारकों को एक समय जटिलता के साथ उत्पन्न कर सकता है O(n³). निम्नलिखित पायथन (प्रोग्रामिंग भाषा) कोड लाप्लास विस्तार को पुनरावर्ती रूप से लागू करता है: <वाक्यविन्यास लैंग = पायथन 3> डेफ निर्धारक (एम):

   # रिकर्सिव फ़ंक्शन का बेस केस: 1x1 मैट्रिक्स
   अगर लेन (एम) == 1:
       वापसी एम [0] [0]

   कुल = 0
   स्तंभ के लिए, गणना में तत्व (एम [0]):
       # पहली पंक्ति और वर्तमान कॉलम को बाहर करें।
       K = [x[:column] + x[column + 1 :] for x in M[1:
       एस = 1 अगर कॉलम% 2 == 0 और -1
       कुल + = एस * तत्व * निर्धारक (के)
   कुल वापसी

</वाक्यविन्यास हाइलाइट>

यह भी देखें

• निर्धारकों के लिए लीबनिज सूत्र
• के लिए सारस का नियम $3\times 3$ निर्धारकों

संदर्भ

• David Poole: Linear Algebra. A Modern Introduction. Cengage Learning 2005, ISBN 0-534-99845-3, pp. 265–267 (restricted online copy, p. 265, at Google Books)
• Harvey E. Rose: Linear Algebra. A Pure Mathematical Approach. Springer 2002, ISBN 3-7643-6905-1, pp. 57–60 (restricted online copy, p. 57, at Google Books)

बाहरी संबंध

• Laplace expansion in C (in Portuguese)
• Laplace expansion in Java (in Portuguese)