Permutations and Determinants
This chapter introduces basic concepts about permutations and determinants of matrices, the first part contains permutation groups explained through various definitions and theorems, the second part is about determinants of matrices, a method to obtain th
- PDF / 187,496 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 215 Views
Permutations and Determinants
Abstract This chapter introduces basic concepts about permutations and determinants of matrices, the first part contains permutation groups explained through various definitions and theorems, the second part is about determinants of matrices, a method to obtain the determinant of a matrix is given along various other useful results.
5.1 Permutations Group Definition 5.1 Let X a nonempty set. The permutations group in X , denoted by S X is the set of bijective functions of X itself. The elements of S X are called permutations (of the elements of X ) [1–4]. Proposition 5.1 Let X a nonempty set. 1. 2. 3. 4.
σ, τ ∈ S X then σ ◦ τ ∈ S X . ∀ σ, τ, ρ ∈ S X , (σ ◦ τ ) ◦ ρ = σ ◦ (τ ◦ ρ). There exists id X ∈ S X such that σ ◦ id X = id X ◦ σ = σ ∀ σ ∈ S X . Let σ ∈ S X there exists τ = σ −1 ∈ S X such that σ ◦ τ = τ ◦ σ = id X .
Proof 1. The proof 1, 2 and 4 are left as an exercise to the reader. 2. 3. Having σ ∈ S X and x ∈ X , then (σ ◦ id X ) (x) = σ (id X (x)) = σ (x) and (id X ◦ σ ) (x) = id X (σ (x)) = σ (x) then it is possible to conclude σ ◦ id X = id X ◦ σ = σ 4. Corollary 5.1 Let σ, τ, ρ ∈ S X . 1. If σ ◦ τ = σ ◦ ρ, then τ = ρ. 2. If σ ◦ ρ = τ ◦ ρ, then σ = τ .
© Springer Nature Switzerland AG 2019 R. Martínez-Guerra et al., Algebraic and Differential Methods for Nonlinear Control Theory, Mathematical and Analytical Techniques with Applications to Engineering, https://doi.org/10.1007/978-3-030-12025-2_5
65
66
5 Permutations and Determinants
−1 −1 −1 Proof −11. σ ◦ τ = σ ◦ ρ ⇒ σ ◦ (σ ◦ τ ) = σ ◦ (σ ◦ ρ) ⇒ σ ◦ σ ◦ τ = σ ◦ σ ◦ ρ ⇒ id X ◦ τ = id X ◦ ρ ⇒ τ = ρ 2. The procedure is similar to 1 and it is left as an exercise to the reader. Proposition 5.2 If X is a finite set with n elements, then S X has n! = 1 · 2 · . . . · n elements. In this case S X = Sn .
Proof It is left as an exercise to the reader.
Remark 5.1 Let suppose n > 1. If X = {1, 2, . . . , n} and ϕ ∈ Sn , then ϕ is a bijection of X in itself: ϕ : X −→ X 1 −→ i 1 2 −→ i 2 .. . n −→ i n We write:
1 2 ··· n ϕ= i1 i2 · · · in
Let n, k ∈ N, with k ≤ n. Let i 1 , i 2 , . . . , i k different integers in X = {1, 2, . . . , n}. We write i1 i2 · · · ik to represent the permutation σ ∈ Sn given by σ (i 1 ) = i 2 , σ (i 2 ) = i 3 , . . . , σ (i k−1 ) = i k , σ (i k ) = i 1 and σ (x) = x ∀x ∈ X, x ∈ / {i 1 , i 2 , . . . , i k }. Definition 5.2 It said that a permutation i 1 i 2 · · · i k is called cycle of order k or k-cycle. If k = 2 , the 2-cycle is called transposition. Proposition 5.3 If σ is a k-cycle then σ k = σ ◦ · · · ◦ σ = id Proof It is left to the reader as an exercise.
Definition 5.3 It is said that two cycles are disjoint if they have elements in common. Lemma 5.1 Let σ, τ ∈ Sn . If σ and τ are disjoint cycles then σ ◦ τ = τ ◦ σ . In this case we say that σ and τ commute.
5.1 Permutations Group
67
Proof It is left to the reader as an exercise.
Theorem 5.1 Every permutation in Sn is a product of disjoint cycles pairs. This is uniquely except the order and 1-cycle [2, 5–
Data Loading...
