Лемма Стейница об обмене

Лемма Стейница о замене — это основная теорема линейной алгебры , используемая, например, для того, чтобы показать, что любые два базиса конечномерного векторного пространства имеют одинаковое количество элементов. Результат назван в честь немецкого математика Эрнста Стейница . Результат часто называют леммой об обмене Стейница – Мак Лейна , также признавая обобщение ^[1]автор: Сондерс Мак Лейн леммы Стейница к матроидам . ^[2]

Заявление

Позволять $U$ и $W$ быть конечными подмножествами векторного пространства $V$ . Если $U$ представляет собой набор линейно независимых векторов, а $W$ пролеты $V$ , затем:

1. $|U|\leq |W|$ ;

2. Есть набор $W'\subseteq W$ с $|W'|=|W|-|U|$ такой, что $U\cup W'$ пролеты $V$ .

Доказательство

Предполагать $U=\{u_{1},\dots ,u_{m}\}$ и $W=\{w_{1},\dots ,w_{n}\}$ . Мы хотим показать, что $m\leq n$ , и что после перестановки $w_{j}$ при необходимости набор $\{u_{1},\dotsc ,u_{m},w_{m+1},\dotsc ,w_{n}\}$ пролеты $V$ . Будем действовать индукцией по $m$ .

Для базового случая предположим $m$ равен нулю.В этом случае утверждение справедливо, поскольку нет векторов $u_{i}$ , и набор $\{w_{1},\dotsc ,w_{n}\}$ пролеты $V$ по гипотезе.

Для индуктивного шага предположим, что предложение верно для $m-1$ . По индуктивному предположению мы можем переупорядочить $w_{i}$ так что $\{u_{1},\ldots ,u_{m-1},w_{m},\ldots ,w_{n}\}$ пролеты $V$ . С $u_{m}\in V$ , существуют коэффициенты $\mu _{1},\ldots ,\mu _{n}$ такой, что

u_{m}=\sum _{i=1}^{m-1}\mu _{i}u_{i}+\sum _{j=m}^{n}\mu _{j}w_{j}

.

По крайней мере один из $\mu _{j}$ должно быть ненулевым, так как в противном случае это равенство противоречило бы линейной независимости $\{u_{1},\ldots ,u_{m}\}$ ; отсюда следует, что $m\leq n$ . Путем повторного заказа $\mu _{m}w_{m},\ldots ,\mu _{n}w_{n}$ при необходимости мы можем предположить, что $\mu _{m}$ ненулевое значение. Поэтому у нас есть

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)

.

Другими словами, $w_{m}$ находится в промежутке $\{u_{1},\ldots ,u_{m},w_{m+1},\ldots ,w_{n}\}$ . Поскольку этот интервал содержит каждый из векторов $u_{1},\ldots ,u_{m-1},w_{m},w_{m+1},\ldots ,w_{n}$ , по индуктивному предположению он содержит $V$ .

Приложения

Лемма Стейница об обмене — основной результат вычислительной математики , особенно линейной алгебры и комбинаторных алгоритмов . ^[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 .
^ Страница v в Boots: Штифель, Эдуард Л. (1963). Введение в числовую математику (перевод Вернера К. Райнбольдта и Корнели Дж. Райнбольдт из второго немецкого издания). Нью-Йорк: Академическая пресса. стр. х+286. МР 0181077 .

Хулио Р. Бастида, Расширение полей и теория Галуа , Издательство Аддисона – Уэсли (1984).

Внешние ссылки

системы Mizar Доказательство : http://mizar.org/version/current/html/vectsp_9.html#T19

[1] Мак Лейн, Сондерс (1936), «Некоторые интерпретации абстрактной линейной зависимости с точки зрения проективной геометрии», American Journal of Mathematics , 58 (1), The Johns Hopkins University Press: 236–240, doi : 10.2307/2371070 , JSTOR 2371070 .

[2] Кунг, Джозеф PS, изд. (1986), Справочник по теории матроидов , Бостон: Birkhäuser, doi : 10.1007/978-1-4684-9199-9 , ISBN 0-8176-3173-9 , МР 0890330 .

[3] Страница v в Boots: Штифель, Эдуард Л. (1963). Введение в числовую математику (перевод Вернера К. Райнбольдта и Корнели Дж. Райнбольдт из второго немецкого издания). Нью-Йорк: Академическая пресса. стр. х+286. МР 0181077 .

[1]

[2]

[3]