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

редактировать

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

Содержание

1 Утверждение
2 Доказательство
3 Приложения
4 Ссылки
5 Внешние ссылки

Заявление

Если ${v 1,…, vm} {\ displaystyle \ {v_ { 1}, \ dots, v_ {m} \}}$ ${\ displaystyle \ {v_ {1}, \ dots, v_ {m} \}}$ - это набор $m {\ displaystyle m}$ $m$ линейно независимых векторов в векторном пространстве $V { \ displaystyle V}$ $V$ и ${w 1,…, wn} {\ displaystyle \ {w_ {1}, \ dots, w_ {n} \}}$ ${\ displaystyle \ {w_ {1}, \ dots, w_ {n} \}}$ span $V {\ displaystyle V}$ $V$ , затем:

1. $m ≤ n {\ displaystyle m \ leq n}$ $m \ leq n$ ;

2. Набор ${v 1,…, vm, wm + 1,…, wn} {\ displaystyle \ {v_ {1}, \ dots, v_ {m}, w_ {m + 1}, \ dots, w_ {n} \}}$ ${\ displaystyle \ {v_ {1}, \ dots, v_ {m}, w_ {m + 1}, \ dots, w_ {n} \}}$ охватывает $V {\ displaystyle V}$ $V$ , возможно, после изменения порядка $wi {\ displaystyle w_ {i}}$ $w_ {i}$ .

Proof

Предположим, что у нас есть указанные наборы векторов. Мы хотим показать, что для каждого $k ∈ {0,…, m} {\ displaystyle k \ in \ {0, \ dots, m \}}$ ${\ displaystyle k \ in \ {0, \ dots, m \}}$ мы имеем $k ≤ n {\ displaystyle k \ leq n}$ $k \ leq n$ , и что набор ${v 1,…, vk, wk + 1,…, wn} {\ displaystyle \ {v_ {1}, \ dotsc, v_ {k}, w_ {k + 1}, \ dotsc, w_ {n} \}}$ ${\ displaystyle \ {v_ {1}, \ dotsc, v_ {k}, w_ {k + 1}, \ dotsc, w_ {n} \}}$ spans $V {\ displaystyle V}$ $V$ (где $wj {\ displaystyle w_ {j}}$ $w_ {j}$ , возможно, был переупорядочен, и переупорядочение зависит от $k {\ displaystyle k}$ $k$ ). Мы продолжаем математической индукцией на $k {\ displaystyle k}$ $k$ .

Для базового случая предположим, что $k {\ displaystyle k}$ $k$ равно нулю. В этом случае утверждение выполняется, потому что нет векторов $vi {\ displaystyle v_ {i}}$ $v_ {i}$ и набора ${w 1,…, wn} {\ displaystyle \ { w_ {1}, \ dotsc, w_ {n} \}}$ ${\ displaystyle \ {w_ {1}, \ dotsc, w_ {n} \}}$ охватывает $V {\ displaystyle V}$ $V$ по гипотезе.

