معضلة تبادل شتاينيتز

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

يمكن استخدامها، على سبيل المثال، لإثبات أن أي قاعدتين لفضاء متجهي محدود الأبعاد لهما نفس عدد العناصر. سُميت هذه النتيجة نسبةً إلى عالم الرياضيات الألماني ^إرنست شتاينيتز . وتُعرف هذه النتيجة غالبًا باسم " ^{مُبرهنة} التبادل لشتاينيتز-ماك لين ^" ،  ^{مع الإشارة أيضًا إلى} تعميم ساوندرز ماك لين لمُبرهنة شتاينيتز على الماترويدات .

يترك${\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 m}$.

بالنسبة للحالة الأساسية، لنفترض${\displaystyle m}$يساوي صفرًا. في هذه الحالة، يكون الادعاء صحيحًا لأنه لا توجد متجهات.${\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}w_{j}}$.

واحد على الأقل من${\displaystyle \mu _{j}}$ل${\displaystyle j\geq m}$يجب أن تكون القيمة غير صفرية، وإلا فإن هذه المساواة ستتعارض مع الاستقلال الخطي لـ${\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