تبديل سايدل: أي طيف يبقى ثابتًا؟

الخلاصة السريعة

الثابت هو طيف مصفوفة سايدل. في مثالنا ينتقل المسار AB BC CD DE إلى AD AE CE DE عند اختيار {A,C}. يحتفظ الرسمان بكثيرة حدود سايدل نفسها، لكن كثيرتي حدود التجاور تختلفان؛ لذلك لا ننقل ثبات الطيف إلى أي مصفوفة تمثل الرسم.

• تبديل سايدل يقلب وجود الحواف بين مجموعة مختارة ومجموعة الرؤوس الباقية، ويترك الحواف داخل كل مجموعة كما هي. اختيار المجموعة المكملة يعطي النتيجة نفسها، والتبديل نفسه مرتين يعيد الرسم. [1] نعمل على رسوم بسيطة غير موجهة بلا حلقات أو أوزان، مع تثبيت أسماء الرؤوس.
• من الأزواج العابرة نحذف AB وBC وCD، ونضيف AD وAE وCE. تبقى DE لأنها داخل المجموعة الباقية. كلا الرسمين له أربع حواف، لكن B يصبح معزولًا ويظهر المثلث ADE.
• مصفوفة سايدل تضع صفرًا على القطر، و−1 للحافة، و+1 لغيابها خارج القطر؛ وتكتب S=J−I−2M. تغيير الإشارات بمصفوفة قطرية D ذات قيم ±1 يعطي S′=DSD ويحفظ طيف S. [2] هنا J كلها واحدات وI مصفوفة الوحدة؛ الإشارات ترميز للتجاور، وليست أوزان حواف سالبة.
• نختار D=diag(−1,1,−1,1,1) بترتيب A B C D E. بما أن D²=I، فإن det(tI−DSD)=det(tI−S). هذه حجة عامة منفصلة عن الحصر العددي.
• كثيرة حدود سايدل في المثال t⁵−10t³+4t²+17t−12. كثيرة حدود التجاور قبل التبديل t⁵−4t³+3t، وبعده t⁵−4t³−2t²+t. تساوي عدد الحواف لا يساوي تساوي الطيف.
• قلب الحواف العابرة يختلف عن متمم الرسم الذي يقلب كل الأزواج المسموحة. اختيار جميع الرؤوس هنا لا يغير أي حافة؛ ولا يحذف الرأس المعزول من قائمة الأسماء.
• فحصنا 64 رسمًا على أربعة رؤوس مع 16 اختيارًا للمجموعة، أي 1024 حالة. ثبتت كثيرة حدود سايدل في كلها؛ تغيرت كثيرة حدود التجاور في 752 وعدد المكونات في 464. الأعداد تخص هذا الحصر فقط.

نقلب ما يعبر بين المجموعتين

تبديل سايدل يقلب وجود الحواف بين مجموعة مختارة ومجموعة الرؤوس الباقية، ويترك الحواف داخل كل مجموعة كما هي. اختيار المجموعة المكملة يعطي النتيجة نفسها، والتبديل نفسه مرتين يعيد الرسم. [1]

نثبت الأسماء A B C D E، ونبدأ بالمسار ذي الحواف AB وBC وCD وDE. الحافة تصل اسمين مختلفين بلا اتجاه أو تكرار؛ AB وBA وصلة واحدة. لا تدخل AA ضمن الأزواج الممكنة.

المجموعة المختارة U={A,C}، والباقية {B,D,E}. للزوج ثلاثة مواضع ممكنة: داخل U، أو داخل الباقية، أو عابر بينهما. الموضع الثالث وحده يخضع للقلب. لا نقلب الحافة لأن خطها يمر فوق حدود مرسومة في الصورة؛ نحكم من أسماء طرفيها.

الأزواج العابرة هي AB وAD وAE وBC وCD وCE. في المسار توجد AB وBC وCD فنحذفها. وتغيب AD وAE وCE فنضيفها. أما AC وBD وBE وDE فليست عابرة؛ تبقى حالتها الأصلية.

نحصل على AD وAE وCE وDE. أربع حواف قبل العملية وأربع بعدها في هذا المثال، لأننا حذفنا ثلاثًا وأضفنا ثلاثًا. هذا توازن لقائمتنا المحددة، ولا نفترض أنه حاصل لكل اختيار في كل رسم.

