PropositionStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-09-27

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Cardinality of a finite Bruhat cell

Statement

Let $n \geq 1$ , let $q$ be a prime power, put $G = {GL}_{n} (F_{q})$ with standard Borel subgroup $B$ , standard torus $T$ and standard unipotent subgroup $U$ , and for $σ \in S_{n}$ let $w : = P_{σ}$ be the permutation matrix and $ℓ (σ)$ the number of inversions of $σ$ (Permutation Weyl group and inversion length), so that $G = ⨆_{σ \in S_{n}} B w B$ is the Bruhat decomposition (Bruhat decomposition of GL_n over a finite field). Then for every $σ \in S_{n}$ :

the cell $B w B$ is a union of exactly $∣ B w B / B ∣ = q^{ℓ (σ)}$ left cosets of $B$ ;
consequently $∣ B w B ∣ = ∣ B ∣ q^{ℓ (σ)} = (q - 1)^{n} q^{n (n - 1) / 2 + ℓ (σ)}$ , so the Bruhat decomposition writes $∣ G ∣$ as $\sum_{σ \in S_{n}} (q - 1)^{n} q^{n (n - 1) / 2 + ℓ (σ)}$ : the cells are indexed by $W$ , and their numbers of left $B$ -cosets are the powers $q^{ℓ (σ)}$ .

Facts & Assumptions

Given: An integer $n \geq 1$ , a prime power $q$ , the group $G = {GL}_{n} (F_{q})$ with standard Borel subgroup $B$ , standard torus $T$ and standard unipotent subgroup $U$ , and a permutation $σ \in S_{n}$ with permutation matrix $w : = P_{σ}$ and length $ℓ (σ)$ .

[L1]

$B = {b \in G : b is upper triangular}$ is a subgroup of $G$ with $B = T ⋉ U$ ; $U$ is the set of unitriangular matrices, $T$ the set of invertible diagonal matrices, and $∣ U ∣ = q^{n (n - 1) / 2}$ , $∣ T ∣ = (q - 1)^{n}$ , $∣ B ∣ = (q - 1)^{n} q^{n (n - 1) / 2}$ (Standard subgroups of finite general linear groups).

[L2]

$G = ⨆_{σ \in S_{n}} B P_{σ} B$ , and since $B$ is a subgroup each $B P_{σ} B$ is a union of left cosets $b B$ (Bruhat decomposition of GL_n over a finite field).

[L3]

For $σ \in S_{n}$ the permutation matrix satisfies $(P_{σ})_{i j} = 1$ exactly when $i = σ (j)$ and $P_{σ} P_{τ} = P_{σ τ}$ , so $P_{σ^{- 1}} w = I_{n}$ (Permutation Weyl group and inversion length).

[L4]

The length $ℓ (σ) = # Inv (σ)$ counts the pairs $i < j$ with $σ (i) > σ (j)$ , and $ℓ (σ^{- 1}) = ℓ (σ)$ (Permutation Weyl group and inversion length).

[L5]

