دائم (رياضيات)

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 68 صور
الموسوعة الحرة

في الجبر الخطي ، يُعدّ الثابت للمصفوفة المربعة دالةً للمصفوفة، على غرار المحدد . والثابت، كما المحدد، هو متعدد حدود في عناصر المصفوفة. [ 1 ] وكلاهما حالتان خاصتان لدالة أكثر عمومية للمصفوفة تُسمى الدالة الجوهرية .

تعريف

يُعرَّف العنصر الدائم لمصفوفة A = ( a i , j ) من الرتبة n × n على النحو التالي:

موج الشعر بإستمرار⁡(أ)=∑σ∈Sن∏أنا=1نأأنا،σ(أنا).{\displaystyle \operatorname {perm} (A)=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}.}

يمتد المجموع هنا على جميع العناصر σ للمجموعة المتناظرة S n ؛ أي على جميع تباديل الأعداد 1، 2، ...، n .

على سبيل المثال،

موج الشعر بإستمرار⁡(أبجد)=أد+بج،{\displaystyle \operatorname {perm} {\begin{pmatrix}a&b\\c&d\end{pmatrix}}=ad+bc,}

و

موج الشعر بإستمرار⁡(أبجدهـوزحأنا)=أهـأنا+بوز+جدح+جهـز+بدأنا+أوح.{\displaystyle \operatorname {perm} {\begin{pmatrix}a&b&c\\d&e&f\\g&h&i\end{pmatrix}}=aei+bfg+cdh+ceg+bdi+afh.}

يختلف تعريف الثابت لـ A عن تعريف محدد A في أن توقيعات التباديل لا تؤخذ في الاعتبار.

يُرمز إلى العنصر الدائم للمصفوفة A بالرمز per A أو perm A أو Per A ، وأحيانًا يُحاط الوسيط بأقواس. يستخدم مينك الرمز Per( A ) للعنصر الدائم للمصفوفات المستطيلة، والرمز per( A ) عندما تكون A مصفوفة مربعة. [ 2 ] يستخدم موير وميتزلر الترميز التالي:|+|+{\displaystyle {\overset {+}{|}}\quad {\overset {+}{|}}}[ 3 ]​

كلمة " دائم " نشأت مع كوشي في عام 1812 بمعنى "fonctions symétriques permanentes" لنوع مشابه من الدوال، [ 4 ] وقد استخدمها موير وميتزلر [ 5 ] بالمعنى الحديث والأكثر تحديدًا. [ 6 ]

ملكيات

إذا نظرنا إلى الدالة الدائمة على أنها دالة تأخذ n متجهات كمعاملات، فإنها دالة متعددة الخطية ومتناظرة (بمعنى أن أي ترتيب للمتجهات ينتج عنه نفس الدالة الدائمة). علاوة على ذلك، بالنظر إلى مصفوفة مربعةأ=(أأناج){\displaystyle A=\left(a_{ij}\right)}من الرتبة n : [ 7 ]

  • خاصية perm( A ) ثابتة تحت أي تبديلات عشوائية لصفوف و/أو أعمدة المصفوفة A. ويمكن كتابة هذه الخاصية رمزياً على النحو التالي: perm( A ) = perm( PAQ ) لأي مصفوفات تبديل مناسبة الحجم P و Q.
  • يؤدي ضرب أي صف أو عمود واحد من المصفوفة A في قيمة عددية λ إلى تغيير perm( A ) إلى λ ⋅perm( A ).
  • perm( A ) ثابت تحت التبديل ، أي أن perm( A ) = perm( A T ).
  • لوأ=(أأناج){\displaystyle A=\left(a_{ij}\right)}وب=(بأناج){\displaystyle B=\left(b_{ij}\right)}إذا كانت مصفوفات مربعة من الرتبة n ، فإنموج الشعر بإستمرار⁡(أ+ب)=∑s،تموج الشعر بإستمرار⁡(أأناج)أنا∈s،ج∈تموج الشعر بإستمرار⁡(بأناج)أنا∈s¯،ج∈ت¯،{\displaystyle \operatorname {perm} \left(A+B\right)=\sum _{s,t}\operatorname {perm} \left(a_{ij}\right)_{i\in s,j\in t}\operatorname {perm} \left(b_{ij}\right)_{i\in {\bar {s}},j\in {\bar {t}}},}حيث s و t مجموعتان جزئيتان من نفس الحجم من {1، 2، ...، n } وs¯،ت¯{\displaystyle {\bar {s}},{\bar {t}}}[ 8 ] وهي مكملاتها الخاصة في تلك المجموعة.
  • لوأ{\displaystyle A}هي مصفوفة مثلثية ، أيأأناج=0{\displaystyle a_{ij}=0}حينماأنا>ج{\displaystyle i>j}أو بدلاً من ذلك، متى ماأنا<ج{\displaystyle i<j}ثم يكون الناتج الدائم مساوياً لحاصل ضرب عناصر القطر الرئيسي:موج الشعر بإستمرار⁡(أ)=أ11أ22⋯أنن=∏أنا=1نأأناأنا.{\displaystyle \operatorname {perm} \left(A\right)=a_{11}a_{22}\cdots a_{nn}=\prod _{i=1}^{n}a_{ii}.}