مصفوفة التجاور ومصفوفة الإشارات

مصفوفة سايدل تضع صفرًا على القطر، و−1 للحافة، و+1 لغيابها خارج القطر؛ وتكتب S=J−I−2M. تغيير الإشارات بمصفوفة قطرية D ذات قيم ±1 يعطي S′=DSD ويحفظ طيف S. [2]

نسمي مصفوفة التجاور M، ونثبت ترتيب الصفوف والأعمدة A B C D E. الخانة خارج القطر تساوي1 للحافة و0 لغيابها. صف A قبل التبديل هو (0,1,0,0,0)، وبعده (0,0,0,1,1).

في مصفوفة سايدل S، يصبح صف A قبل العملية (0,−1,1,1,1)، وبعدها (0,1,1,−1,−1). خانة AC لم تتغير لأن الطرفين داخل U. خانة AB تغيرت من−1 إلى+1 لأننا حذفنا الحافة، وAD من+1 إلى−1 لأننا أضفناها.

الإشارة السالبة تعني وجود حافة في هذا الترميز، لكنها لا تحول الرسم إلى شبكة ذات أوزان سالبة. ليست S مصفوفة التجاور M، وليست مصفوفة لابلاس. حين نقول إن طيفًا بقي ثابتًا يجب أن نذكر المصفوفة التي حسبناه منها.

J في الصيغة جدول جميع خاناته1، وI لها1 على القطر فقط. على القطر نحسب1−1−0=0. وخارجه نحسب1−2 عندما تكون الحافة موجودة، و1 عندما تغيب. هكذا نراجع الترميز خانة خانة بدل اعتبار الرموز متشابهة.

لماذا يحفظ تغيير الإشارات هذه المصفوفة؟

في مثالنا نضع D=diag(−1,1,−1,1,1). العنصر القطري−1 يخص A وC المختارين، والعنصر+1 يخص B وD وE. الرمز D هنا اسم مصفوفة؛ حين نقول «الرأس D» نقصد الاسم الرابع في القائمة.

الخانة i,j من DSD تساوي di×Sij×dj. عندما يكون الطرفان داخل المجموعة نفسها تتساوى إشارتاهما ويكون حاصل ضربهما+1. وعندما يكون أحدهما مختارًا والآخر خارجها يكون الحاصل−1، فتنعكس الخانة غير القطرية.

على القطر يبقى الصفر صفرًا. إذن ضرب المصفوفة من الجهتين يطابق قلب الأزواج العابرة، ولا يعيد تسمية الرؤوس أو ينقل خانة إلى موقع آخر. راجعنا هذه المساواة في الخانات الخمس والعشرين للمثال.

كل عنصر قطري من D هو+1 أو−1، لذلك D²=I وD⁻¹=D. نكتب tI−DSD=D(tI−S)D. بأخذ المحدد يظهر العامل det(D)²=1، فيبقى det(tI−S) نفسه.

هذه الحجة تفسر ثبات كثيرة الحدود المميزة ثم جذورها مع تكراراتها. لا تحتاج أن يكون الرسم متصلًا أو منتظم الدرجات. لكنها تطبق هنا على S وفق الترميز المحدد؛ لا تستبدل S تلقائيًا بمصفوفة التجاور M في المساواة.

كثيرة ثابتة وأخرى تتغير

في المسار الأصلي كثيرة حدود التجاور هي pM(t)=t⁵−4t³+3t. وبعد التبديل تصبح pM′(t)=t⁵−4t³−2t²+t. المعامل−2 عند t² في الثانية يكفي لإثبات اختلاف كثيرتي الحدود.

أما كثيرة حدود سايدل في الرسمين فهي pS(t)=t⁵−10t³+4t²+17t−12. قارنا جميع المعاملات الصحيحة، بما فيها معامل t⁴ الصفري. لا نعتمد على تقريب قيم ذاتية قد يخفي اختلافًا صغيرًا.

تساوي كثيرتي الحدود يعني تساوي الجذور مع تعددها. وفي مثالنا اختلاف كثيرتي حدود التجاور ينفي تساوي طيفيهما الكاملين. ليس المطلوب كتابة صيغ جذرية طويلة لكل قيمة لكي نثبت هذا الفرق.

