مصفوفة التبديل

في الرياضيات ، وتحديدًا في نظرية المصفوفات ، مصفوفة التبديل هي مصفوفة ثنائية مربعة تحتوي على عنصر واحد فقط قيمته 1 في كل صف وكل عمود، وباقي العناصر قيمتها 0. ^{[ 1 ] : 26} يمكن لمصفوفة تبديل من الرتبة n × n أن تمثل تبديلًا لـ n عنصرًا. بضرب مصفوفة M ذات n صف من اليسار بمصفوفة التبديل P ، لتكوين PM ، ينتج تبديل صفوف M ، بينما بضرب مصفوفة M ذات n عمود من اليمين ، لتكوين MP ، ينتج تبديل أعمدة M.

كل مصفوفة تبديل P متعامدة ، ومعكوسها يساوي منقولها :${\displaystyle P^{-1}=P^{\mathsf {T}}}$^{[ 1 ] : 26} في الواقع ، يمكن وصف مصفوفات التبديل بأنها المصفوفات المتعامدة التي تكون جميع عناصرها غير سالبة . ^{[ 2 ]}

توجد علاقتان طبيعيتان متناظرتان بين التباديل ومصفوفات التباديل، إحداهما تعمل على طول صفوف المصفوفة، والأخرى على طول أعمدتها. إليك مثال، بدءًا من التبديل π في شكل سطرين في أعلى اليسار:

