Лемма Стейница об обмене
Лемма Стейница о замене — это основная теорема линейной алгебры , используемая, например, для того, чтобы показать, что любые два конечномерного векторного базиса пространства имеют одинаковое количество элементов. Результат назван в честь немецкого математика Эрнста Стейница . Результат часто называют леммой об обмене Стейница – Мак Лейна , также признавая обобщение [1] автор: Сондерс Мак Лейн леммы Стейница к матроидам . [2]
Заявление [ править ]
Позволять и быть конечными подмножествами векторного пространства . Если представляет собой набор линейно независимых векторов, а пролеты , затем:
1. ;
2. Есть набор с такой, что пролеты .
Доказательство [ править ]
Предполагать и . Мы хотим показать, что , и что после перестановки при необходимости набор пролеты . Будем действовать индукцией по .
Для базового случая предположим равен нулю. В этом случае утверждение справедливо, поскольку нет векторов , и набор пролеты по гипотезе.
Для индуктивного шага предположим, что предложение верно для . По индуктивному предположению мы можем переупорядочить так что пролеты . С , существуют коэффициенты такой, что
- .
По крайней мере один из должно быть ненулевым, так как в противном случае это равенство противоречило бы линейной независимости ; следует, что . Путем повторного заказа при необходимости мы можем предположить, что ненулевое значение. Поэтому у нас есть
- .
Другими словами, находится в промежутке . Поскольку этот интервал содержит каждый из векторов , по индуктивному предположению он содержит .
Приложения [ править ]
Лемма Стейница об обмене — основной результат вычислительной математики , особенно линейной алгебры и комбинаторных алгоритмов . [3]
Ссылки [ править ]
- ^ Мак Лейн, Сондерс (1936), «Некоторые интерпретации абстрактной линейной зависимости с точки зрения проективной геометрии», American Journal of Mathematics , 58 (1), The Johns Hopkins University Press: 236–240, doi : 10.2307/2371070 , JSTOR 2371070 .
- ^ Кунг, Джозеф PS, изд. (1986), Справочник по теории матроидов , Бостон: Birkhäuser, doi : 10.1007/978-1-4684-9199-9 , ISBN 0-8176-3173-9 , МР 0890330 .
- ^ Page v in Stiefel: Штифель, Эдуард Л. (1963). Введение в числовую математику (перевод Вернера К. Райнбольдта и Корнели Дж. Райнбольдт из второго немецкого издания). Нью-Йорк: Академическая пресса. стр. х+286. МР 0181077 .
- Хулио Р. Бастида, Расширение полей и теория Галуа , Издательство Addison – Wesley (1984).