يمكن رؤية تغير في البنية قبل الحساب الجبري. المسار متصل ودرجاته (1,2,2,2,1). الرسم الجديد درجاته (2,0,1,2,3)، ومكوناه {A,C,D,E} و{B}. يوجد المثلث ADE، ويتصل C بـE فقط.

مع ذلك لم يتغير عدد الحواف: ما زال أربعًا. الاتفاق في هذا العدد وفي عدد الرؤوس لا يفرض الاتفاق في معاملات أخرى. كذلك تغير الاتصال لا يناقض ثبات طيف سايدل؛ المثال يبين أن هذا الطيف وحده لا يحفظ الاتصال تحت العملية.

الرجوع والقلب الشامل سؤالان مختلفان

إذا كررنا التبديل على U نفسها، انعكس وجود كل زوج عابر مرة ثانية فعاد إلى بدايته. وبقيت الأزواج الداخلية ثابتة في المرحلتين. نستعيد AB وBC وCD وDE، ويعود B إلى المسار.

اختيار الباقية {B,D,E} بدل {A,C} يقسم الأسماء إلى المجموعتين نفسيهما مع تبديل جهتيهما؛ لذلك يعطي الناتج نفسه. وعلى مستوى الإشارات تصبح المصفوفة القطرية−D، لكن (−D)S(−D)=DSD.

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

متمم الرسم، في المقابل، يقلب كل زوج مسموح بين اسمين مختلفين، بما فيه الأزواج الداخلية. لهذا لا نستبدل تبديل سايدل بأخذ المتمم. في مثالنا تبقى DE موجودة بعد التبديل، لكنها تختفي من المتمم.

نحتفظ بالأسماء الخمسة في كل مرحلة. عزل B لا يحذفه من المصفوفة، ولا يحول الرسم الجديد إلى مدخل بأربعة رؤوس. حذف صفه وعموده يغير المصفوفة وحجم كثيرة الحدود، فيصبح سؤالًا آخر.

ما الذي غطاه الحصر المحدود؟

أربعة رؤوس ثابتة تتيح ست حواف بسيطة ممكنة، أي 2⁶=64 قائمة حواف. ولكل قائمة 2⁴=16 مجموعة مختارة من الرؤوس. فحصنا الأزواج المرتبة بين المدخل والاختيار، فكان العدد64×16=1024.

في كل حالة بنينا مصفوفتي التجاور وسايدل قبل القلب وبعده. قارنا الخانات بمساواة الإشارات، وراجعنا العودة عند تكرار الاختيار، وتطابق الناتج عند اختيار المجموعة المكملة. لم نحذف حالات متشابهة بإعادة أسماء الرؤوس.

حسبنا كثيرة الحدود بطريقتين: توسع المحدد عبر تبديلات الأعمدة، وعلاقات نيوتن باستخدام آثار القوى وحساب صحيح. تطابقت الطريقتان لكل المصفوفات المفحوصة. ثم وجدنا كثيرة حدود سايدل ثابتة في1024 حالة.

تغيرت كثيرة حدود التجاور في752 حالة، وتغير عدد المكونات في464. لا ندعي أن هذين العددين متساويان أو أن إحدى الفئتين تحتوي الأخرى؛ فحصنا كل شرط وحده. ولا نحولهما إلى احتمال لشبكة واقعية.

المثال الرئيس ذو خمسة رؤوس، والحصر الإضافي ذو أربعة. راجعنا كثيرات المثال بالطريقتين أيضًا؛ لا نزعم حصر جميع الرسوم ذات الخمسة رؤوس واختياراتها. البرهان العام للمصفوفة القطرية منفصل عن عدد الحالات المحدود.

عند إعادة الفحص، اكتب قائمة الحواف والتقسيم أولًا، ثم حدد ترميز المصفوفة. افحص الأزواج العابرة والقطر، واحسب كثيرة الحدود في ترتيب واحد. السؤال الصحيح هو أي طيف بقي ثابتًا، ثم ما الذي نستطيع استنتاجه عن الرسم من ذلك الثبات.