Algebra ir geometrija informatikams. Paskaitu̧ konspektas. Rimantas Grigutis

5 paskaita (2002 10 04). Keitiniai.

Tegu π yra aibės N_{n} = {1, 2, ..., n} kėlinys (v_{1}, v_{2}, ..., v_{n}) . Tuo pačiu žymeniu π žymėsime ir funkcija̧, kuria̧ vadinsime keitiniu

π : N_{n} → N_{n},
π (1) = v_{1}, π (2) = v_{2}, ..., π (n) = v_{n}.

Žinome, kad keitiniai yra abipus vienareikšmės funkcijos ir ju̧ yra n! . Visu̧ aibės N_{n} keitiniu̧ aibȩ žymėsime S_{n}.

Pateiksime keitiniu̧ reiškimo būdus.

1. Keitinio, kaip funkcijos apibrėžtos baigtinėje aibėje, reiškimas lentele:

( \begin{matrix}1 & 2 & ... & n \\ v_{1} & v_{2} & ... & v_{n} \end{matrix} ) .

2. Reiškimas grafu. Grafas sudarytas iš viršūniu̧ i ir orientuotu̧ briaunu̧ ⟨i, π (i)⟩ , 1 ≤ i ≤ n .

Pavyzdys. N_{7} = {1, 2, 3, 4, 5, 6, 7}

π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 4 & 5 & 2 & 1 & 6 & 7 \end{matrix} )

\begin{aligned}& & 1 \\ & ↗ & & ↘ \\ 5 & & ⟵ & & 3 \end{aligned} 2 ⟷ 4 6 7

3. Reiškimas nepriklausomais ciklais. Tegu i ∈ N_{n} . Tada turime aibės N_{n} elementu̧ seka̧

i, π (i) , π^{2} (i) = π (π (i)) , ..., π^{k−1} (i) , π^{k} (i) = i.

Gauname k ilgio cikla̧ (i, π (i) , π^{2} (i) = π (π (i)) , ..., π^{k−1} (i)) . Jeigu k = n , tai visi aibės N_{n} elementai yra šiame cikle. Kitu atveju, egzis-

tuoja toks j ∉ (i, π (i) , π^{2} (i) = π (π (i)) , ..., π^{k−1} (i)) , kuriam konstruojame savo cikla̧:

(j, π (j) , π^{2} (j) = π (π (j)) , ..., π^{l−1} (j)) .

Skirtinguose cikluose yra skirtingi elementai. Jeigu būtu̧ kitaip, tai atsirastu̧ tokie r ir s, kad π^{r} (j) = π^{s} (i) ir π^{r+1} (j) = π^{s+1} (i) , …, j = π^{l} (j) = π^{s+(l−r)} (i), o tada elementas j priklausytu̧ pirma̧jam ciklui, o tai prieštarautu̧ sa̧lygai.

Tokiu būdu, visi aibės N_{n} elementai suskyla keitinio π atžvilgiu i̧ nepriklausomus ciklus, o pats keitinys π reiškiamas nepriklausomu̧ ciklu̧ ”sandauga”( vadinama dar kanoniniu keitinio π skaidiniu):

(i, π (i) , π^{2} (i) , ..., π^{k−1} (i)) (j, π (j) , π^{2} (j) , ..., π^{l−1} (j)) · · · .

Parodėme, kad bet kuri̧ keitini̧ galima užrašyti poromis nepriklausomu̧ ciklu̧ ”sandauga”. Šis skaidinys yra vienintėlis nepriklausomu̧ ciklu̧ išsidėstymo tikslumu.

Paaiškinsime ”sandaugos” sa̧voka̧.

Apibrėžimas.Tegu π , ρ - keitiniai aibėje V. Keitiniu̧ sandauga σ = π ∘ ρ vadinsime keitini̧, apibrėžta̧ lygybe

σ (i) = ρ (π (i)) , ∀v_{i} ∈ N_{n}.

Pastebėsime, kad taip apibrėžta sandauga yra funkciju̧ kompozicija. Ji nėra komutatyvi, t.y. ne visada π ∘ ρ = ρ ∘ π.

Pavyzdys. Kai π = ( \begin{matrix}1 & 2 & 3 \\ 3 & 2 & 1 \end{matrix} ), o ρ = ( \begin{matrix}1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix} ), tai

