Лекции по линейной алгебре (стр. 4 )

  Очевидно, tij-1 = tij, tij2 = tij.

  Утверждение. Любую подстановку σ ∈ Sn, п ≥ 2, можно разложить в композицию  транспозиций.

  Доказательство по индукции.

1. При п =2 утверждение очевидно, так как  S2  состоит из двух элементов:  id и  tij.

2.  Пусть для п – 1 утверждение верно. Рассмотрим σ ∈ Sn. Пусть σ(п) = q, и  σ1 = tqnσ.  Тогда  σ1 (n) = n, и  σ1 – биекция множества  {1, 2, 3, …, n -1 } из (п-1)-го элемента. По предположению индукции можно считать, что для σ1  утверждение верно, то есть σ1=τ1τ2…τr  - композиция транспозиций. Но σ = tqn-1σ1 = tqnσ1 = tqnτ1τ2…τr  - композиция транспозиций.

  Очевидно, разложение подстановки в композицию транспозиций неоднозначно.

  На практике очень легко раскладывать подстановку в произведение транспозиций, если она задана в циклической записи. Так, например, легко проверить, что

(1, 3, 7, 2, 4)(5, 6)(8) = t13 t37 t72 t24 t56 .

  Будем говорить, что в последовательности чисел i1, i2 ,..,in  два числа  ik и  il  образуют инверсию, если ik > il, но ik  расположено левее il. Подстановка σ = называется четной, если количество инверсий в её нижней строке

че­тно, и  σ  называется нечетной, если количество инверсий в

её нижней строке нечетно. 

  Утверждение. Если количество инверсий в нижней строке подстановки σ  равно m, то σ  можно разложить в произведение m  транспозиций.

  Доказательство. Пусть два соседних элемента ik и  ik+1  в нижней строке подстановки σ образуют инверсию. Тогда 

σ1=σ =, и число инверсий в нижней строке у σ1  равно m – 1.  Продолжая эту процедуру далее, получим, что существуют транспозиции τ1 ,τ2 , …,τm такие, что  подстановка τmτm-1…τ1σ  не имеет инверсий в нижней строке, то есть τmτm-1…τ1σ  = id.  Умножая последнее равенство слева на τm, затем на τm-1  и так далее до τ1 , и учитывая, что все τi2= id, получим, что  σ = τ1τ2…τm. 

Лекция 4.

  3.3. Отношение эквивалентности.

  Определения.

  1. Отношение R на множестве Х называется рефлексивным, если xRx  ∀ x∈ Х.

  2. Отношение R на множестве Х называется симметричным, если для x, у ∈ Х  из xRy следует yRx.

  3. Отношение R на множестве Х называется транзитивным, если для x, у, z ∈ Х  из xRy и  yRz  следует  xRz.

  4.  Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и тран­зи­тивно.

  Упражнения.

1. Доказать, что отношение R на множестве Х рефлексивно

⇔ R ⊇ ΔX.

2. Доказать, что отношение R – симметрично ⇔ R-1 – симметрично ⇔ R = R-1.

3. Доказать, что отношение R – транзитивно ⇔ R2⊆ R (здесь  R2= R*R) .

4. Доказать, что пустое отношение ∅ – симметрично и транзитивно.

5. Найти множества, для которых пустое отношение ∅ – рефлексивно.

6. Доказать, что на множестве Х  наибольшее отношение

R= X×X рефлексивно, симметрично и транзитивно, и, следовательно, является отношением эквивалентности.

7. Доказать, что пересечение рефлексивных отношений  – рефлексивно, пересечение симметричных отношений – симметрично, пересечение транзитивных отношений – транзитивно, пересечение отношений эквивалентности - отношение эквивалентности.

8. Доказать, что объединение рефлексивных отношений – рефлексивно, объединение симметричных отношений – симметрично. Привести пример транзитивных отношений, объединение которых не транзитивно.

9.  Привести пример симметричных отношений, компози-

ция которых не симметрична. Привести пример транзитивных отношений, композиция которых не транзитивна.

  Определение. Для отношения эквивалентности π на мно­же­стве Х определим класс элемента х∈ Х  как

clπ x = { y∈ Х| yπ x }. Когда ясно, какое отношение эквивалентности имеется ввиду, будем обозначать класс элемента х также  cl x или  .

  Утверждения. Пусть π - отношение эквивалентности. Тогда

1) ∀ х∈ Х  х∈ clπ x. 

2)  Если х∈ clπ y, то y∈ clπ x.

3)  Если y∈ clπ x, то clπ y ⊆ clπ x.

4)  Если  yπ x, то clπ y =  clπ x.

  Доказательство 1) следует из определения рефлексивности, 2) – из определения симметричности, 3) – из определения транзитивности, 4) – из утверждений 2), 3). 

  Теорема. Если на множестве Х задано отношение эквивалентности  π, то множество Х  разбивается в  объединение непересекающихся классов эквивалентных элементов, то есть  X = , где ∀ x, y∈ X либо  clπ х ∩ clπ y = ∅, либо clπ х = clπ y. Наоборот, любое разбиение множества Х в объединение непересекающихся подмножеств получается из некоторого отношения эквивалентности, которое определено однозначно, то есть если Х = U Хi, где  Хi ∩ Хj = ∅  при i ≠  j, то ∃! отношение эквивалентности π  такое, что ∀i  Хi = clπ хi, где хi∈ Хi.

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

⇒.  1. Очевидно, ∀ х∈ Х  х∈ clπ x  ⇒ X = .

2. Если  clπ х ∩ clπ y ≠ ∅, то есть clπ х ∩ clπ y? z, то из утверждения 4)  clπ х = clπ z = clπ y.

⇐ . Пусть Х = U Хi, где  Хi ∩ Хj = ∅  при i ≠  j. Если существует отношения эквивалентности π, которое порождает  данное разбиение, то есть ∀i  Хi = clπ хi, то все элементы из каждого подмножества Хi должны находиться в отношении π, а элементы, не лежащие в одном подмножестве, не должны находиться в отношении π . То есть  хπу ⇔ ∃ i такое, что

х, у∈ Хi. Это означает единственность π.

  Докажем существование. Как мы только что увидели, если π ∃, то хπу ⇔ ∃ i такое, что х, у∈ Хi. Очевидно, так определенное отношение π  рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. ∀ х∈Х  clπ х – это множество элементов, находящихся с х в отношении π, то есть подмножество Хi, содержащее элемент х. Это

означает существование π.

  Определение. Множество классов эквивалентных элементов по отношению π называется фактор-множеством и обозначается Х/π. Другими словами, элементами множества

Х/π  являются классы эквивалентных элементов множества Х. Часто отношение эквивалентности обозначается знаком ~ .

  Упражнения.

1. Пусть π1  и  π2  - отношения эквивалентности на Х. Найти классы эквивалентных элементов для отношения эквивалентности π1 ∩ π2 .