If $G$ is a finite group and $H \leq G$ , then $∣ G ∣ = [G : H] ∣ H ∣$ , where the index $[G : H]$ is the number of left cosets of $H$ in $G$ (Lagrange's theorem: $∣ G ∣ = [G : H] ∣ H ∣$ for every subgroup $H$ of a finite group $G$ , The coset set $G / H$ and the index $[G : H]$ of a subgroup).

[L6]

Matrix products satisfy $(X Y)_{i j} = \sum_{k} X_{i k} Y_{k j}$ and $I_{n}$ has entries $δ_{i j}$ (Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes, Matrix multiplication is associative, unital, distributive, and compatible with scalar multiplication).

[L7]

A matrix is upper triangular when $a_{i j} = 0$ for $i > j$ ; a unitriangular matrix is an upper triangular matrix with all diagonal entries equal to $1$ (Upper triangular, lower triangular and diagonal square matrices over a commutative ring, Standard subgroups of finite general linear groups).

[L9]

If $A_{0}, \dots, A_{m - 1}$ are finite sets then $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ (The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ ), and the field $F_{q}$ has exactly $q$ elements (Finite fields and their order).

Proof

technique · direct

1.1

Conjugation by $w$ . For every $b \in M_{n} (F_{q})$ and all $i, j$ the product formula of [L6] together with the entries $(P_{σ})_{i j} = δ_{i, σ (j)}$ and $(P_{σ^{- 1}})_{i j} = δ_{i, σ^{- 1} (j)}$ of [L3] give $(w^{- 1} b w)_{i j} = b_{σ (i), σ (j)}$ : in the sum $\sum_{k, l} (w^{- 1})_{i k} b_{k l} w_{l j}$ the only nonzero term has $k = σ (i)$ and $l = σ (j)$ . In particular $(w^{- 1} b w)_{i i} = b_{σ (i), σ (i)}$ , so conjugation by $w$ permutes the diagonal entries.

L3L6

1.2

The coset bijection. Put $C : = B \cap w B w^{- 1}$ , a subgroup of the group $B$ of [L1], and define $ψ : B / C \to B w B / B$ by $ψ (b C) : = b w B$ . This is well defined: if $b C = b^{'} C$ , then $b^{' - 1} b \in C \subseteq w B w^{- 1}$ , so $(b^{'} w)^{- 1} (b w) = w^{- 1} b^{' - 1} b w \in B$ , that is $b w B = b^{'} w B$ . It is injective: $b w B = b^{'} w B$ means $w^{- 1} b^{' - 1} b w \in B$ , while $b^{' - 1} b \in B$ because $B$ is a group, so $b^{' - 1} b \in C$ and $b C = b^{'} C$ . It is surjective: every element of $B w B$ is $b_{1} w b_{2}$ with $b_{1}, b_{2} \in B$ , and $b_{1} w b_{2} B = b_{1} w B$ because $b_{2} B = B$ . Hence the number of left cosets of $B$ inside the cell is $∣ B w B / B ∣ = ∣ B / C ∣ = [B : C]$ .

L1L2

2.1

The index lives in $U$ . Put $K : = U \cap w U w^{- 1}$ and note $w T w^{- 1} = T$ , so $T \subseteq C$ . An element $b = t u$ of $B$ with $t \in T$ , $u \in U$ (unique form by [L1]) lies in $w B w^{- 1}$ if and only if $u = t^{- 1} b$ does, because $t \in w B w^{- 1}$ and $w B w^{- 1}$ is a subgroup; hence $C = T \cdot K$ . Indeed, if $u \in U$ and $w^{- 1} u w \in B$ , then $w^{- 1} u w$ is upper triangular with $(i, i)$ entry $1$ by step 1.1, hence unitriangular by [L7], so $u \in w U w^{- 1}$ ; the reverse inclusion $K \subseteq C$ is clear because $U \subseteq B$ and $w U w^{- 1} \subseteq w B w^{- 1}$ . Consequently the map $U / K \to B / C$ , $u K \mapsto u C$ , is a bijection: it is well defined since $K \subseteq C$ ; it is injective because $u C = u^{'} C$ forces $u^{' - 1} u \in C \cap U = K$ ; and it is surjective because $t u C = (t u t^{- 1}) C$ with $t u t^{- 1} \in U$ by [L1] and $t \in T \subseteq C$ . Therefore $[B : C] = [U : K]$ .

step 1.1L1L3L6L7

2.2

Description of $K$ . By step 1.1 an element $u \in U$ lies in $K = U \cap w U w^{- 1}$ if and only if $w^{- 1} u w$ is unitriangular, that is, if and only if $u$ is unitriangular and $u_{σ (i), σ (j)} = 0$ for all $i > j$ ; writing $a = σ (i)$ and $b = σ (j)$ this says $u_{a b} = 0 whenever a > b or (a < b and σ^{- 1} (a) > σ^{- 1} (b)),$ the first alternative being the unitriangular condition of [L7] and the second the condition coming from $i > j$ .

step 1.1L3L7

3.1

Cardinality of $K$ . A set of matrices whose entries are constrained only by fixing some entries to $0$ or $1$ and leaving $m$ off-diagonal entries free has exactly $q^{m}$ elements, since each free entry ranges over the field $F_{q}$ of $q$ elements and the choices are independent, by [L9]. By step 2.2 the free entries of $u \in K$ are the entries $u_{a b}$ with $a < b$ and $σ^{- 1} (a) < σ^{- 1} (b)$ , the non-inversions of the permutation $σ^{- 1}$ ; all other entries are forced. Among the $(\binom{n}{2})$ pairs $a < b$ , $σ^{- 1}$ has $(\binom{n}{2}) - ℓ (σ^{- 1}) = (\binom{n}{2}) - ℓ (σ)$ non-inversions by [L4]. Hence $∣ K ∣ = q^{(\binom{n}{2}) - ℓ (σ)}$ .

step 2.2L4L9

4.1

By [L5] applied to the subgroup $K$ of $U$ , whose order is $∣ U ∣ = q^{(\binom{n}{2})}$ by [L1], the index of $K$ in $U$ is $[U : K] = ∣ U ∣ / ∣ K ∣ = q^{(\binom{n}{2})} q^{- ((\binom{n}{2}) - ℓ (σ))} = q^{ℓ (σ)}$ . By step 2.1 this equals $[B : C]$ , and by step 1.2 it equals $∣ B w B / B ∣$ , which is claim 1. Multiplying by $∣ B ∣ = (q - 1)^{n} q^{(\binom{n}{2})}$ from [L1] gives $∣ B w B ∣ = ∣ B ∣ q^{ℓ (σ)} = (q - 1)^{n} q^{(\binom{n}{2}) + ℓ (σ)}$ , and summing over the disjoint cells of [L2] gives $∣ G ∣ = \sum_{σ \in S_{n}} (q - 1)^{n} q^{(\binom{n}{2}) + ℓ (σ)}$ , which is claim 2. ∎

step 1.2step 2.1step 3.1L1L2L5

Remark. The left cosets of $B$ inside $B w B$ are the $B$ -orbit of the coset $w B$ in $G / B$ , so $q^{ℓ (σ)}$ is the number of complete flags in the $B$ -orbit of $w V_{∙}$ ; the torus contributes the constant factor $(q - 1)^{n}$ , and the entire dependence on $σ$ is carried by the unipotent subgroup, through the index $[U : U \cap w U w^{- 1}]$ . All these are finite cardinalities of explicit matrix sets, so no choice principle is used.

Depends on

Used by

Flags and Bruhat cells for GL₂(F_q) Example
GL₁ and the trivial parabolic endpoints Example

Dependency tree · two levels

47 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Olivier Dudas and Jean Michel, Lectures on Finite Reductive Groups and Their Representations - Example 4.5 and Lemma 4.7, printed p. 18 (standard reference, not scraped)
Jay Taylor, Finite Reductive Groups - Exercise 4.28, printed pp. 38-39 (standard reference, not scraped)