${\displaystyle {\begin{matrix}\pi \colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &R_{\pi }\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]C_{\pi }\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\pi ^{-1}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

تُجري عملية التناظر القائمة على الصفوف التبديل π على المصفوفة${\displaystyle R_{\pi }}$في أعلى اليمين. الصف الأول من${\displaystyle R_{\pi }}$يحتوي على الرقم 1 في العمود الثالث لأن${\displaystyle \pi (1)=3}$وبشكل أعم، لدينا${\displaystyle R_{\pi }=(r_{ij})}$أين${\displaystyle r_{ij}=1}$متى${\displaystyle j=\pi (i)}$و${\displaystyle r_{ij}=0}$خلاف ذلك.

تُحوّل عملية التناظر القائمة على الأعمدة قيمة π إلى المصفوفة${\displaystyle C_{\pi }}$في أسفل اليسار. العمود الأول من${\displaystyle C_{\pi }}$يحتوي على الرقم 1 في الصف الثالث لأن${\displaystyle \pi (1)=3}$وبشكل أعم، لدينا${\displaystyle C_{\pi }=(c_{ij})}$أين${\displaystyle c_{ij}}$يساوي 1 عندما${\displaystyle i=\pi (j)}$وصفر فيما عدا ذلك. بما أن الوصفتين تختلفان فقط بتبديل i مع j ، فإن المصفوفة${\displaystyle C_{\pi }}$هو منقول${\displaystyle R_{\pi }}$و، بما أن${\displaystyle R_{\pi }}$لدينا مصفوفة تبديل${\displaystyle C_{\pi }=R_{\pi }^{\mathsf {T}}=R_{\pi }^{-1}}$بتتبع الجانبين الآخرين للمربع الكبير، نحصل على${\displaystyle R_{\pi ^{-1}}=C_{\pi }=R_{\pi }^{-1}}$و${\displaystyle C_{\pi ^{-1}}=R_{\pi }}$[ ^{3 ]​}

ضرب المصفوفة M إما${\displaystyle R_{\pi }}$أو${\displaystyle C_{\pi }}$سيؤدي استخدام أي من الخيارين على اليسار أو اليمين إلى تبديل صفوف أو أعمدة المصفوفة M بمقدار π أو π ⁻¹ . التفاصيل معقدة بعض الشيء.

بدايةً، عندما نقوم بتبديل عناصر متجه${\displaystyle (v_{1},\ldots ,v_{n})}$عن طريق تبديل ما π ، ننقل${\displaystyle i^{\text{th}}}$دخول${\displaystyle v_{i}}$من متجه الإدخال إلى${\displaystyle \pi (i)^{\text{th}}}$خانة من متجه الإخراج. أي عنصر ينتهي به المطاف، على سبيل المثال، في الخانة الأولى من الإخراج؟ الإجابة: العنصر${\displaystyle v_{j}}$والتي${\displaystyle \pi (j)=1}$وبالتالي${\displaystyle j=\pi ^{-1}(1)}$وباتباع نفس المنطق فيما يتعلق بكل خانة، نجد أن متجه الإخراج هو

${\displaystyle {\big (}v_{\pi ^{-1}(1)},v_{\pi ^{-1}(2)},\ldots ,v_{\pi ^{-1}(n)}{\big )},}$

على الرغم من أننا نقوم بالتبديل بواسطة${\displaystyle \pi }$ليس عن طريق${\displaystyle \pi ^{-1}}$وبالتالي، من أجل تبديل المدخلات بواسطة${\displaystyle \pi }$، يجب علينا تبديل المؤشرات بواسطة${\displaystyle \pi ^{-1}}$[ ^{1 ] : 25 (} تبديل المدخلات بواسطة${\displaystyle \pi }$يُطلق عليه أحيانًا اسم اتخاذ وجهة نظر الذريعة ، مع تبديل المؤشرات بواسطة${\displaystyle \pi }$سيتخذ وجهة نظر الاسم المستعار . ^{[ 4 ]} )

لنفترض الآن أننا نضرب من اليسار مصفوفة مكونة من n صف${\displaystyle M=(m_{i,j})}$بواسطة مصفوفة التبديل${\displaystyle C_{\pi }}$بحسب قاعدة ضرب المصفوفات ، فإن${\displaystyle (i,j)^{\text{th}}}$إدخال في المنتج${\displaystyle C_{\pi }M}$يكون

$${\displaystyle \sum _{k=1}^{n}c_{i,k}m_{k,j},}$$

أين${\displaystyle c_{i,k}}$يساوي صفرًا إلا عندما${\displaystyle i=\pi (k)}$، عندما يكون 1. وبالتالي، فإن الحد الوحيد الذي يبقى في المجموع هو الحد الذي فيه${\displaystyle k=\pi ^{-1}(i)}$ويختزل المجموع إلى${\displaystyle m_{\pi ^{-1}(i),j}}$بما أننا قمنا بتبديل فهرس الصف بواسطة${\displaystyle \pi ^{-1}}$، لقد قمنا بتبديل صفوف المصفوفة M نفسها بمقدار π . ^{[ 1 ] : 25} تُظهر حجة مماثلة أن ضرب مصفوفة M ذات n عمودًا من الخلف بـ${\displaystyle R_{\pi }}$يقوم بتبديل أعمدته بمقدار π .

الخياران الآخران هما الضرب المسبق بـ${\displaystyle R_{\pi }}$أو الضرب اللاحق بـ${\displaystyle C_{\pi }}$وتقوم هذه العمليات بتبديل الصفوف أو الأعمدة على التوالي بمقدار π ⁻¹ ، بدلاً من π .

تُثبت حجةٌ ذات صلة، كما ذكرنا سابقًا، أن منقولة أي مصفوفة تبديل P تعمل أيضًا كمعكوس لها، مما يعني أن P قابلة للعكس. (يترك آرتين هذا البرهان كتمرين، ^{[ 1 ] : 26،} والذي نحله هنا). إذا${\displaystyle P=(p_{i,j})}$ثم الـ${\displaystyle (i,j)^{\text{th}}}$دخول منقوله${\displaystyle P^{\mathsf {T}}}$يكون${\displaystyle p_{j,i}}$. ال${\displaystyle (i,j)^{\text{th}}}$إدخال المنتج${\displaystyle PP^{\mathsf {T}}}$ثم

$${\displaystyle \sum _{k=1}^{n}p_{i,k}p_{j,k}.}$$

حينما${\displaystyle i\neq j}$، ال${\displaystyle k^{\text{th}}}$الحد الموجود في هذا المجموع هو ناتج ضرب عنصرين مختلفين في${\displaystyle k^{\text{th}}}$عمود من P ؛ لذا فإن جميع الحدود تساوي صفرًا، والمجموع يساوي صفرًا. عندما${\displaystyle i=j}$نقوم بجمع مربعات القيم في${\displaystyle i^{\text{th}}}$صف من P ، لذا فإن المجموع يساوي 1. حاصل الضرب${\displaystyle PP^{\mathsf {T}}}$وبالتالي، فإنّ مصفوفة الوحدة هي مصفوفة الوحدة. وتُظهر حجة متناظرة الشيء نفسه بالنسبة لـ${\displaystyle P^{\mathsf {T}}P}$مما يعني أن P قابلة للعكس مع${\displaystyle P^{-1}=P^{\mathsf {T}}}$.

بفرض وجود تبديلين لعناصر n، هما 𝜎 و 𝜏 ، فإن حاصل ضرب مصفوفات التبديل العمودية المناظرة C _σ و C _τ يُعطى، ^{[ 1 ] : 25} كما هو متوقع، بواسطة $${\displaystyle C_{\sigma }C_{\tau }=C_{\sigma \,\circ \,\tau },}$$ حيث التبديل المركب${\displaystyle \sigma \circ \tau }$يتم تطبيق 𝜏 أولاً ثم 𝜎 ، بالعمل من اليمين إلى اليسار: $${\displaystyle (\sigma \circ \tau )(k)=\sigma \left(\tau (k)\right).}$$ ويعود ذلك إلى أن ضرب مصفوفة ما من اليسار بـ _Cτ ثم ضرب الناتج من اليسار بـ _Cσ يعطي نفس نتيجة الضرب من اليسار مرة واحدة فقط بالمصفوفة المركبة${\displaystyle C_{\sigma \,\circ \,\tau }}$.

بالنسبة للمصفوفات الصفية، هناك اختلاف بسيط: يُعطى حاصل _ضرب Rσ و Rτ بالصيغة _{التالية}

${\displaystyle R_{\sigma }R_{\tau }=R_{\tau \,\circ \,\sigma },}$

مع تطبيق 𝜎 قبل 𝜏 في التبديل المركب. يحدث هذا لأنه يجب علينا الضرب من الخلف لتجنب الانعكاسات في الخيار القائم على الصفوف، لذلك سنضرب من الخلف أولاً بـ R _σ ثم بـ R _τ .

عند تطبيق دالة على وسيط، يكتب بعض الأشخاص الدالة بعد الوسيط ( ترميز لاحق )، بدلاً من كتابتها قبله. في الجبر الخطي، يتعاملون مع فضاءات خطية من متجهات الصفوف، ويطبقون تحويلاً خطياً على وسيط باستخدام مصفوفة التحويل لضرب متجه صف الوسيط من اليمين. غالباً ما يستخدمون عامل التركيب من اليسار إلى اليمين، والذي نرمز إليه هنا باستخدام فاصلة منقوطة؛ لذا فإن التركيب${\displaystyle \sigma \,;\,\tau }$يتم تعريفها إما بواسطة

${\displaystyle (\sigma \,;\,\tau )(k)=\tau \left(\sigma (k)\right),}$

أو، بشكل أكثر أناقة، عن طريق

${\displaystyle (k)(\sigma \,;\,\tau )=\left((k)\sigma \right)\tau ,}$

بتطبيق 𝜎 أولاً. هذه الصيغة تعطينا قاعدة أبسط لضرب مصفوفات التبديل القائمة على الصفوف:

${\displaystyle R_{\sigma }R_{\tau }=R_{\sigma \,;\,\tau }.}$

عندما يكون π هو التبديل المحايد، والذي له${\displaystyle \pi (i)=i}$لكل i ، فإن كل من C _π و R _π هما مصفوفة الوحدة .

يوجد n ! مصفوفة تبديل، لأن هناك n ! تبديلًا والخريطة${\displaystyle C\colon \pi \mapsto C_{\pi }}$هي علاقة تناظرية بين التباديل ومصفوفات التباديل. (الخريطة)${\displaystyle R}$(وهذا مثال آخر على هذا النوع من المراسلات). وفقًا للصيغ المذكورة أعلاه، تُشكّل مصفوفات التبديل من الرتبة n × n زمرة من الرتبة n ! تحت عملية ضرب المصفوفات، حيث تكون مصفوفة الوحدة هي عنصرها المحايد ، وهي زمرة نرمز لها بـ${\displaystyle {\mathcal {P}}_{n}}$المجموعة${\displaystyle {\mathcal {P}}_{n}}$هي مجموعة فرعية من المجموعة الخطية العامة${\displaystyle \operatorname {GL} _{n}(\mathbb {R} )}$من المصفوفات القابلة للعكس من الرتبة n × n للأعداد الحقيقية. في الواقع، لأي حقل F ، فإن المجموعة ${\displaystyle {\mathcal {P}}_{n}}$وهي أيضًا مجموعة فرعية من المجموعة${\displaystyle \operatorname {GL} _{n}(F)}$حيث تنتمي عناصر المصفوفة إلى F. (يحتوي كل حقل على 0 و1 مع${\displaystyle 0+0=0,}$${\displaystyle 0+1=1,}$${\displaystyle 0*0=0,}$${\displaystyle 0*1=0,}$و${\displaystyle 1*1=1;}$وهذا كل ما نحتاجه لضرب مصفوفات التبديل. تختلف الآراء في مختلف المجالات حول ما إذا كان${\displaystyle 1+1=0}$لكن هذا المجموع لا يتحقق.

يترك${\displaystyle S_{n}^{\leftarrow }}$يرمز إلى المجموعة المتناظرة ، أو مجموعة التبديلات ، على {1،2،...، ن } حيث تكون عملية المجموعة هي التركيب القياسي من اليمين إلى اليسار.${\displaystyle \circ }$"؛ ولتكن${\displaystyle S_{n}^{\rightarrow }}$يشير إلى المجموعة المقابلة ، والتي تستخدم التركيب من اليسار إلى اليمين.${\displaystyle \,;\,}$"الخريطة${\displaystyle C\colon S_{n}^{\leftarrow }\to \operatorname {GL} _{n}(\mathbb {R} )}$ذلك يأخذ π إلى مصفوفة عمودية${\displaystyle C_{\pi }}$هو تمثيل أمين ، وكذلك بالنسبة للخريطة${\displaystyle R\colon S_{n}^{\rightarrow }\to \operatorname {GL} _{n}(\mathbb {R} )}$هذا يأخذ π إلى${\displaystyle R_{\pi }}$.

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

وكما أن كل تبديل مرتبط بمصفوفتي تبديل، فإن كل مصفوفة تبديل مرتبطة بتبديلين، كما يمكننا أن نرى من خلال إعادة تسمية المثال في المربع الكبير أعلاه بدءًا من المصفوفة P في أعلى اليمين:

${\displaystyle {\begin{matrix}\rho _{P}\colon {\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}}&\longleftrightarrow &P\colon {\begin{pmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}\\[5pt]{\Big \updownarrow }&&{\Big \updownarrow }\\[5pt]P^{-1}\colon {\begin{pmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{pmatrix}}&\longleftrightarrow &\kappa _{P}\colon {\begin{pmatrix}1&2&3&4\\4&2&1&3\end{pmatrix}}\end{matrix}}}$

إذن، نحن هنا نرمز إلى معكوس C بـ${\displaystyle \kappa }$ومعكوس R هو${\displaystyle \rho }$يمكننا بعد ذلك حساب الخصائص الجبرية الخطية لـ P من بعض الخصائص التوافقية المشتركة بين التبديلين${\displaystyle \kappa _{P}}$و${\displaystyle \rho _{P}=\kappa _{P}^{-1}}$.

يتم تحديد نقطة بواسطة${\displaystyle \kappa _{P}}$بمجرد إصلاحها بواسطة${\displaystyle \rho _{P}}$وأثر P هو عدد هذه النقاط الثابتة المشتركة. ^{[ 1 ] : 322 إذا} كان العدد الصحيح ^k أحد هذه النقاط، فإن ^متجه _الأساس القياسي ek هو متجه ذاتي لـ P. [ ¹ ] : ¹¹⁸

لحساب القيم الذاتية المركبة لـ P ، اكتب التبديل${\displaystyle \kappa _{P}}$على سبيل المثال، كتركيبة من دورات منفصلة${\displaystyle \kappa _{P}=c_{1}c_{2}\cdots c_{t}}$(تتبادل تباديل المجموعات الجزئية المنفصلة، ​​لذا لا يهم هنا ما إذا كنا نركب من اليمين إلى اليسار أو من اليسار إلى اليمين.)${\displaystyle 1\leq i\leq t}$لنفترض أن طول الدورة${\displaystyle c_{i}}$يكون${\displaystyle \ell _{i}}$ودع${\displaystyle L_{i}}$لتكن مجموعة الحلول المعقدة لـ${\displaystyle x^{\ell _{i}}=1}$وهذه الحلول هي${\displaystyle \ell _{i}^{\,{\text{th}}}}$جذور الوحدة . اتحاد المجموعات المتعددة لـ${\displaystyle L_{i}}$إذن، هي مجموعة القيم الذاتية المتعددة لـ P. منذ كتابة${\displaystyle \rho _{P}}$بتحليلها، فإن ناتج الدورات سيعطي نفس عدد الدورات بنفس الأطوال.${\displaystyle \rho _{p}}$سيؤدي ذلك إلى نفس النتيجة. تعددية أي قيمة ذاتية v هي عدد قيم i التي${\displaystyle L_{i}}$يحتوي على v . ^{[ 6 ]} (بما أن أي مصفوفة تبديل هي مصفوفة طبيعية وأي مصفوفة طبيعية قابلة للتقطير على الأعداد المركبة، ^{[ 1 ] : 259} فإن التعدد الجبري والهندسي للقيمة الذاتية v متماثلان.)

من نظرية الزمر، نعلم أن أي تبديل يمكن كتابته كتركيب لمصفوفات تبديل . لذلك، فإن أي مصفوفة تبديل تُحلل إلى حاصل ضرب مصفوفات أولية تبديل الصفوف ، كل منها محددها يساوي -1 . وبالتالي، فإن محدد مصفوفة التبديل P هو إشارة التبديل.${\displaystyle \kappa _{P}}$وهو أيضاً علامة على${\displaystyle \rho _{P}}$.

• مصفوفة كوستاس ، وهي مصفوفة تبديل تكون فيها متجهات الإزاحة بين المدخلات جميعها متميزة
• لغز الملكات n ، وهو عبارة عن مصفوفة تبديل تحتوي على عنصر واحد على الأكثر في كل قطر وقطر فرعي.

• مصفوفة الإشارات المتناوبة
• مصفوفة التبادل
• مصفوفة التبديل المعممة
• متعددة حدود الرخ
• دائم
• مخطط كايلي – مخطط مُنشأ من مجموعة تكون مصفوفة التجاور الخاصة بها عبارة عن مجموع مصفوفات التبديل.