مقارنة بالمحددات

يمتد توسيع لابلاس بواسطة المحددات الصغرى لحساب المحدد على طول صف أو عمود أو قطر إلى المحدد الدائم عن طريق تجاهل جميع الإشارات. [ 9 ]

لكلأنا{\textstyle i}،

صهـرم(ب)=∑ج=1نبأنا،جمأنا،ج،{\displaystyle \mathbb {perm} (B)=\sum _{j=1}^{n}B_{i,j}M_{i,j},}

أينبأنا،ج{\displaystyle B_{i,j}}يمثل العنصر الموجود في الصف i والعمود j من المصفوفة B ، ومأنا،ج{\textstyle M_{i,j}}هو العنصر الدائم للمصفوفة الفرعية التي تم الحصول عليها عن طريق إزالة الصف i والعمود j من B.

على سبيل المثال، التوسع على طول العمود الأول،

موج الشعر بإستمرار⁡(1111210030104001)=1⋅موج الشعر بإستمرار⁡(100010001)+2⋅موج الشعر بإستمرار⁡(111010001)+ 3⋅موج الشعر بإستمرار⁡(111100001)+4⋅موج الشعر بإستمرار⁡(111100010)=1(1)+2(1)+3(1)+4(1)=10،{\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&1\cdot \operatorname {perm} \left({\begin{matrix}1&0&0\\0&1&0\\0&0&1\end{matrix}}\right)+2\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\0&1&0\\0&0&1\end{matrix}}\right)\\&{}+\ 3\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&0&1\end{matrix}}\right)+4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)\\={}&1(1)+2(1)+3(1)+4(1)=10,\end{aligned}}}

بينما يؤدي التوسع على طول الصف الأخير إلى،

موج الشعر بإستمرار⁡(1111210030104001)=4⋅موج الشعر بإستمرار⁡(111100010)+0⋅موج الشعر بإستمرار⁡(111200310)+ 0⋅موج الشعر بإستمرار⁡(111210300)+1⋅موج الشعر بإستمرار⁡(111210301)=4(1)+0+0+1(6)=10.{\displaystyle {\begin{aligned}\operatorname {perm} \left({\begin{matrix}1&1&1&1\\2&1&0&0\\3&0&1&0\\4&0&0&1\end{matrix}}\right)={}&4\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\1&0&0\\0&1&0\end{matrix}}\right)+0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&0&0\\3&1&0\end{matrix}}\right)\\&{}+\ 0\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&0\end{matrix}}\right)+1\cdot \operatorname {perm} \left({\begin{matrix}1&1&1\\2&1&0\\3&0&1\end{matrix}}\right)\\={}&4(1)+0+0+1(6)=10.\end{aligned}}}

من جهة أخرى، فإن خاصية الضرب الأساسية للمحددات لا تنطبق على الثوابت. [ 10 ] مثال بسيط يوضح ذلك.

4=موج الشعر بإستمرار⁡(1111)موج الشعر بإستمرار⁡(1111)≠موج الشعر بإستمرار⁡((1111)(1111))=موج الشعر بإستمرار⁡(2222)=8.{\displaystyle {\begin{aligned}4&=\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\operatorname {perm} \left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\\&\neq \operatorname {perm} \left(\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\left({\begin{matrix}1&1\\1&1\end{matrix}}\right)\right)=\operatorname {perm} \left({\begin{matrix}2&2\\2&2\end{matrix}}\right)=8.\end{aligned}}}

على عكس المحدد، لا يوجد تفسير هندسي سهل للمتغير الدائم؛ ويُستخدم بشكل أساسي في التوافقية ، وفي معالجة دوال غرين للبوزونات في نظرية الحقل الكمومي ، وفي تحديد احتمالات الحالة لأنظمة أخذ عينات البوزونات . [ 11 ] ومع ذلك، له تفسيران في نظرية المخططات : كمجموع أوزان أغطية الدورات في مخطط موجه ، وكمجموع أوزان المطابقات الكاملة في مخطط ثنائي الأجزاء .

التطبيقات

الموترات المتناظرة

