Sign of a permutation

The main definition of this file is Equiv.Perm.sign, associating a ℤˣ sign with a permutation.

Other lemmas have been moved to Mathlib.GroupTheory.Perm.Fintype

def Equiv.Perm.modSwap {α : Type u} [DecidableEq α] (i : α) (j : α) : Setoid (Equiv.Perm α)

modSwap i j contains permutations up to swapping i and j.

We use this to partition permutations in Matrix.det_zero_of_row_eq, such that each partition sums up to 0.

Equations

• Equiv.Perm.modSwap i j = { r := fun (σ τ : Equiv.Perm α) => σ = τ ∨ σ = Equiv.swap i j * τ, iseqv := ⋯ }

noncomputable instance Equiv.Perm.instDecidableRelROfFintype {α : Type u_1} [Fintype α] [DecidableEq α] (i : α) (j : α) : DecidableRel Setoid.r

Equations

• Equiv.Perm.instDecidableRelROfFintype i j x✝ x = Or.decidable

def Equiv.Perm.swapFactorsAux {α : Type u} [DecidableEq α] (l : List α) (f : Equiv.Perm α) : (∀ {x : α}, f x ≠ x → x ∈ l) → { l : List (Equiv.Perm α) // l.prod = f ∧ ∀ g ∈ l, g.IsSwap }

Given a list l : List α and a permutation f : Perm α such that the nonfixed points of f are in l, recursively factors f as a product of transpositions.

Equations

• One or more equations did not get rendered due to their size.
• Equiv.Perm.swapFactorsAux [] = fun (f : Equiv.Perm α) (h : ∀ {x : α}, f x ≠ x → x ∈ []) => ⟨[], ⋯⟩

def Equiv.Perm.swapFactors {α : Type u} [DecidableEq α] [Fintype α] [LinearOrder α] (f : Equiv.Perm α) : { l : List (Equiv.Perm α) // l.prod = f ∧ ∀ g ∈ l, g.IsSwap }

swapFactors represents a permutation as a product of a list of transpositions. The representation is non unique and depends on the linear order structure. For types without linear order truncSwapFactors can be used.

Equations

• f.swapFactors = Equiv.Perm.swapFactorsAux (Finset.sort (fun (x x_1 : α) => x ≤ x_1) Finset.univ) f ⋯

def Equiv.Perm.truncSwapFactors {α : Type u} [DecidableEq α] [Fintype α] (f : Equiv.Perm α) : Trunc { l : List (Equiv.Perm α) // l.prod = f ∧ ∀ g ∈ l, g.IsSwap }

This computably represents the fact that any permutation can be represented as the product of a list of transpositions.

Equations

• One or more equations did not get rendered due to their size.

theorem Equiv.Perm.swap_induction_on {α : Type u} [DecidableEq α] [Finite α] {P : Equiv.Perm α → Prop} (f : Equiv.Perm α) : P 1 → (∀ (f : Equiv.Perm α) (x y : α), x ≠ y → P f → P (Equiv.swap x y * f)) → P f

An induction principle for permutations. If P holds for the identity permutation, and is preserved under composition with a non-trivial swap, then P holds for all permutations.

theorem Equiv.Perm.mclosure_isSwap {α : Type u} [DecidableEq α] [Finite α] : Submonoid.closure {σ : Equiv.Perm α | σ.IsSwap} = ⊤

theorem Equiv.Perm.closure_isSwap {α : Type u} [DecidableEq α] [Finite α] : Subgroup.closure {σ : Equiv.Perm α | σ.IsSwap} = ⊤

theorem Equiv.Perm.mclosure_swap_castSucc_succ (n : ℕ) : Submonoid.closure (Set.range fun (i : Fin n) => Equiv.swap i.castSucc i.succ) = ⊤

Every finite symmetric group is generated by transpositions of adjacent elements.

theorem Equiv.Perm.swap_induction_on' {α : Type u} [DecidableEq α] [Finite α] {P : Equiv.Perm α → Prop} (f : Equiv.Perm α) : P 1 → (∀ (f : Equiv.Perm α) (x y : α), x ≠ y → P f → P (f * Equiv.swap x y)) → P f

Like swap_induction_on, but with the composition on the right of f.

An induction principle for permutations. If P holds for the identity permutation, and is preserved under composition with a non-trivial swap, then P holds for all permutations.

theorem Equiv.Perm.isConj_swap {α : Type u} [DecidableEq α] {w : α} {x : α} {y : α} {z : α} (hwx : w ≠ x) (hyz : y ≠ z) : IsConj (Equiv.swap w x) (Equiv.swap y z)

def Equiv.Perm.finPairsLT (n : ℕ) : Finset ((_ : Fin n) × Fin n)

set of all pairs (⟨a, b⟩ : Σ a : fin n, fin n) such that b < a

Equations

• Equiv.Perm.finPairsLT n = Finset.univ.sigma fun (a : Fin n) => (Finset.range ↑a).attachFin ⋯

theorem Equiv.Perm.mem_finPairsLT {n : ℕ} {a : (_ : Fin n) × Fin n} : a ∈ Equiv.Perm.finPairsLT n ↔ a.snd < a.fst

def Equiv.Perm.signAux {n : ℕ} (a : Equiv.Perm (Fin n)) : ℤˣ

signAux σ is the sign of a permutation on Fin n, defined as the parity of the number of pairs (x₁, x₂) such that x₂ < x₁ but σ x₁ ≤ σ x₂

Equations

• a.signAux = ∏ x ∈ Equiv.Perm.finPairsLT n, if a x.fst ≤ a x.snd then -1 else 1

@[simp]

theorem Equiv.Perm.signAux_one (n : ℕ) : Equiv.Perm.signAux 1 = 1

def Equiv.Perm.signBijAux {n : ℕ} (f : Equiv.Perm (Fin n)) (a : (_ : Fin n) × Fin n) : (_ : Fin n) × Fin n

signBijAux f ⟨a, b⟩ returns the pair consisting of f a and f b in decreasing order.

Equations

• f.signBijAux a = if x : f a.snd < f a.fst then ⟨f a.fst, f a.snd⟩ else ⟨f a.snd, f a.fst⟩

theorem Equiv.Perm.signBijAux_injOn {n : ℕ} {f : Equiv.Perm (Fin n)} : Set.InjOn f.signBijAux ↑(Equiv.Perm.finPairsLT n)

theorem Equiv.Perm.signBijAux_surj {n : ℕ} {f : Equiv.Perm (Fin n)} (a : (_ : Fin n) × Fin n) : a ∈ Equiv.Perm.finPairsLT n → ∃ b ∈ Equiv.Perm.finPairsLT n, f.signBijAux b = a

theorem Equiv.Perm.signBijAux_mem {n : ℕ} {f : Equiv.Perm (Fin n)} (a : (_ : Fin n) × Fin n) : a ∈ Equiv.Perm.finPairsLT n → f.signBijAux a ∈ Equiv.Perm.finPairsLT n

@[simp]

theorem Equiv.Perm.signAux_inv {n : ℕ} (f : Equiv.Perm (Fin n)) : f⁻¹.signAux = f.signAux

theorem Equiv.Perm.signAux_mul {n : ℕ} (f : Equiv.Perm (Fin n)) (g : Equiv.Perm (Fin n)) : (f * g).signAux = f.signAux * g.signAux

theorem Equiv.Perm.signAux_swap {n : ℕ} {x : Fin n} {y : Fin n} (_hxy : x ≠ y) : (Equiv.swap x y).signAux = -1

def Equiv.Perm.signAux2 {α : Type u} [DecidableEq α] : List α → Equiv.Perm α → ℤˣ

When the list l : List α contains all nonfixed points of the permutation f : Perm α, signAux2 l f recursively calculates the sign of f.

Equations

• Equiv.Perm.signAux2 [] x = 1
• Equiv.Perm.signAux2 (x_2 :: l) x = if x_2 = x x_2 then Equiv.Perm.signAux2 l x else -Equiv.Perm.signAux2 l (Equiv.swap x_2 (x x_2) * x)

theorem Equiv.Perm.signAux_eq_signAux2 {α : Type u} [DecidableEq α] {n : ℕ} (l : List α) (f : Equiv.Perm α) (e : α ≃ Fin n) (_h : ∀ (x : α), f x ≠ x → x ∈ l) : Equiv.Perm.signAux ((e.symm.trans f).trans e) = Equiv.Perm.signAux2 l f

def Equiv.Perm.signAux3 {α : Type u} [DecidableEq α] [Finite α] (f : Equiv.Perm α) {s : Multiset α} : (∀ (x : α), x ∈ s) → ℤˣ

When the multiset s : Multiset α contains all nonfixed points of the permutation f : Perm α, signAux2 f _ recursively calculates the sign of f.

Equations

• f.signAux3 = Quotient.hrecOn (motive := fun (x : Multiset α) => (∀ (x_1 : α), x_1 ∈ x) → ℤˣ) s (fun (l : List α) (x : ∀ (x : α), x ∈ ⟦l⟧) => Equiv.Perm.signAux2 l f) ⋯

theorem Equiv.Perm.signAux3_mul_and_swap {α : Type u} [DecidableEq α] [Finite α] (f : Equiv.Perm α) (g : Equiv.Perm α) (s : Multiset α) (hs : ∀ (x : α), x ∈ s) : (f * g).signAux3 hs = f.signAux3 hs * g.signAux3 hs ∧ Pairwise fun (x y : α) => (Equiv.swap x y).signAux3 hs = -1

theorem Equiv.Perm.signAux3_symm_trans_trans {α : Type u} [DecidableEq α] {β : Type v} [Finite α] [DecidableEq β] [Finite β] (f : Equiv.Perm α) (e : α ≃ β) {s : Multiset α} {t : Multiset β} (hs : ∀ (x : α), x ∈ s) (ht : ∀ (x : β), x ∈ t) : Equiv.Perm.signAux3 ((e.symm.trans f).trans e) ht = f.signAux3 hs

def Equiv.Perm.sign {α : Type u} [DecidableEq α] [Fintype α] : Equiv.Perm α →* ℤˣ

SignType.sign of a permutation returns the signature or parity of a permutation, 1 for even permutations, -1 for odd permutations. It is the unique surjective group homomorphism from Perm α to the group with two elements.

Equations

• Equiv.Perm.sign = MonoidHom.mk' (fun (f : Equiv.Perm α) => f.signAux3 ⋯) ⋯

theorem Equiv.Perm.sign_mul {α : Type u} [DecidableEq α] [Fintype α] (f : Equiv.Perm α) (g : Equiv.Perm α) : Equiv.Perm.sign (f * g) = Equiv.Perm.sign f * Equiv.Perm.sign g

@[simp]

theorem Equiv.Perm.sign_trans {α : Type u} [DecidableEq α] [Fintype α] (f : Equiv.Perm α) (g : Equiv.Perm α) : Equiv.Perm.sign (Equiv.trans f g) = Equiv.Perm.sign g * Equiv.Perm.sign f

theorem Equiv.Perm.sign_one {α : Type u} [DecidableEq α] [Fintype α] : Equiv.Perm.sign 1 = 1

@[simp]

theorem Equiv.Perm.sign_refl {α : Type u} [DecidableEq α] [Fintype α] : Equiv.Perm.sign (Equiv.refl α) = 1

theorem Equiv.Perm.sign_inv {α : Type u} [DecidableEq α] [Fintype α] (f : Equiv.Perm α) : Equiv.Perm.sign f⁻¹ = Equiv.Perm.sign f

@[simp]

theorem Equiv.Perm.sign_symm {α : Type u} [DecidableEq α] [Fintype α] (e : Equiv.Perm α) : Equiv.Perm.sign (Equiv.symm e) = Equiv.Perm.sign e

theorem Equiv.Perm.sign_swap {α : Type u} [DecidableEq α] [Fintype α] {x : α} {y : α} (h : x ≠ y) : Equiv.Perm.sign (Equiv.swap x y) = -1

@[simp]

theorem Equiv.Perm.sign_swap' {α : Type u} [DecidableEq α] [Fintype α] {x : α} {y : α} : Equiv.Perm.sign (Equiv.swap x y) = if x = y then 1 else -1

theorem Equiv.Perm.IsSwap.sign_eq {α : Type u} [DecidableEq α] [Fintype α] {f : Equiv.Perm α} (h : f.IsSwap) : Equiv.Perm.sign f = -1

@[simp]

theorem Equiv.Perm.sign_symm_trans_trans {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (f : Equiv.Perm α) (e : α ≃ β) : Equiv.Perm.sign ((e.symm.trans f).trans e) = Equiv.Perm.sign f

@[simp]

theorem Equiv.Perm.sign_trans_trans_symm {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (f : Equiv.Perm β) (e : α ≃ β) : Equiv.Perm.sign ((e.trans f).trans e.symm) = Equiv.Perm.sign f

theorem Equiv.Perm.sign_prod_list_swap {α : Type u} [DecidableEq α] [Fintype α] {l : List (Equiv.Perm α)} (hl : ∀ g ∈ l, g.IsSwap) : Equiv.Perm.sign l.prod = (-1) ^ l.length

@[simp]

theorem Equiv.Perm.sign_abs {α : Type u} [DecidableEq α] [Fintype α] (f : Equiv.Perm α) : |↑(Equiv.Perm.sign f)| = 1

theorem Equiv.Perm.sign_surjective (α : Type u) [DecidableEq α] [Fintype α] [Nontrivial α] : Function.Surjective ⇑Equiv.Perm.sign

theorem Equiv.Perm.eq_sign_of_surjective_hom {α : Type u} [DecidableEq α] [Fintype α] {s : Equiv.Perm α →* ℤˣ} (hs : Function.Surjective ⇑s) : s = Equiv.Perm.sign

theorem Equiv.Perm.sign_subtypePerm {α : Type u} [DecidableEq α] [Fintype α] (f : Equiv.Perm α) {p : α → Prop} [DecidablePred p] (h₁ : ∀ (x : α), p x ↔ p (f x)) (h₂ : ∀ (x : α), f x ≠ x → p x) : Equiv.Perm.sign (f.subtypePerm h₁) = Equiv.Perm.sign f

theorem Equiv.Perm.sign_eq_sign_of_equiv {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (f : Equiv.Perm α) (g : Equiv.Perm β) (e : α ≃ β) (h : ∀ (x : α), e (f x) = g (e x)) : Equiv.Perm.sign f = Equiv.Perm.sign g

theorem Equiv.Perm.sign_bij {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] {f : Equiv.Perm α} {g : Equiv.Perm β} (i : (x : α) → f x ≠ x → β) (h : ∀ (x : α) (hx : f x ≠ x) (hx' : f (f x) ≠ f x), i (f x) hx' = g (i x hx)) (hi : ∀ (x₁ x₂ : α) (hx₁ : f x₁ ≠ x₁) (hx₂ : f x₂ ≠ x₂), i x₁ hx₁ = i x₂ hx₂ → x₁ = x₂) (hg : ∀ (y : β), g y ≠ y → ∃ (x : α) (hx : f x ≠ x), i x hx = y) : Equiv.Perm.sign f = Equiv.Perm.sign g

theorem Equiv.Perm.prod_prodExtendRight {β : Type v} {α : Type u_1} [DecidableEq α] (σ : α → Equiv.Perm β) {l : List α} (hl : l.Nodup) (mem_l : ∀ (a : α), a ∈ l) : (List.map (fun (a : α) => Equiv.Perm.prodExtendRight a (σ a)) l).prod = Equiv.prodCongrRight σ

If we apply prod_extendRight a (σ a) for all a : α in turn, we get prod_congrRight σ.

@[simp]

theorem Equiv.Perm.sign_prodExtendRight {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (a : α) (σ : Equiv.Perm β) : Equiv.Perm.sign (Equiv.Perm.prodExtendRight a σ) = Equiv.Perm.sign σ

theorem Equiv.Perm.sign_prodCongrRight {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (σ : α → Equiv.Perm β) : Equiv.Perm.sign (Equiv.prodCongrRight σ) = ∏ k : α, Equiv.Perm.sign (σ k)

theorem Equiv.Perm.sign_prodCongrLeft {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (σ : α → Equiv.Perm β) : Equiv.Perm.sign (Equiv.prodCongrLeft σ) = ∏ k : α, Equiv.Perm.sign (σ k)

@[simp]

theorem Equiv.Perm.sign_permCongr {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (e : α ≃ β) (p : Equiv.Perm α) : Equiv.Perm.sign (e.permCongr p) = Equiv.Perm.sign p

@[simp]

theorem Equiv.Perm.sign_sumCongr {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (σa : Equiv.Perm α) (σb : Equiv.Perm β) : Equiv.Perm.sign (σa.sumCongr σb) = Equiv.Perm.sign σa * Equiv.Perm.sign σb

@[simp]

theorem Equiv.Perm.sign_subtypeCongr {α : Type u} [DecidableEq α] [Fintype α] {p : α → Prop} [DecidablePred p] (ep : Equiv.Perm { a : α // p a }) (en : Equiv.Perm { a : α // ¬p a }) : Equiv.Perm.sign (ep.subtypeCongr en) = Equiv.Perm.sign ep * Equiv.Perm.sign en

@[simp]

theorem Equiv.Perm.sign_extendDomain {α : Type u} [DecidableEq α] {β : Type v} [Fintype α] [DecidableEq β] [Fintype β] (e : Equiv.Perm α) {p : β → Prop} [DecidablePred p] (f : α ≃ Subtype p) : Equiv.Perm.sign (e.extendDomain f) = Equiv.Perm.sign e

@[simp]

theorem Equiv.Perm.sign_ofSubtype {α : Type u} [DecidableEq α] [Fintype α] {p : α → Prop} [DecidablePred p] (f : Equiv.Perm (Subtype p)) : Equiv.Perm.sign (Equiv.Perm.ofSubtype f) = Equiv.Perm.sign f