# Documentation

Mathlib.GroupTheory.Perm.Sign

# Sign of a permutation #

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

This file also contains miscellaneous lemmas about Equiv.Perm and Equiv.swap, building on top of those in Data/Equiv/Basic and other files in GroupTheory/Perm/*.

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

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.

Instances For
noncomputable instance Equiv.Perm.instDecidableRelPermRModSwap {α : Type u_1} [] [] (i : α) (j : α) :
DecidableRel Setoid.r
theorem Equiv.Perm.perm_inv_on_of_perm_on_finset {α : Type u} {s : } {f : } (h : ∀ (x : α), x sf x s) {y : α} (hy : y s) :
f⁻¹ y s
theorem Equiv.Perm.perm_inv_mapsTo_of_mapsTo {α : Type u} (f : ) {s : Set α} [Finite s] (h : Set.MapsTo (f) s s) :
Set.MapsTo (f⁻¹) s s
@[simp]
theorem Equiv.Perm.perm_inv_mapsTo_iff_mapsTo {α : Type u} {f : } {s : Set α} [Finite s] :
Set.MapsTo (f⁻¹) s s Set.MapsTo (f) s s
theorem Equiv.Perm.perm_inv_on_of_perm_on_finite {α : Type u} {f : } {p : αProp} [Finite { x // p x }] (h : (x : α) → p xp (f x)) {x : α} (hx : p x) :
p (f⁻¹ x)
@[inline, reducible]
abbrev Equiv.Perm.subtypePermOfFintype {α : Type u} (f : ) {p : αProp} [Fintype { x // p x }] (h : (x : α) → p xp (f x)) :
Equiv.Perm { x // p x }

If the permutation f maps {x // p x} into itself, then this returns the permutation on {x // p x} induced by f. Note that the h hypothesis is weaker than for Equiv.Perm.subtypePerm.

Instances For
@[simp]
theorem Equiv.Perm.subtypePermOfFintype_apply {α : Type u} (f : ) {p : αProp} [Fintype { x // p x }] (h : (x : α) → p xp (f x)) (x : { x // p x }) :
↑() x = { val := f x, property := h (x) x.property }
theorem Equiv.Perm.subtypePermOfFintype_one {α : Type u} (p : αProp) [Fintype { x // p x }] (h : (x : α) → p xp (1 x)) :
theorem Equiv.Perm.perm_mapsTo_inl_iff_mapsTo_inr {m : Type u_1} {n : Type u_2} [] [] (σ : Equiv.Perm (m n)) :
Set.MapsTo (σ) (Set.range Sum.inl) (Set.range Sum.inl) Set.MapsTo (σ) (Set.range Sum.inr) (Set.range Sum.inr)
theorem Equiv.Perm.mem_sumCongrHom_range_of_perm_mapsTo_inl {m : Type u_1} {n : Type u_2} [] [] {σ : Equiv.Perm (m n)} (h : Set.MapsTo (σ) (Set.range Sum.inl) (Set.range Sum.inl)) :
theorem Equiv.Perm.Disjoint.orderOf {α : Type u} {σ : } {τ : } (hστ : ) :
orderOf (σ * τ) = Nat.lcm () ()
theorem Equiv.Perm.Disjoint.extendDomain {β : Type v} {α : Type u_1} {p : βProp} [] (f : α ) {σ : } {τ : } (h : ) :
theorem Equiv.Perm.support_pow_coprime {α : Type u} [] [] {σ : } {n : } (h : Nat.Coprime n ()) :
def Equiv.Perm.swapFactorsAux {α : Type u} [] (l : List α) (f : ) :
(∀ {x : α}, f x xx l) → { l // = f ∀ (g : ), g l }

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.
• = fun f h => { val := [], property := (_ : = f ∀ (g : ), g []) }
Instances For
def Equiv.Perm.swapFactors {α : Type u} [] [] [] (f : ) :
{ l // = f ∀ (g : ), g l }

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.

Instances For
def Equiv.Perm.truncSwapFactors {α : Type u} [] [] (f : ) :
Trunc { l // = f ∀ (g : ), g l }

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

Instances For
theorem Equiv.Perm.swap_induction_on {α : Type u} [] [] {P : } (f : ) :
P 1((f : ) → (x y : α) → x yP fP ( * 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.closure_isSwap {α : Type u} [] [] :
theorem Equiv.Perm.swap_induction_on' {α : Type u} [] [] {P : } (f : ) :
P 1((f : ) → (x y : α) → x yP fP (f * )) → 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} [] {w : α} {x : α} {y : α} {z : α} (hwx : w x) (hyz : y z) :
IsConj () ()
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

Instances For
theorem Equiv.Perm.mem_finPairsLT {n : } {a : (_ : Fin n) × Fin 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₂

Instances For
@[simp]
theorem Equiv.Perm.signAux_one (n : ) :
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.

Instances For
theorem Equiv.Perm.signBijAux_inj {n : } {f : Equiv.Perm (Fin n)} (a : (_ : Fin n) × Fin n) (b : (_ : Fin n) × Fin n) :
a = b
theorem Equiv.Perm.signBijAux_surj {n : } {f : Equiv.Perm (Fin n)} (a : (_ : Fin n) × Fin n) :
b _H,
theorem Equiv.Perm.signBijAux_mem {n : } {f : Equiv.Perm (Fin n)} (a : (_ : Fin n) × Fin n) :
@[simp]
theorem Equiv.Perm.signAux_inv {n : } (f : Equiv.Perm (Fin n)) :
theorem Equiv.Perm.signAux_mul {n : } (f : Equiv.Perm (Fin n)) (g : Equiv.Perm (Fin n)) :
theorem Equiv.Perm.signAux_swap {n : } {x : Fin n} {y : Fin n} (_hxy : x y) :
= -1
def Equiv.Perm.signAux2 {α : Type u} [] :
List α

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

Equations
Instances For
theorem Equiv.Perm.signAux_eq_signAux2 {α : Type u} [] {n : } (l : List α) (f : ) (e : α Fin n) (_h : ∀ (x : α), f x xx l) :
Equiv.Perm.signAux ((e.symm.trans f).trans e) =
def Equiv.Perm.signAux3 {α : Type u} [] [] (f : ) {s : } :
(∀ (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.

Instances For
theorem Equiv.Perm.signAux3_mul_and_swap {α : Type u} [] [] (f : ) (g : ) (s : ) (hs : ∀ (x : α), x s) :
Equiv.Perm.signAux3 (f * g) hs = * ∀ (x y : α), x yEquiv.Perm.signAux3 () hs = -1
def Equiv.Perm.sign {α : Type u} [] [] :

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.

Instances For
theorem Equiv.Perm.sign_mul {α : Type u} [] [] (f : ) (g : ) :
Equiv.Perm.sign (f * g) = Equiv.Perm.sign f * Equiv.Perm.sign g
@[simp]
theorem Equiv.Perm.sign_trans {α : Type u} [] [] (f : ) (g : ) :
Equiv.Perm.sign (f.trans g) = Equiv.Perm.sign g * Equiv.Perm.sign f
theorem Equiv.Perm.sign_one {α : Type u} [] [] :
Equiv.Perm.sign 1 = 1
@[simp]
theorem Equiv.Perm.sign_refl {α : Type u} [] [] :
Equiv.Perm.sign () = 1
theorem Equiv.Perm.sign_inv {α : Type u} [] [] (f : ) :
Equiv.Perm.sign f⁻¹ = Equiv.Perm.sign f
@[simp]
theorem Equiv.Perm.sign_symm {α : Type u} [] [] (e : ) :
Equiv.Perm.sign e.symm = Equiv.Perm.sign e
theorem Equiv.Perm.sign_swap {α : Type u} [] [] {x : α} {y : α} (h : x y) :
Equiv.Perm.sign () = -1
@[simp]
theorem Equiv.Perm.sign_swap' {α : Type u} [] [] {x : α} {y : α} :
Equiv.Perm.sign () = if x = y then 1 else -1
theorem Equiv.Perm.IsSwap.sign_eq {α : Type u} [] [] {f : } (h : ) :
Equiv.Perm.sign f = -1
theorem Equiv.Perm.signAux3_symm_trans_trans {α : Type u} {β : Type v} [] [] [] [] (f : ) (e : α β) {s : } {t : } (hs : ∀ (x : α), x s) (ht : ∀ (x : β), x t) :
Equiv.Perm.signAux3 ((e.symm.trans f).trans e) ht =
@[simp]
theorem Equiv.Perm.sign_symm_trans_trans {α : Type u} {β : Type v} [] [] [] [] (f : ) (e : α β) :
Equiv.Perm.sign ((e.symm.trans f).trans e) = Equiv.Perm.sign f
@[simp]
theorem Equiv.Perm.sign_trans_trans_symm {α : Type u} {β : Type v} [] [] [] [] (f : ) (e : α β) :
Equiv.Perm.sign ((e.trans f).trans e.symm) = Equiv.Perm.sign f
theorem Equiv.Perm.sign_prod_list_swap {α : Type u} [] [] {l : List ()} (hl : ∀ (g : ), g l) :
Equiv.Perm.sign () = (-1) ^
theorem Equiv.Perm.sign_surjective (α : Type u) [] [] [] :
Function.Surjective Equiv.Perm.sign
theorem Equiv.Perm.eq_sign_of_surjective_hom {α : Type u} [] [] {s : } (hs : ) :
s = Equiv.Perm.sign
theorem Equiv.Perm.sign_subtypePerm {α : Type u} [] [] (f : ) {p : αProp} [] (h₁ : ∀ (x : α), p x p (f x)) (h₂ : (x : α) → f x xp x) :
Equiv.Perm.sign () = Equiv.Perm.sign f
theorem Equiv.Perm.sign_eq_sign_of_equiv {α : Type u} {β : Type v} [] [] [] [] (f : ) (g : ) (e : α β) (h : ∀ (x : α), e (f x) = g (e x)) :
Equiv.Perm.sign f = Equiv.Perm.sign g
theorem Equiv.Perm.sign_bij {α : Type u} {β : Type v} [] [] [] [] {f : } {g : } (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 yx hx, i x hx = y) :
Equiv.Perm.sign f = Equiv.Perm.sign g
theorem Equiv.Perm.prod_prodExtendRight {β : Type v} {α : Type u_1} [] (σ : α) {l : List α} (hl : ) (mem_l : ∀ (a : α), a l) :
List.prod (List.map (fun a => ) l) =

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

@[simp]
theorem Equiv.Perm.sign_prodExtendRight {α : Type u} {β : Type v} [] [] [] [] (a : α) (σ : ) :
Equiv.Perm.sign () = Equiv.Perm.sign σ
theorem Equiv.Perm.sign_prodCongrRight {α : Type u} {β : Type v} [] [] [] [] (σ : α) :
Equiv.Perm.sign () = Finset.prod Finset.univ fun k => Equiv.Perm.sign (σ k)
theorem Equiv.Perm.sign_prodCongrLeft {α : Type u} {β : Type v} [] [] [] [] (σ : α) :
Equiv.Perm.sign () = Finset.prod Finset.univ fun k => Equiv.Perm.sign (σ k)
@[simp]
theorem Equiv.Perm.sign_permCongr {α : Type u} {β : Type v} [] [] [] [] (e : α β) (p : ) :
Equiv.Perm.sign (↑() p) = Equiv.Perm.sign p
@[simp]
theorem Equiv.Perm.sign_sumCongr {α : Type u} {β : Type v} [] [] [] [] (σa : ) (σb : ) :
Equiv.Perm.sign () = Equiv.Perm.sign σa * Equiv.Perm.sign σb
@[simp]
theorem Equiv.Perm.sign_subtypeCongr {α : Type u} [] [] {p : αProp} [] (ep : Equiv.Perm { a // p a }) (en : Equiv.Perm { a // ¬p a }) :
Equiv.Perm.sign () = Equiv.Perm.sign ep * Equiv.Perm.sign en
@[simp]
theorem Equiv.Perm.sign_extendDomain {α : Type u} {β : Type v} [] [] [] [] (e : ) {p : βProp} [] (f : α ) :
Equiv.Perm.sign () = Equiv.Perm.sign e
@[simp]
theorem Equiv.Perm.sign_ofSubtype {α : Type u} [] [] {p : αProp} [] (f : ) :
Equiv.Perm.sign (Equiv.Perm.ofSubtype f) = Equiv.Perm.sign f