ينشأ الثابت بشكل طبيعي في دراسة قوة الموتر المتناظر لفضاءات هيلبرت . [ 12 ] على وجه الخصوص، بالنسبة لفضاء هيلبرتح{\displaystyle H}، يترك∨كح{\displaystyle \vee ^{k}H}يشير إلىك{\displaystyle k}القوة الموترية المتناظرة لـح{\displaystyle H}، وهو فضاء الموترات المتناظرة . لاحظ على وجه الخصوص أن∨كح{\displaystyle \vee ^{k}H}يتم توليدها بواسطة الضرب المتناظر للعناصر فيح{\displaystyle H}. لx1،x2،...،xك∈ح{\displaystyle x_{1},x_{2},\dots ,x_{k}\in H}نُعرّف الضرب المتناظر لهذه العناصر بـ x1∨x2∨⋯∨xك=(ك!)-1/2∑σ∈Sكxσ(1)⊗xσ(2)⊗⋯⊗xσ(ك){\displaystyle x_{1}\vee x_{2}\vee \cdots \vee x_{k}=(k!)^{-1/2}\sum _{\sigma \in S_{k}}x_{\sigma (1)}\otimes x_{\sigma (2)}\otimes \cdots \otimes x_{\sigma (k)}} إذا نظرنا∨كح{\displaystyle \vee ^{k}H}(كمساحة فرعية من⊗كح{\displaystyle \otimes ^{k}H}، القوة الموترية رقم k لـح{\displaystyle H}) وعرّف الضرب الداخلي على∨كح{\displaystyle \vee ^{k}H}وبناءً على ذلك، نجد أنه بالنسبة لـxج،yج∈ح{\displaystyle x_{j},y_{j}\in H}⟨x1∨x2∨⋯∨xك،y1∨y2∨⋯∨yك⟩=موج الشعر بإستمرار⁡[⟨xأنا،yج⟩]أنا،ج=1ك{\displaystyle \langle x_{1}\vee x_{2}\vee \cdots \vee x_{k},y_{1}\vee y_{2}\vee \cdots \vee y_{k}\rangle =\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}} بتطبيق متباينة كوشي-شفارتز ، نجد أنموج الشعر بإستمرار⁡[⟨xأنا،xج⟩]أنا،ج=1ك≥0{\displaystyle \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\geq 0}وذلك |موج الشعر بإستمرار⁡[⟨xأنا،yج⟩]أنا،ج=1ك|2≤موج الشعر بإستمرار⁡[⟨xأنا،xج⟩]أنا،ج=1ك⋅موج الشعر بإستمرار⁡[⟨yأنا،yج⟩]أنا،ج=1ك{\displaystyle \left|\operatorname {perm} \left[\langle x_{i},y_{j}\rangle \right]_{i,j=1}^{k}\right|^{2}\leq \operatorname {perm} \left[\langle x_{i},x_{j}\rangle \right]_{i,j=1}^{k}\cdot \operatorname {perm} \left[\langle y_{i},y_{j}\rangle \right]_{i,j=1}^{k}}

أغطية الدراجات

أي مصفوفة مربعةأ=(أأناج)أنا،ج=1ن{\displaystyle A=(a_{ij})_{i,j=1}^{n}}يمكن اعتبارها مصفوفة تجاور لرسم بياني موجه مرجح على مجموعة الرؤوسV={1،2،...،ن}{\displaystyle V=\{1,2,\dots ,n\}}، معأأناج{\displaystyle a_{ij}}يمثل وزن القوس من الرأس i إلى الرأس j . غطاء الدورة في الرسم البياني الموجه الموزون هو مجموعة من الدورات الموجهة المنفصلة رأسيًا في الرسم البياني، والتي تغطي جميع رؤوس الرسم البياني. وبالتالي، لكل رأس i في الرسم البياني "خلف" فريد.σ(أنا){\displaystyle \sigma (i)}في غطاء الدراجة، وهكذاσ{\displaystyle \sigma }يمثل تبديلاً على V. وعلى العكس من ذلك، أي تبديلσ{\displaystyle \sigma }يمثل V غطاءً دوريًا بأقواس من كل رأس i إلى الرأسσ(أنا){\displaystyle \sigma (i)}.

إذا عُرِّف وزن غطاء الدراجة بأنه حاصل ضرب أوزان الأقواس في كل دورة، فإن وزن⁡(σ)=∏أنا=1نأأنا،σ(أنا)،{\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)},} مما يعني أن موج الشعر بإستمرار⁡(أ)=∑σوزن⁡(σ).{\displaystyle \operatorname {perm} (A)=\sum _{\sigma }\operatorname {weight} (\sigma ).} وبالتالي فإن العنصر الدائم لـ A يساوي مجموع أوزان جميع أغطية الدورات للرسم البياني الموجه.

تطابق مثالي

