مصفوفة عشوائية مزدوجة

في الرياضيات ، وخاصة في الاحتمالات والتوافقية ، المصفوفة العشوائية المزدوجة ( وتسمى أيضًا المصفوفة ثنائية العشوائية ) هي مصفوفة مربعة${\displaystyle X=(x_{ij})}$من الأعداد الحقيقية غير السالبة ، التي يكون مجموع كل صف وعمود فيها يساوي 1، أي

${\displaystyle \sum _{i}x_{ij}=\sum _{j}x_{ij}=1,}$

وبالتالي، فإن المصفوفة العشوائية المزدوجة هي مصفوفة عشوائية من اليسار ومصفوفة عشوائية من اليمين. ^{[ 1 ]}

في الواقع، أي مصفوفة عشوائية من اليسار واليمين يجب أن تكون مربعة : إذا كان مجموع كل صف يساوي 1، فإن مجموع جميع المدخلات في المصفوفة يجب أن يساوي عدد الصفوف، وبما أن الأمر نفسه ينطبق على الأعمدة، فإن عدد الصفوف والأعمدة يجب أن يكون متساوياً.

فئة${\displaystyle n\times n}$المصفوفات العشوائية المزدوجة هي متعدد سطوح محدب يُعرف باسم متعدد سطوح بيركوف.${\displaystyle B_{n}}$باستخدام عناصر المصفوفة كإحداثيات ديكارتية ، فإنها تقع في${\displaystyle (n-1)^{2}}$الفضاء الأفيني ذو الأبعاد n من${\displaystyle n^{2}}$الفضاء الإقليدي ذو الأبعاد n المعرّف بواسطة${\displaystyle 2n-1}$قيود خطية مستقلة تحدد أن مجموع الصفوف والأعمدة يساوي 1. (يوجد${\displaystyle 2n-1}$القيود بدلاً من${\displaystyle 2n}$لأن أحد هذه القيود تابع، حيث يجب أن يساوي مجموع مجاميع الصفوف مجموع مجاميع الأعمدة.) علاوة على ذلك، فإن جميع المدخلات مقيدة بأن تكون غير سالبة وأقل من أو تساوي 1.

تنص نظرية بيركوف-فون نيومان (المعروفة غالبًا باسم نظرية بيركوف ^{[ 2 ] [ 3 ] [ 4 ]} ) على أن متعدد السطوح${\displaystyle B_{n}}$هو الغلاف المحدب لمجموعة${\displaystyle n\times n}$مصفوفات التبديل ، وعلاوة على ذلك فإن رؤوس${\displaystyle B_{n}}$هي تحديدًا مصفوفات التبديل. بعبارة أخرى، إذا${\displaystyle X}$إذا كانت مصفوفة عشوائية مزدوجة، فإنه يوجد${\displaystyle \theta _{1},\ldots ,\theta _{k}\geq 0,\sum _{i=1}^{k}\theta _{i}=1}$ومصفوفات التبديل${\displaystyle P_{1},\ldots ,P_{k}}$بحيث

${\displaystyle X=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.}$

(يُعرف هذا التفكيك لـ X باسم "التركيبة المحدبة"). يرد أدناه برهان النظرية المستندة إلى نظرية هول للزواج .

يُعرف هذا التمثيل بتحليل بيركوف-فون نيومان ، وقد لا يكون فريدًا. غالبًا ما يُوصف بأنه تعميم حقيقي لنظرية كونيغ ، حيث يتم إثبات التطابق من خلال مصفوفات التجاور للرسوم البيانية. كما تُستخدم نظرية بيركوف-فون نيومان في البرمجة الخطية الصحيحة . ^{[ 5 ]}

• حاصل ضرب مصفوفتين عشوائيتين مزدوجتين هو مصفوفة عشوائية مزدوجة. ومع ذلك، فإن معكوس مصفوفة عشوائية مزدوجة غير منفردة ليس بالضرورة أن يكون عشوائيًا مزدوجًا (في الواقع، يكون المعكوس عشوائيًا مزدوجًا إذا كانت عناصره غير سالبة).
• يكون التوزيع الثابت لسلسلة ماركوف المحدودة غير الدورية غير القابلة للاختزال منتظمًا إذا وفقط إذا كانت مصفوفة الانتقال الخاصة بها عشوائية مزدوجة.
• تنص نظرية سينكهورن على أنه يمكن جعل أي مصفوفة ذات مدخلات موجبة تمامًا عشوائية مزدوجة عن طريق الضرب المسبق واللاحق بالمصفوفات القطرية .
• ل${\displaystyle n=2}$جميع المصفوفات ثنائية الاحتمالية هي أحادية الاحتمالية ومتعامدة الاحتمالية ، ولكن بالنسبة للمصفوفات الأكبر${\displaystyle n}$هذا ليس هو الحال.
• تخمين فان دير فاردن بأن الحد الأدنى للقيمة الدائمة بين جميع المصفوفات العشوائية المزدوجة من الرتبة n × n هو${\displaystyle n!/n^{n}}$، ويتحقق ذلك من خلال المصفوفة التي تكون جميع عناصرها متساوية${\displaystyle 1/n}$[ ^{6 ]} نُشرت براهين هذه الفرضية في عام 1980 بواسطة ب. جيريس ^{[ 7 ]} وفي عام 1981 بواسطة ج. ب. إيغوريتشيف ^{[ 8 ]} ود. إ. فاليكمان؛ ^{[ 9 ] عن} هذا العمل، فاز إيغوريتشيف وفاليكمان بجائزة فولكرسون في عام 1982. ^{[ 10 ]}