π ∘ ρ = ( \begin{matrix}1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix} ) ≠ ( \begin{matrix}1 & 2 & 3 \\ 1 & 3 & 2 \end{matrix} ) = ρ ∘ π .

Pastebėsime. kad keitinio π kanoniniame skaidinyje esantys nepriklausomi ciklai komutuoja poromis.

Keitiniu̧ sandauga aibėje S_{n} pasižymi savybėmis:

S1. Operacijos korektiškumas: jei π, ρ ∈ S_{n} , tai π ∘ ρ ∈ S_{n} . S2. Asociatyvumas: (π ∘ ρ) ∘ τ = π ∘ (ρ ∘ τ) . ((π ∘ ρ) ∘ τ) (i) = τ ((π ∘ ρ) (i)) = τ (ρ (π (i))) = (ρ ∘ τ) (π (i)) = (π ∘ (ρ ∘ τ)) (i) .

S3. Neutralaus elemento egzistavimas : id(i) = i , ∀i ∈ N_{n} , todėl id∘π = π∘id= π , su visais π ∈ S_{n}.

4) Atvirkštinio elemento egzistavimas: jei π (i) = v_{i} , su visais i ∈ N_{n},tai keitinys ρ (v_{i}) = i, su visais i ∈ N_{n}, vaidina veiksmo ∘ atžvilgiu atvirkštinio elemento vaidmeni̧:

π ∘ ρ = ρ ∘ π =id.

Apibrėžimas. Ciklas (i, j) vadinamas transpozicija.

Teiginys. Kai n ≥ 2, tai bet kuri̧ keitini̧ iš S_{n} galima užrašyti transpoziciju̧ sandauga.

I̧rodymas. Ši̧ teigini̧ pakanka i̧rodyti k ilgio ciklui. Kai k = 1, tai (i) = (i, j) ∘ (i, j) . Kai k = 2, tai (i, j) = (i, j) , o kai k ≥ 3, tai (1, 2, ..., k) = (1, 2) ∘ (1, 3) ∘ ⋯ ∘ (1, k). Sandaugoje yra k − 1

transpozicija.

I̧rodyta.

Pastebėsime, kad keitinio reiškimas transpoziciju̧ sandauga yra nevienareikšmiškas.

Pavyzdžiui,

(i, j) = (i, j) ∘ (j, i) ∘ (j, i) .

Pastovus dydis šiame reiškime vis dėlto yra: tai transpoziciju̧ skaičiaus dalybos iš 2 liekana , t.y. kiekviename keitinio reiškime transpozicijomis pastaru̧ju̧ skaičius yra arba visada lyginis, arba visada nelyginis..

Apibrėžimas. Tegu π ∈ S_{n}. Pora (i, j), kai i < j, bet π (i) > π (j) vadinama keitinio π inversija.

π vadinamas lyginiu keitiniu, jeigu π inversiju̧ skaičius yra lyginis. π vadinamas nelyginiu keitiniu, jeigu π inversiju̧ skaičius yra nelyginis.

Keitinio π inversiju̧ skaičiu̧ žymėsime |π|, o ženkla̧ signπ = (−1)^{|π|} . Pastebėsime, kad tapatusis keitinys id yra lyginis. Jei π− lyginis, tai signπ = 1,

jei π− nelyginis, tai signπ = −1.

Teiginys. Skaičius |π ∘ (a, b)| − |π| ya nelyginis su visomis transpozicijomis (a, b) .

I̧rodymas.

π = ( \begin{matrix}1 & ... & k & k + 1 & k + 2 & ... & k + l + 1 & k + l + 2 & k + l + 3 & ... & n \\ a_{1} & ... & a_{k} & a & b_{1} & ... & b_{l} & b & c_{1} & ... & c_{m} \end{matrix} ) ,

π∘(a, b) = ( \begin{matrix}1 & ... & k & k + 1 & k + 2 & ... & k + l + 1 & k + l + 2 & k + l + 3 & ... & n \\ a_{1} & ... & a_{k} & b & b_{1} & ... & b_{l} & a & c_{1} & ... & c_{m} \end{matrix} ) .

Pažymėkime:

p_{a} = |{a_{1}, ..., a_{k}|a_{i} > a}| , q_{a} = |{a_{1}, ..., a_{k}|a_{i} > b}|
p_{b} = |{b_{1}, ..., b_{l}|b_{i} > a}| , q_{b} = |{b_{1}, ..., b_{l}|b_{i} > b}|
p_{c} = |{c_{1}, ..., c_{m}|c_{i} > a}| , q_{c} = |{c_{1}, ..., c_{m}|c_{i} > b}| .

Tegu skaičius r yra keitinio

( \begin{matrix}1 & ... & k & k + 2 & ... & k + l + 1 & k + l + 3 & ... & n \\ a_{1} & ... & a_{k} & b_{1} & ... & b_{l} & c_{1} & ... & c_{m} \end{matrix} )

inversiju̧ skaičius. Tada , kai a < b turime

|π| = p_{a} + (l − p_{b}) + (m − p_{c}) + q_{a} + q_{b} + (m − q_{c}) + r,
|π ∘ (a, b)| = p_{a} + p_{b} + (m − p_{c}) + q_{a} + (l − q_{b}) + (m − q_{c}) + 1 + r.

Todėl

|π| − |π ∘ (a, b)| = 2 (q_{b} − p_{b}) + 1

yra nelyginis skaičius. Atvejis a > b nagrinėjamas analogiškai.

I̧rodyta .

Turime, kad sign(id) = 1 ir sign((a, b)) = −1 .

Teiginys. Transpoziciju̧ skaičius keitinio π reiškime transpozicijomis yra arba visada lyginis, arba visada nelyginis .

I̧rodymas. Jeigu turime du keitinio π reiškimus transpoziciju̧ sandauga :

π = σ_{1} ⋯ σ_{k} = τ_{1} ⋯ τ_{l} ,

tai

signπ =sign(σ_{1} ⋯ σ_{k}) =sign(τ_{1} ⋯ τ_{l})

ir

signπ = (−1)^{k} = (−1)^{l} ⟹ (−1)^{k−l} = 1 ⟹skaičius k − l lyginis⟹ skaičiai k, l arba abu lyginiai, raba abu nelyginiai.

I̧rodyta.

Išvados.

1. Keitinys yra lyginis tada ir tik tada, kai jis yra lyginio skaičiaus transpozicijiu̧ sandauga.

2. Keitinys yra nelyginis tada ir tik tada, kai jis yra nelyginio skaičiaus transpozicijiu̧ sandauga.

3. k-ciklas yra lyginis tada ir tik tada, kai k yra nelyginis ir atvirkščiai.

4. (lyginis) ∘ (lyginis) = (lyginis) . (nelyginis) ∘ (nelyginis) = (lyginis) . (nelyginis) ∘ (lyginis) = (nelyginis) .

5. sign(π ∘ ρ) =sign(π) ·sign(ρ) .

Lyginiu̧ keitinu̧ aibȩ žymėsime A_{n} ir vadina alternuojančia keitiniu̧ aibe.

Teiginys. Lyginiu̧ ir nelyginiu̧ keitiniu̧ yra po lygiai \frac{n!}{2} .

I̧rodymas. Nagrinėjama alternuojanti keitiniu̧ aibė A_{n}. Apibrėžiama aibė

U_{(a,b)} = {π ∈ S_{n}|π = σ ∘ (a, b) , σ ∈ A_{n}} ⊆ S_{n} − A_{n}.

Tegu |A_{n}| = m_{1} , |S_{n} − A_{n}| = m_{2}. Tada aibės U_{(a,b)} visi elementai skirtingi: σ_{1} ∘ (a, b) = σ_{2} ∘ (a, b) ⟺ σ_{1} ∘ (a, b) ∘ (a, b) = σ_{2} ∘ (a, b) ∘ (a, b) ⟺ σ_{1} = σ_{2}. Taigi, |U_{(a,b)}| = |A_{n}| = m_{1} ≤ m_{2}.

Analogiškai, tegu turime aibȩ

V_{(a,b)} = {π ∈ S_{n}|π = ρ ∘ (a, b) , ρ ∈ S_{n} − A_{n}} ⊆ A_{n}.

Kaip ir aibės U_{(a,b)} taip ir aibės V_{(a,b)} visi elementai skirtingi. Tada |V_{(a,b)}| = |S_{n} − A_{n}| = m_{2} ≤ m_{1}.

Taigi, m_{1} = m_{2} = \frac{n!}{2} .

I̧rodyta.