مصفوفة مربعةأ=(أأناج){\displaystyle A=(a_{ij})}يمكن أيضًا اعتبارها مصفوفة تجاور لرسم بياني ثنائي الأجزاء يحتوي على رؤوسx1،x2،...،xن{\displaystyle x_{1},x_{2},\dots ,x_{n}}من جانب واحد وy1،y2،...،yن{\displaystyle y_{1},y_{2},\dots ,y_{n}}على الجانب الآخر، معأأناج{\displaystyle a_{ij}}يمثل وزن الحافة من الرأسxأنا{\displaystyle x_{i}}إلى الرأسyج{\displaystyle y_{j}}إذا كان وزن التطابق التامσ{\displaystyle \sigma }هذا يطابقxأنا{\displaystyle x_{i}}لyσ(أنا){\displaystyle y_{\sigma (i)}}يُعرَّف بأنه حاصل ضرب أوزان الحواف في المطابقة، ثم وزن⁡(σ)=∏أنا=1نأأنا،σ(أنا).{\displaystyle \operatorname {weight} (\sigma )=\prod _{i=1}^{n}a_{i,\sigma (i)}.} وبالتالي فإن الثابت لـ A يساوي مجموع أوزان جميع المطابقات الكاملة للرسم البياني.

العناصر الدائمة للمصفوفات (0، 1)

تعداد

يمكن حساب إجابات العديد من أسئلة العد كثوابت للمصفوفات التي تحتوي فقط على 0 و 1 كمدخلات.

ليكن Ω( n , k ) فئة جميع المصفوفات (0, k) من الرتبة n التي يكون مجموع كل صف وعمود فيها مساويًا لـ k . كل مصفوفة A في هذه الفئة يكون لها perm( A ) > 0. [ 13 ] مصفوفات الوقوع لكل مستوى إسقاطي محدود تنتمي إلى الفئة Ω( n² + n + 1, n + 1) لعدد صحيح n > 1. تم حساب القيم الدائمة المقابلة لأصغر المستويات الإسقاطية. بالنسبة لـ n = 2 و3 و4 ، تكون القيم 24 و3852 و18534400 على التوالي. [ 13 ] ليكن Z مصفوفة الوقوع للمستوى الإسقاطي ذي n = 2، وهو مستوى فانو . والجدير بالذكر أن perm( Z ) = 24 = |det( Z )|، وهي القيمة المطلقة لمحدد Z. هذا نتيجة لكون Z مصفوفة دائرية ، وكذلك النظرية: [ 14 ]

إذا كانت A مصفوفة دائرية من الفئة Ω( n , k )، فإنه إذا كان k  >  3، فإن perm( A )  >  |det( A )|، وإذا كان k  =  3، فإن perm( A )  =  |det( A )| . علاوة على ذلك، عندما k  = 3، يمكن وضع A، عن  طريق تبديل الصفوف والأعمدة، على شكل مجموع مباشر لـ e نسخ من المصفوفة Z، وبالتالي، n = 7e و perm( A ) = 24e .    

