مبرهنة تبادل شتاينيتز

إن معضلة تبادل شتاينتز هي نظرية أساسية في الجبر الخطي تستخدم، على سبيل المثال، لإظهار أن أي قاعدتين لمساحة متجهية محدودة الأبعاد لهما نفس عدد العناصر. تم تسمية النتيجة على اسم عالم الرياضيات الألماني إرنست شتاينتز . غالبًا ما تسمى النتيجة معضلة تبادل شتاينتز-ماك لين ، مع الاعتراف أيضًا بالتعميم ^[1] بواسطة سوندرز ماك لين لمعضلة شتاينتز على الماترويدات . ^[2]

ليكن و مجموعات جزئية منتهية من فضاء متجه . إذا كانت مجموعة متجهات مستقلة خطيًا ، و تمتد ، فإن: ${\displaystyle U}$${\displaystyle W}$${\displaystyle V}$${\displaystyle U}$${\displaystyle W}$ ${\displaystyle V}$

1. ؛ ${\displaystyle |U|\leq |W|}$

2. هناك مجموعة بها مثل هذه التي تمتد على . ${\displaystyle W'\subseteq W}$${\displaystyle |W'|=|W|-|U|}$${\displaystyle U\cup W'}$${\displaystyle V}$

افترض و . نريد أن نبين أن و أنه بعد إعادة ترتيب إذا لزم الأمر، فإن المجموعة تمتد على . نستمر بالاستدلال على . ${\displaystyle U=\{u_{1},\dots ,u_{m}\}}$${\displaystyle W=\{w_{1},\dots ,w_{n}\}}$${\displaystyle m\leq n}$${\displaystyle w_{j}}$${\displaystyle \{u_{1},\dotsc ,u_{m},w_{m+1},\dotsc ,w_{n}\}}$${\displaystyle V}$${\displaystyle م}$

بالنسبة للحالة الأساسية، افترض أن تساوي صفرًا. في هذه الحالة، ينطبق الادعاء لأنه لا توجد متجهات ، وتمتد المجموعة حسب الفرضية. ${\displaystyle م}$${\displaystyle u_{i}}$${\displaystyle \{w_{1},\dotsc ,w_{n}\}}$${\displaystyle V}$

بالنسبة للخطوة الاستقرائية، افترض أن الاقتراح صحيح بالنسبة لـ . وباستخدام الفرضية الاستقرائية، يمكننا إعادة ترتيب بحيث تمتد إلى . نظرًا لأن ، توجد معاملات بحيث ${\displaystyle m-1}$${\displaystyle w_{i}}$${\displaystyle \{u_{1},\ldots ,u_{m-1},w_{m},\ldots ,w_{n}\}}$${\displaystyle V}$${\displaystyle u_{m}\in V}$${\displaystyle \mu _{1},\ldots ,\mu _{n}}$

${\displaystyle u_{m}=\sum _{i=1}^{m-1}\mu _{i}u_{i}+\sum _{j=m}^{n}\mu _{j }ث_{ي}}$.

يجب أن يكون واحد على الأقل من غير صفر، وإلا فإن هذه المساواة ستتناقض مع الاستقلال الخطي لـ ؛ ويترتب على ذلك أن . من خلال إعادة الترتيب إذا لزم الأمر، يمكننا افتراض أن غير صفري. لذلك، لدينا ${\displaystyle \mu _{j}}$${\displaystyle \{u_{1},\ldots ,u_{m}\}}$${\displaystyle m\leq n}$${\displaystyle \mu _{m}w_{m},\ldots ,\mu _{n}w_{n}}$${\displaystyle \mu _{m}}$

${\displaystyle w_{m}={\frac {1}{\mu _{m}}}\left(u_{m}-\sum _{j=1}^{m-1}\mu _{j}u_{j}-\sum _{j=m+1}^{n}\mu _{j}w_{j}\right)}$.

بمعنى آخر، يقع في مدى . وبما أن هذا المدى يحتوي على كل من المتجهات ، فإنه يحتوي على . وفقًا للفرضية الاستقرائية.${\displaystyle w_{m}}$${\displaystyle \{u_{1},\ldots ,u_{m},w_{m+1},\ldots ,w_{n}\}}$${\displaystyle u_{1},\ldots ,u_{m-1},w_{m},w_{m+1},\ldots ,w_{n}}$${\displaystyle V}$

تعتبر معضلة تبادل شتاينتز نتيجة أساسية في الرياضيات الحسابية ، وخاصة في الجبر الخطي وفي الخوارزميات التوافقية . ^[3]

• جوليو ر. باستيدا، امتدادات المجال ونظرية جالوا ، شركة أديسون ويسلي للنشر (1984).

• إثبات نظام الميزار : http://mizar.org/version/current/html/vectsp_9.html#T19