لتكن X مصفوفة احتمالية مزدوجة. سنُبين أنه توجد مصفوفة تبديل P بحيث يكون x _{_ij} ≠ 0 كلما كان p _{_ij} ≠ 0. بالتالي، إذا اعتبرنا λ أصغر قيمة لـ x_{_ij} تُقابل قيمة غير صفرية لـ p_{_ij}، فإن الفرق X – λP سيكون مضاعفًا قياسيًا لمصفوفة احتمالية مزدوجة، وسيحتوي على خلية صفرية واحدة على الأقل أكثر من X. بناءً على ذلك ، يُمكننا تقليل عدد الخلايا غير الصفرية في X تدريجيًا عن طريق إزالة مضاعفات قياسية لمصفوفات التبديل حتى نصل إلى مصفوفة الصفر، وعندها نكون قد أنشأنا توليفة محدبة من مصفوفات التبديل تُساوي X الأصلية . ^{[ 2 ]}      

على سبيل المثال إذا${\displaystyle X={\frac {1}{12}}{\begin{pmatrix}7&0&5\\2&6&4\\3&6&3\end{pmatrix}}}$ثم ${\displaystyle P={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}}$،${\displaystyle \lambda ={\frac {2}{12}}}$، و ${\displaystyle X-\lambda P={\frac {1}{12}}{\begin{pmatrix}7&0&3\\0&6&4\\3&4&3\end{pmatrix}}}$.

البرهان: أنشئ رسمًا بيانيًا ثنائي الأجزاء حيث تُدرج صفوف المصفوفة X في جزء والأعمدة في الجزء الآخر، ويكون الصف i متصلًا بالعمود j إذا وفقط إذا كان x _ij ≠ 0.  ${\displaystyle A}$ليكن أي مجموعة من الصفوف، وعرّف${\displaystyle A'}$كما هو الحال مع مجموعة الأعمدة المتصلة بالصفوف في A في الرسم البياني. نريد التعبير عن الأحجام${\displaystyle |A|}$و${\displaystyle |A'|}$من المجموعتين بدلالة x _ij .

لكل عنصر i في A ، يكون مجموع x _ij على j في A' يساوي 1، لأن جميع الأعمدة j التي يكون فيها x _ij ≠ 0 موجودة في A ' ، و X متغير عشوائي مزدوج؛ ومن ثم  ${\displaystyle |A|}$هو المجموع على جميع i  ∈ A ، j ∈ A ' لـ x _ij .   

في أثناء${\displaystyle |A'|}$هو مجموع x _ij على جميع i (سواءً كانت في A أم لا ) وجميع j في A ' ؛ وهذا المجموع أكبر من أو يساوي المجموع المقابل الذي تقتصر فيه i على صفوف في A. ${\displaystyle |A'|\geq |A|}$.

يترتب على ذلك أن شروط نظرية هول للزواج مُحققة، وبالتالي يمكننا إيجاد مجموعة من الحواف في الرسم البياني تربط كل صف في X بعمود واحد (مختلف) فقط. تُحدد هذه الحواف مصفوفة تبديل، حيث تتوافق خلاياها غير الصفرية مع خلايا غير صفرية في X.

• المصفوفة العشوائية
• مصفوفة أحادية العشوائية
• خوارزمية بيركوف

• بروالدي، ريتشارد أ. (2006). فئات المصفوفات التوافقية . موسوعة الرياضيات وتطبيقاتها. المجلد  108. كامبريدج: مطبعة جامعة كامبريدج . ISBN 978-0-521-86565-4. Zbl 1106.05001 . 

• صفحة PlanetMath حول نظرية بيركوف-فون نيومان
• صفحة PlanetMath حول برهان نظرية بيركوف-فون نيومان