يمكن أيضًا استخدام العناصر الدائمة لحساب عدد التباديل ذات المواضع المقيدة (الممنوعة). بالنسبة للمجموعة القياسية ذات n عنصر {1، 2، ...، n }، ليكنأ=(أأناج){\displaystyle A=(a_{ij})}لتكن A مصفوفة (0, 1) حيث a <sub> ij</sub> = 1 إذا كان الانتقال من i  إلى j مسموحًا به في التبديل، و a <sub>ij</sub> = 0 خلاف ذلك. عندئذٍ، يكون perm( A ) مساويًا لعدد تباديل المجموعة n التي تحقق جميع القيود. [ 9 ] من الحالات الخاصة المعروفة لهذا حل مسألة الترتيب غير المنتظم ومسألة الترتيب المختلط : يُعطى عدد تباديل مجموعة n التي لا تحتوي على نقاط ثابتة (ترتيبات غير منتظمة) بالعلاقة التالية: موج الشعر بإستمرار⁡(ج-أنا)=موج الشعر بإستمرار⁡(011...1101...1110...1⋮⋮⋮⋱⋮111...0)=ن!∑أنا=0ن(-1)أناأنا!،{\displaystyle \operatorname {perm} (J-I)=\operatorname {perm} \left({\begin{matrix}0&1&1&\dots &1\\1&0&1&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&1&1&\dots &0\end{matrix}}\right)=n!\sum _{i=0}^{n}{\frac {(-1)^{i}}{i!}},} حيث J هي مصفوفة n × n جميع عناصرها 1، و I هي مصفوفة الوحدة ، ويتم إعطاء أعداد الزوجية بواسطة موج الشعر بإستمرار⁡(ج-أنا-أنا′)=موج الشعر بإستمرار⁡(001...1100...1110...1⋮⋮⋮⋱⋮011...0)=∑ك=0ن(-1)ك2ن2ن-ك(2ن-كك)(ن-ك)!،{\displaystyle {\begin{aligned}\operatorname {perm} (J-I-I')&=\operatorname {perm} \left({\begin{matrix}0&0&1&\dots &1\\1&0&0&\dots &1\\1&1&0&\dots &1\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&1&1&\dots &0\end{matrix}}\right)\\&=\sum _{k=0}^{n}(-1)^{k}{\frac {2n}{2n-k}}{2n-k \choose k}(n-k)!,\end{aligned}}} حيث I' هي المصفوفة (0، 1) ذات المدخلات غير الصفرية في المواضع ( i ، i + 1) و ( n ، 1).

بالنسبة لمصفوفة من الرتبة n × n (0, 1)، يمكن وصف العنصر الدائم بشكل مكافئ بأنه عدد طرق وضع n من الرخ غير المهاجمة على رقعة الشطرنج من الرتبة n × n بحيث لا يوجد أي رخ في موضع يحتوي على عنصر صفري في المصفوفة. (تظهر هذه الأعداد في التوافقية كمعاملات رئيسية لكثيرات حدود الرخ .) [ 15 ]

الحدود

تُعطي متباينة بريغمان -مينك ، التي افترضها هـ. مينك عام 1963 [ 16 ] وأثبتها ل. م. بريغمان عام 1973 [ 17 ]، حدًا أعلى للثابت الدائم لمصفوفة من الرتبة n × n (0, 1). إذا كانت المصفوفة A تحتوي على r i من الواحدات في الصف i لكل 1 ≤ i ≤ n ، فإن المتباينة تنص على أن موج الشعر بإستمرار⁡أ≤∏أنا=1ن(رأنا)!1/رأنا.{\displaystyle \operatorname {perm} A\leq \prod _{i=1}^{n}(r_{i})!^{1/r_{i}}.}

تخمين فان دير فاردن

في عام 1926، افترض فان دير فاردن أن أصغر قيمة ثابتة بين جميع المصفوفات العشوائية المزدوجة من الرتبة n × n هي n ! / nn ، والتي تتحقق بواسطة المصفوفة التي تكون جميع عناصرها مساوية لـ 1/ n . [ 18 ] نُشرت براهين هذا الافتراض في عام 1980 بواسطة ب. جييريس [ 19 ] وفي عام 1981 بواسطة ج. ب. إيغوريتشيف [ 20 ] ود . إ. فاليكمان [ 21 ] . يُعد برهان إيغوريتشيف تطبيقًا لمتباينة ألكساندروف-فينشل . [ 22 ] فاز إيغوريتشيف وفاليكمان بجائزة فولكرسون عام 1982 عن هذا العمل. [ 23 ] 

حساب

إنّ الطريقة البسيطة، باستخدام التعريف، لحساب الثوابت غير مجدية حسابيًا حتى بالنسبة للمصفوفات الصغيرة نسبيًا. إحدى أسرع الخوارزميات المعروفة تعود إلى إتش جيه رايزر . [ 24 ] تعتمد طريقة رايزر على صيغة الإدراج والاستبعاد التي يمكن التعبير عنها [ 25 ] كما يلي: ليكنأك{\displaystyle A_{k}}يمكن الحصول على المصفوفة A عن طريق حذف k عمودًا، ولتكنP(أك){\displaystyle P(A_{k})}ليكن حاصل ضرب مجموع صفوفأك{\displaystyle A_{k}}ودعΣك{\displaystyle \Sigma _{k}}ليكن مجموع قيمP(أك){\displaystyle P(A_{k})}بشكل عام ممكنأك{\displaystyle A_{k}}. ثم موج الشعر بإستمرار⁡(أ)=∑ك=0ن-1(-1)كΣك.{\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{n-1}(-1)^{k}\Sigma _{k}.}

يمكن إعادة كتابتها بدلالة عناصر المصفوفة على النحو التالي: موج الشعر بإستمرار⁡(أ)=(-1)ن∑S⊆{1،...،ن}(-1)|S|∏أنا=1ن∑ج∈Sأأناج.{\displaystyle \operatorname {perm} (A)=(-1)^{n}\sum _{S\subseteq \{1,\dots ,n\}}(-1)^{|S|}\prod _{i=1}^{n}\sum _{j\in S}a_{ij}.}

يُعتقد أن حساب الثابت أصعب من حساب المحدد. فبينما يُمكن حساب المحدد في زمن متعدد الحدود باستخدام طريقة الحذف الغاوسي ، لا يُمكن استخدام هذه الطريقة لحساب الثابت. علاوة على ذلك، فإن حساب الثابت لمصفوفة (0,1) يُعد مسألة كاملة من فئة #P . وبالتالي، إذا أمكن حساب الثابت في زمن متعدد الحدود بأي طريقة، فإن FP  = #P  ، وهي عبارة أقوى من P  =  NP . مع ذلك، عندما تكون عناصر المصفوفة A غير سالبة، يُمكن حساب الثابت تقريبًا في زمن متعدد الحدود احتمالي ، مع هامش خطأ قدرهεم{\displaystyle \varepsilon M}، أينم{\displaystyle M}هي قيمة الدائم وε>0{\displaystyle \varepsilon >0}[ 26 ] يُعدّ تقريب المصفوفة الدائمة لمجموعة معينة من المصفوفات شبه الموجبة المحددة مسألةً صعبةً حسابيًا (NP-hard) ضمن أي عامل شبه أسي. [ 27 ] إذا فُرضت شروط إضافية على الطيف ، يُمكن تقريب المصفوفة الدائمة في وقت متعدد الحدود احتمالي: أفضل خطأ يُمكن تحقيقه لهذا التقريب هوεم{\displaystyle \varepsilon {\sqrt {M}}}(م{\displaystyle M}(وهي مرة أخرى قيمة الدائم). [ 28 ] ترتبط الصلابة في هذه الحالات ارتباطًا وثيقًا بصعوبة محاكاة تجارب أخذ عينات البوزونات .

نظرية ماكماهون الرئيسية

هناك طريقة أخرى لعرض المتغيرات الدائمة وهي من خلال الدوال المولدة متعددة المتغيرات . لنفترضأ=(أأناج){\displaystyle A=(a_{ij})}لتكن مصفوفة مربعة من الرتبة n . لنعتبر دالة التوليد متعددة المتغيرات: F(x1،x2،...،xن)=∏أنا=1ن(∑ج=1نأأناجxج)=(∑ج=1نأ1جxج)(∑ج=1نأ2جxج)⋯(∑ج=1نأنجxج).{\displaystyle {\begin{aligned}F(x_{1},x_{2},\dots ,x_{n})&=\prod _{i=1}^{n}\left(\sum _{j=1}^{n}a_{ij}x_{j}\right)\\&=\left(\sum _{j=1}^{n}a_{1j}x_{j}\right)\left(\sum _{j=1}^{n}a_{2j}x_{j}\right)\cdots \left(\sum _{j=1}^{n}a_{nj}x_{j}\right).\end{aligned}}} معاملx1x2...xن{\displaystyle x_{1}x_{2}\dots x_{n}}فيF(x1،x2،...،xن){\displaystyle F(x_{1},x_{2},\dots ,x_{n})}is perm( A ). [ 29 ]

كتعميم، لأي متتالية من n عدد صحيح غير سالب،s1،s2،...،sن{\displaystyle s_{1},s_{2},\dots ,s_{n}}يُعرِّف: موج الشعر بإستمرار(s1،s2،...،sن)⁡(أ){\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)}كمعامل لـx1s1x2s2⋯xنsن{\displaystyle x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}}في(∑ج=1نأ1جxج)s1(∑ج=1نأ2جxج)s2⋯(∑ج=1نأنجxج)sن.{\displaystyle \left(\sum _{j=1}^{n}a_{1j}x_{j}\right)^{s_{1}}\left(\sum _{j=1}^{n}a_{2j}x_{j}\right)^{s_{2}}\cdots \left(\sum _{j=1}^{n}a_{nj}x_{j}\right)^{s_{n}}.}

تنص نظرية ماكماهون الرئيسية التي تربط بين الثوابت والمحددات على ما يلي: [ 30 ]موج الشعر بإستمرار(s1،s2،...،sن)⁡(أ)= معامل x1s1x2s2⋯xنsن في 1المحقق(أنا-Xأ)،{\displaystyle \operatorname {perm} ^{(s_{1},s_{2},\dots ,s_{n})}(A)={\text{ coefficient of }}x_{1}^{s_{1}}x_{2}^{s_{2}}\cdots x_{n}^{s_{n}}{\text{ in }}{\frac {1}{\det(I-XA)}},} حيث I هي مصفوفة الوحدة من الرتبة n و X هي المصفوفة القطرية ذات القطر[x1،x2،...،xن].{\displaystyle [x_{1},x_{2},\dots ,x_{n}].}

المصفوفات المستطيلة

يمكن تعميم الدالة الدائمة لتشمل المصفوفات غير المربعة. في الواقع، يعتبر العديد من المؤلفين هذا تعريفًا للدالة الدائمة، ويعتبرون قصرها على المصفوفات المربعة حالة خاصة. [ 31 ] تحديدًا، بالنسبة لمصفوفة من الرتبة m  × n أ=(أأناج){\displaystyle A=(a_{ij})}مع m  ≤ n ، عرّف  موج الشعر بإستمرار⁡(أ)=∑σ∈P⁡(ن،م)أ1σ(1)أ2σ(2)...أمσ(م)،{\displaystyle \operatorname {perm} (A)=\sum _{\sigma \in \operatorname {P} (n,m)}a_{1\sigma (1)}a_{2\sigma (2)}\ldots a_{m\sigma (m)},} حيث P( n , m ) هي مجموعة جميع التباديل m للمجموعة n {1,2,...,n}. [ 32 ]

يمكن تعميم نتيجة رايزر الحسابية للمتغيرات الدائمة أيضًا. إذا كانت A مصفوفة من الرتبة m  × n حيث m ≤ n ، فلنفترض   أك{\displaystyle A_{k}}يمكن الحصول على المصفوفة A عن طريق حذف k عمودًا، ولتكنP(أك){\displaystyle P(A_{k})}ليكن حاصل ضرب مجموع صفوفأك{\displaystyle A_{k}}ودعσك{\displaystyle \sigma _{k}}ليكن مجموع قيمP(أك){\displaystyle P(A_{k})}بشكل عام ممكنأك{\displaystyle A_{k}}ثم [ 10 ]موج الشعر بإستمرار⁡(أ)=∑ك=0م-1(-1)ك(ن-م+كك)σن-م+ك.{\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{m-1}(-1)^{k}{\binom {n-m+k}{k}}\sigma _{n-m+k}.}

أنظمة الممثلين المتميزين

يُتيح تعميم تعريف المصفوفة الدائمة ليشمل المصفوفات غير المربعة استخدام المفهوم بطريقة أكثر طبيعية في بعض التطبيقات. على سبيل المثال:

لتكن S1 ، S2 ، ...، Sm مجموعات جزئية (ليست بالضرورة متميزة) من مجموعة n- ية حيث m ≤ n . مصفوفة الوقوع لهذه المجموعة من المجموعات الجزئية هي مصفوفة A من الرتبة m × n (0,1) . عدد أنظمة الممثلين المتميزين (SDR) لهذه المجموعة هو perm( A ). [ 33 ]    

انظر أيضاً

ملحوظات

  1. ↑ ماركوس، مارفن ؛ مينك، هنريك (1965). "الثوابت" . المجلة الأمريكية للرياضيات الشهرية . 72 (6): 577-591 . doi : 10.2307/2313846 . JSTOR 2313846. مؤرشف من الأصل في 2022-07-03 . تم الاسترجاع في 2022-08-15 . 
  2. ↑ مينك (1978)
  3. ↑ موير وميتزلر (1960)
  4. ^ كوشي، AL (1815)، “Mémoire sur les fonctions qui ne peuvent obtenir que deux valeurs égales et de Signes Contraires par suite des transpositions opérées entre lesvariables qu'elles renferment.” ، مجلة المدرسة المتعددة التقنيات ، 10 : 91 – 169
  5. ↑ موير وميتزلر (1960)
  6. ^ فان لينت وويلسون 2001 ، ص. 108
  7. ^ رايسر 1963 ، ص 25 – 26
  8. ↑ بيركوس 1971 ، ص. 2
  9. 1 2 بيركوس 1971 ، ص. 12
  10. 1 2 رايزر 1963 ، ص 26
  11. ↑ آرونسون، سكوت (14 نوفمبر 2010). "التعقيد الحسابي للبصريات الخطية". arXiv : 1011.3245 [ quant-ph ].
  12. ↑ بهاتيا، راجندرا (1997). تحليل المصفوفات . نيويورك: سبرينغر-فيرلاغ. ص 16-19 . ISBN  978-0-387-94846-1.
  13. 1 2 رايزر 1963 ، ص 124
  14. ↑ رايزر 1963 ، ص 125
  15. ↑ شيڤيليف، ڤي إس (1990). "حول تمثيل كثيرات حدود الرخ" . المسوحات الرياضية الروسية . 45 (4): 183-185 . Bibcode : 1990RuMaS..45..183S . doi : 10.1070/RM1990v045n04ABEH002387 .
  16. ↑ مينك، هنريك (1963)، "الحدود العليا للمتغيرات الدائمة للمصفوفات (0،1)"، نشرة الجمعية الرياضية الأمريكية ، 69 (6): 789-791 ، doi : 10.1090/s0002-9904-1963-11031-9
  17. ^ فان لينت وويلسون 2001 ، ص. 101
  18. ^ فان دير وايردن، بي إل (1926)، “أوفجابي 45”، جبر. الألمانية. الرياضيات-فيرين. ، 35 : 117.
  19. ^ Gyires، B. (1980)، “المصدر المشترك للعديد من عدم المساواة فيما يتعلق بالمصفوفات العشوائية المضاعفة”، منشورات Mathematicae Institutum Mathematicum Mathematicum Universitatis Debreceniensis ، 27 ( 3–4 ): 291–304 ، دوى : 10.5486/PMD.1980.27.3-4.15 ، MR 0604006 .
  20. ^ Egoryčev، GP (1980)، Reshenie مشكلة فان دير فاردينا dlya Permanentov (بالروسية)، كراسنويارسك: أكاد. ناوك SSSR سيبيرسك. أوتديل. انست. فيز، ص. 12، م.ر 0602332  إيغوريتشيف ، جي بي (1981)، "إثبات حدسية فان دير فاردن للمثبتات"، أكاديمية العلوم في الاتحاد السوفيتي (باللغة الروسية)، 22 (6): 65-71 ، 225، Bibcode : 1981SibMJ..22..854E ، doi : 10.1007/BF00968054 ، MR 0638007 إيغوريتشيف، جي بي (1981) ، "حل مسألة فان دير فاردن للمثبتات"، التقدم في الرياضيات ، 42 (3): 299-305 ، doi : 10.1016/0001-8708(81)90044-X ، MR 0642395 .
  21. ↑ فاليكمان، دي آي (1981)، "إثبات حدسية فان دير فاردن على الثابت لمصفوفة عشوائية مزدوجة"، أكاديمية العلوم في جمهورية روسيا الاتحادية الاشتراكية السوفيتية (باللغة الروسية)، 29 (6): 931-938 ، 957، MR 0625097 .
  22. ↑ بروالدي (2006) ص 487
  23. ↑ جائزة فولكرسون ، جمعية التحسين الرياضي، تم الاطلاع عليها بتاريخ 19-08-2012.
  24. ↑ رايزر (1963 ، ص 27)
  25. ^ فان لينت وويلسون (2001) ص. 99
  26. ↑ جيروم، م .؛ سنكلير، أ .؛ فيغودا، إ. (2004)، "خوارزمية تقريبية متعددة الحدود لحساب قيمة المصفوفة الدائمة ذات المدخلات غير السالبة"، مجلة ACM ، 51 (4): 671-697 ، CiteSeerX 10.1.1.18.9466 ، doi : 10.1145/1008731.1008738 ، S2CID 47361920  
  27. ↑ مايبورغ، ألكسندر (2023). "عدم إمكانية تقريب الثوابت شبه الموجبة المحددة والتصوير المقطعي لحالة الكم" . Algorithmica . 85 (12): 3828–3854 . arXiv : 2111.03142 . doi : 10.1007/s00453-023-01169-1 .
  28. ↑ تشاخماخشيان، ليفون؛ سيرف، نيكولاس؛ غارسيا-باترون، راؤول (2017). "خوارزمية مستوحاة من ميكانيكا الكم لتقدير الثابت للمصفوفات شبه الموجبة المحددة". مجلة Physical Review A ، 96 (2) 022329. arXiv : 1609.02416 . Bibcode : 2017PhRvA..96b2329C . doi : 10.1103/PhysRevA.96.022329 . S2CID 54194194 . 
  29. ↑ بيركوس 1971 ، ص 14
  30. ↑ بيركوس 1971 ، ص 17
  31. ↑ على وجه الخصوص، يفعل مينك (1978) ورايزر (1963) ذلك.
  32. ↑ رايزر 1963 ، ص 25
  33. ↑ رايزر 1963 ، ص 54

مراجع

  • بروالدي، ريتشارد أ. (2006). فئات المصفوفات التوافقية . موسوعة الرياضيات وتطبيقاتها. المجلد  108. كامبريدج: مطبعة جامعة كامبريدج . ISBN 978-0-521-86565-4. Zbl 1106.05001 . 
  • مينك، هنريك (1978). الثوابت . موسوعة الرياضيات وتطبيقاتها. المجلد  6. مع مقدمة بقلم مارفن ماركوس. ريدينغ، ماساتشوستس: أديسون-ويسلي. الرقم الدولي الموحد للدوريات 0953-4806 . رمز OCLC 3980645. رمز Zbl 0401.15005 .   
  • موير، توماس؛ ميتزلر، ويليام هـ. (1960) [1882]. رسالة في نظرية المحددات . نيويورك: دوفر. OCLC 535903 . 
  • بيركوس، جيه كيه (1971)، الأساليب التوافقية ، العلوم الرياضية التطبيقية #4، نيويورك: سبرينغر-فيرلاغ، ISBN 978-0-387-90027-8
  • رايزر، هربرت جون (1963)، الرياضيات التوافقية ، سلسلة كاروس للرياضيات رقم 14، الجمعية الرياضية الأمريكية
  • فان لينت، جيه إتش؛ ويلسون، آر إم (2001)، دورة في التوافقية ، مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-42260-4

للمزيد من القراءة

  • هول الابن، مارشال (1986)، نظرية التوافيق (  الطبعة الثانية)، نيويورك: جون وايلي وأولاده، الصفحات 56-72 ، رقم ISBN  978-0-471-09138-7يحتوي على دليل على حدسية Van der Waerden.
  • ماركوس، م.؛ مينك، هـ. (1965)، "الثوابت"، المجلة الرياضية الأمريكية الشهرية ، 72 (6): 577-591 ، doi : 10.2307/2313846 ، JSTOR 2313846