Штейниц обмен леммой является основной теоремой в линейной алгебре используется, например, чтобы показать , что любые две основ для конеч мерного векторного пространства имеют одинаковое число элементов. Результат назван в честь немецкого математика Эрнста Стейница . В результате часто называют Стейница-Маклейна обмена леммой , признавая также обобщение [1] по Маклейн леммы Стейница к матроидам . [2]
Заявление
Если это набор линейно независимые векторы в векторном пространстве, а также охватывать , тогда:
1. ;
2. Есть набор с участием такой, что пролеты .
Доказательство
Предположим, что у нас есть указанные наборы векторов. Мы хотим показать, что для каждогоу нас есть это , и что множество пролеты (где возможно, были переупорядочены, и это зависит от ). Действуем индукцией по.
Для базового случая предположим равно нулю. В этом случае утверждение верно, потому что нет векторов, а множество пролеты по гипотезе.
Что касается индуктивного шага, предположим, что предложение верно для некоторого . С, а также пролеты (по предположению индукции) существуют коэффициенты такой, что
- .
По крайней мере, один из должно быть ненулевым, так как в противном случае это равенство противоречило бы линейной независимости ; обратите внимание, что это дополнительно означает, что. Путем переупорядочивания, можно считать, что не равно нулю. Следовательно, мы имеем
- .
Другими словами, находится в промежутке . Таким образом, последний промежуток содержит каждый из векторов, и, следовательно, должен содержать промежуток этих последних векторов как подмножество. Но поскольку последний промежуток (по предположению индукции) это просто означает, что промежуток содержит как подмножество (таким образом ). Таким образом, мы показали, что наше утверждение верно в отношении, завершая индуктивный шаг.
Таким образом, мы показали, что для каждого у нас есть это , и что множество пролеты (где возможно, были переупорядочены, и это зависит от ).
Дело в том, что следует из постановки в этом результате.
Приложения
Лемма об обмене Стейница является основным результатом вычислительной математики , особенно линейной алгебры и комбинаторных алгоритмов . [3]
Рекомендации
- ^ Маклейн, Saunders (1936), "Некоторые интерпретации абстрактной линейной зависимости с точки зрения проективной геометрии", Американский журнал математики , The Johns Hopkins University Press, 58 (1): 236-240, DOI : 10,2307 / 2371070 , JSTOR 2371070 .
- ^ Кунг, Джозеф П.С., изд. (1986), Справочник по теории матроидов , Бостон: Birkhäuser, DOI : 10.1007 / 978-1-4684-9199-9 , ISBN 0-8176-3173-9, Руководство по ремонту 0890330.
- ^ Страница v в Штифеле: Штифель, Эдуард Л. (1963). Введение в числовую математику (Перевод Вернера К. Райнбольдта и Корнели Дж. Райнбольдт из второго немецкого изд.). Нью-Йорк: Academic Press. С. x + 286. Руководство по ремонту 0181077 .
- Хулио Р. Бастида, Расширения поля и теория Галуа , издательство Addison-Wesley Publishing Company (1984).
Внешние ссылки
- Подтверждение системы Mizar : http://mizar.org/version/current/html/vectsp_9.html#T19