Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 160 стр.

UptoLike

ВУЗ: 

ИвГУ | Иваново

Составители: 

Рубрика: 

160 Теория перестановок Гл. 3
16.2. Умножение перестановок. Рассмотрим множество S
n
перестановок степени n. Действия над перестановками — это дей-
ствия над отображениями (в данном случае — биективными отобра-
жениями множества (16.1) на себя).
Умножение перестановок — это не что иное, как их композиция:
по двум перестановкам ϕ, ψ ∈ S
n
определяется их произведение
ϕψ = ϕ ◦ ψ. (Ради краткости записи кружок ◦, знак композиции,
обычно опускается.) Ясно, что композиция двух биекций сама явля-
ется биекцией, т. е. ϕψ ∈ S
n
.
Пример 16.2. Покажем один из возможных способов "оформ-
ления" умножения перестановок. При минимальном навыке это офо-
рмление делается в уме.
ϕ =
µ
1 2 3 4
4 1 3 2
; ψ =
µ
1 2 3 4
3 4 1 2
1 2 3 4
ϕ ↓ ↓ ↓ ↓
4 1 3 2
ψ ↓ ↓ ↓ ↓
2 3 1 4
1 2 3 4
ψ ↓ ↓ ↓ ↓
3 4 1 2
ϕ ↓ ↓ ↓ ↓
3 2 4 1
ψϕ =
µ
1 2 3 4
2 3 1 4
; ϕψ =
µ
1 2 3 4
3 2 4 1
Надеемся, вы обратили внимание на тот факт, что умножение
(композиция) перестановок не удовлетворяет коммутативному за-
кону: перестановки-сомножители, вообще говоря, нельзя перестав-
лять.
Замечание 16.5. Как и в общем случае действий над отображе-
ниями (см. замечание 15.3), непримиримые партии "правых" и "ле-
вых" используют противоположный порядок действия сомножите-
лей в произведении перестановок. Мы, следуя [2], придерживаемся
левосторонней записи: в произведении ϕψ сначала действует ψ, а
потом ϕ. В курсе [3] используется правосторонняя запись.
16.3. Тождественная (единичная) перестановка. Симво-
лом ε будет обозначаться (фактически это уже делалось в примере
16.1) тождественная (единичная) перестановка
ε =
µ
1 2 · · · n
1 2 · · · n
∈ S
n
. (16.3)
160                       Теория перестановок                     Гл. 3

   16.2. Умножение перестановок. Рассмотрим множество Sn
перестановок степени n. Действия над перестановками — это дей-
ствия над отображениями (в данном случае — биективными отобра-
жениями множества (16.1) на себя).
   Умножение перестановок — это не что иное, как их композиция:
по двум перестановкам ϕ, ψ ∈ Sn определяется их произведение
ϕψ = ϕ ◦ ψ. (Ради краткости записи кружок ◦, знак композиции,
обычно опускается.) Ясно, что композиция двух биекций сама явля-
ется биекцией, т. е. ϕψ ∈ Sn .
  Пример 16.2. Покажем один из возможных способов "оформ-
ления" умножения перестановок. При минимальном навыке это офо-
рмление делается в уме.
                µ           ¶       µ           ¶
                   1 2 3 4            1 2 3 4
            ϕ=                ; ψ=
                   4 1 3 2            3 4 1 2

                      1    2 3    4          1 2    3 4
               ϕ      ↓    ↓ ↓    ↓     ψ    ↓ ↓    ↓ ↓
                      4    1 3    2          3 4    1 2
               ψ      ↓    ↓ ↓    ↓     ϕ    ↓ ↓    ↓ ↓
                      2    3 1    4          3 2    4 1
                  µ                ¶          µ               ¶
                      1 2    3   4              1   2 3   4
           ψϕ =                      ; ϕψ   =
                      2 3    1   4              3   2 4   1
   Надеемся, вы обратили внимание на тот факт, что умножение
(композиция) перестановок не удовлетворяет коммутативному за-
кону: перестановки-сомножители, вообще говоря, нельзя перестав-
лять.
  Замечание 16.5. Как и в общем случае действий над отображе-
ниями (см. замечание 15.3), непримиримые партии "правых" и "ле-
вых" используют противоположный порядок действия сомножите-
лей в произведении перестановок. Мы, следуя [2], придерживаемся
левосторонней записи: в произведении ϕψ сначала действует ψ, а
потом ϕ. В курсе [3] используется правосторонняя запись.
   16.3. Тождественная (единичная) перестановка. Симво-
лом ε будет обозначаться (фактически это уже делалось в примере
16.1) тождественная (единичная) перестановка
                       µ             ¶
                         1 2 ··· n
                    ε=                 ∈ Sn .             (16.3)
                         1 2 ··· n

Страницы