Для индуктивного шага предположим, что утверждение верно для некоторого $k < m {\displaystyle k$ ${\ displaystyle k <m}$ . Поскольку $vk + 1 ∈ V {\ displaystyle v_ {k + 1} \ in V}$ $v _ {{k + 1}} \ in V$ и ${v 1,…, vk, wk + 1,…, wn} { \ displaystyle \ {v_ {1}, \ ldots, v_ {k}, w_ {k + 1}, \ ldots, w_ {n} \}}$ $\ {v_ {1}, \ ldots, v_ {k}, w _ {{k + 1}}, \ ldots, w_ {n} \}$ охватывает $V {\ displaystyle V}$ $V$ (по предположению индукции) существуют коэффициенты $μ 1,…, μ n {\ displaystyle \ mu _ {1}, \ ldots, \ mu _ {n}}$ $\ mu _ {1}, \ ldots, \ mu _ {n}$ такое, что

vk + 1 = ∑ j = 1 k μ jvj + ∑ j = k + 1 n μ jwj {\ displaystyle v_ {k + 1} = \ sum _ {j = 1} ^ {k} \ mu _ {j} v_ {j} + \ sum _ {j = k + 1} ^ {n} \ mu _ {j} w_ {j}}

{\ displaystyle v_ {k + 1} = \ sum _ {j = 1} ^ {k} \ mu _ {j} v_ {j} + \ sum _ {j = k + 1} ^ {n} \ mu _ {j} w_ {j }}

Хотя бы один из ${μ k + 1,…, μ n} {\ displaystyle \ {\ mu _ {k + 1}, \ ldots, \ mu _ {n} \}}$ $\ {\ mu _ {{k + 1}}, \ ldots, \ mu _ {n} \}$ должно быть ненулевым, поскольку в противном случае это равенство противоречат линейной независимости ${v 1,…, vk + 1} {\ displaystyle \ {v_ {1}, \ ldots, v_ {k + 1} \}}$ ${\ displaystyle \ {v_ {1}, \ ldots, v_ {k + 1} \}}$ ; обратите внимание, что это дополнительно подразумевает, что $k + 1 ≤ n {\ displaystyle k + 1 \ leq n}$ ${\ displaystyle k + 1 \ leq n}$ . Переупорядочив $μ k + 1 wk + 1,…, μ nwn {\ displaystyle \ mu _ {k + 1} w_ {k + 1}, \ ldots, \ mu _ {n} w_ {n}}$ ${\ displaystyle \ mu _ { к + 1} w_ {к + 1}, \ ldots, \ mu _ {n} w_ {n}}$ , мы можем предположить, что $μ k + 1 {\ displaystyle \ mu _ {k + 1}}$ $\ mu _ {{k + 1}}$ не равно нулю. Следовательно, мы имеем

wk + 1 = 1 μ k + 1 (vk + 1 - ∑ j = 1 k μ jvj - ∑ j = k + 2 n μ jwj) {\ displaystyle w_ {k + 1} = { \ frac {1} {\ mu _ {k + 1}}} \ left (v_ {k + 1} - \ sum _ {j = 1} ^ {k} \ mu _ {j} v_ {j} - \ sum _ {j = k + 2} ^ {n} \ mu _ {j} w_ {j} \ right)}

w _ {{k + 1}} = {\ frac {1} {\ mu _ {{k + 1}}}} \ left (v _ {{ k + 1}} - \ sum _ {{j = 1}} ^ {k} \ mu _ {j} v_ {j} - \ sum _ {{j = k + 2}} ^ {n} \ mu _ {j} w_ {j} \ right)

Другими словами, $wk + 1 {\ displaystyle w_ {k + 1}}$ $w_ {k + 1}$ находится в диапазоне ${v 1,…, vk + 1, wk + 2,…, wn} {\ displaystyle \ {v_ {1}, \ ldots, v_ {k + 1 }, w_ {k + 2}, \ ldots, w_ {n} \}}$ $\ {v_ {1}, \ ldots, v _ {{k + 1}}, w _ {{k + 2}}, \ ldots, w_ {n} \}$ . Последний диапазон, следовательно, содержит каждый из векторов $v 1,…, vk, wk + 1, wk + 2,…, wn {\ displaystyle v_ {1}, \ ldots, v_ {k}, w_ {k + 1}, w_ {k + 2}, \ ldots, w_ {n}}$ ${\ displaystyle v_ {1}, \ ldots, v_ {k}, w_ {k + 1}, w_ {k + 2}, \ ldots, w_ {n}}$ , и, следовательно, должен содержать диапазон этих последних векторов как подмножество. Но поскольку последний промежуток равен $V {\ displaystyle V}$ $V$ (по предположению индукции), это просто означает, что промежуток ${v 1,…, vk + 1, wk + 2,…, wn} {\ displaystyle \ {v_ {1}, \ ldots, v_ {k + 1}, w_ {k + 2}, \ ldots, w_ {n} \}}$ $\ {v_ {1}, \ ldots, v _ {{k + 1}}, w _ {{k + 2}}, \ ldots, w_ {n} \}$ содержит $V {\ displaystyle V}$ $V$ как подмножество (таким образом, это $V {\ displaystyle V}$ $V$ ). Таким образом, мы показали, что наше утверждение верно для $k + 1 {\ displaystyle k + 1}$ $k + 1$ , завершив индуктивный шаг.

Таким образом, мы показали, что для каждого $k ∈ {0,…, m} {\ displaystyle k \ in \ {0, \ dots, m \}}$ ${\ displaystyle k \ in \ {0, \ dots, m \}}$ мы иметь, что $k ≤ n {\ displaystyle k \ leq n}$ $k \ leq n$ и что набор ${v 1,…, vk, wk + 1,…, wn} {\ displaystyle \ {v_ {1}, \ dotsc, v_ {k}, w_ {k + 1}, \ dotsc, w_ {n} \}}$ ${\ displaystyle \ {v_ {1}, \ dotsc, v_ {k}, w_ {k + 1}, \ dotsc, w_ {n} \}}$ охватывает $V {\ displaystyle V}$ $V$ (где $wj {\ displaystyle w_ {j}}$ $w_ {j}$ , возможно, были переупорядочены, и переупорядочение зависит от $k {\ displaystyle k}$ $k$ ).

Тот факт, что $m ≤ n {\ displaystyle m \ leq n}$ ${\ displaystyle m \ leq n}$ следует из установки $k = m {\ displaystyle k = m}$ ${\ displaystyle k = m}$ в этом результат.

Приложения

Лемма об обмене Стейница является основным результатом в вычислительной математике, особенно в линейной алгебре и в комбинаторных алгоритмах.

Ссылки

^Mac Lane, Saunders (1936), «Некоторые интерпретации абстрактной линейной зависимости в терминах проективной геометрии», American Journal of Mathematics, The Johns Hopkins University Press, 58 (1): 236–240, doi : 10.2307 / 2371070, JSTOR 2371070 CS1 maint: несколько имен: список авторов ( ссылка ).
^Кунг, Джозеф П. С., изд. (1986), A Source Book in Matroid Theory, Boston: Birkhäuser, doi : 10.1007 / 978-1-4684-9199-9, ISBN 0-8176-3173-9, MR 0890330.
^Страница v в Штифеле: Штифель, Эдуард Л. (1963). Введение в численную математику (Перевод Вернера К. Райнбольдта и Корнели Дж. Райнбольдт из второго немецкого изд.). Нью-Йорк: Academic Press. С. x + 286. MR 0181077.

Хулио Р. Бастида, Расширения полей и теория Галуа, издательство Addison – Wesley Publishing Company (1984).

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

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