TheoremStatement: AI-adaptedProof: 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.

Relative position classifies pairs of complete flags

Statement

Let $n \geq 1$ , let $q$ be a prime power, put $V = F_{q}^{n}$ and $G = {GL}_{n} (F_{q})$ , let $X$ be the set of complete flags $0 = F_{0} < F_{1} < \dots < F_{n} = V$ with $\dim_{F_{q}} F_{i} = i$ , and let $V_{∙}$ be the standard flag with $V_{i} = ⟨ e_{1}, \dots, e_{i} ⟩$ , so that the stabiliser of $V_{∙}$ is the standard Borel subgroup $B$ and $G$ acts on $X$ by componentwise transport (Complete flags are G/B). Write $\overline{F} : = h V_{∙}$ for the flag with components $h V_{i}$ and consider the diagonal action of $G$ on $X \times X$ . Then:

Invariant. The assignment $Ψ (\overline{h}, \overline{g}) : = B h^{- 1} g B for (\overline{h}, \overline{g}) : = (h V_{∙}, g V_{∙}) \in X \times X,$ is a well-defined $G$ -invariant map $Ψ : X \times X \to B \ G / B$ , and its fibres are exactly the diagonal $G$ -orbits; composing with the Bruhat bijection $σ \mapsto B P_{σ} B$ of Bruhat decomposition of GL_n over a finite field therefore gives a bijection from the set of diagonal orbits on $X \times X$ onto $S_{n}$ . The permutation $σ (F, E) \in S_{n}$ attached to a pair is its relative position.
Intersection dimensions. For $x \in G$ and all $1 \leq i, j \leq n$ , $\dim_{F_{q}} (V_{i} \cap x V_{j}) = j - r_{i + 1, j} (x),$ where $r_{i + 1, j} (x)$ is the rank of the submatrix of $x$ on the rows $i + 1, \dots, n$ and the columns $1, \dots, j$ , with the convention $r_{n + 1, j} (x) : = 0$ . Consequently for a pair with $\overline{h}, \overline{g}$ and all $i, j$ $\dim_{F_{q}} (F_{i} \cap E_{j}) = j - r_{i + 1, j} (h^{- 1} g);$ in particular, if $F = V_{∙}$ is the standard flag and $E = g V_{∙}$ , then $\dim_{F_{q}} (V_{i} \cap E_{j}) = j - r_{i + 1, j} (g)$ : the southwest ranks of a matrix sending the standard flag to $E$ compute the intersection dimensions.
Complete invariant. Two pairs $(\overline{h}, \overline{g})$ and $(\overline{h^{'}}, \overline{g^{'}})$ lie in the same diagonal $G$ -orbit if and only if $\dim (F_{i} \cap E_{j}) = \dim (F_{i}^{'} \cap E_{j}^{'})$ for all $i, j$ , if and only if $h^{- 1} g$ and $h^{' - 1} g^{'}$ have the same southwest rank matrix; in particular the intersection dimensions determine the relative position $σ (F, E)$ . The diagonal orbits, the relative positions and the double cosets $B x B$ are thus in canonical bijection.

Facts & Assumptions

Given: An integer $n \geq 1$ , a prime power $q$ , the space $V = F_{q}^{n}$ with its standard basis $e_{1}, \dots, e_{n}$ and standard flag $V_{0} ⊊ V_{1} ⊊ \dots ⊊ V_{n} = V$ , the group $G = {GL}_{n} (F_{q})$ with standard Borel subgroup $B$ , the set $X$ of complete flags of $V$ , and the diagonal action of $G$ on $X \times X$ .

[L1]

$G$ acts on $X$ by $g \cdot F = (g (F_{0}), \dots, g (F_{n}))$ , the standard flag $V_{∙}$ is complete with $\dim_{F_{q}} V_{i} = i$ , its stabiliser is $B$ , and $g B \mapsto g \cdot V_{∙}$ is a $G$ -equivariant bijection $G / B \to X$ (Complete flags are G/B).

[L2]

$G = ⨆_{σ \in S_{n}} B P_{σ} B$ and $σ \mapsto B P_{σ} B$ is a bijection from $S_{n}$ onto the set of double cosets $B x B$ (Bruhat decomposition of GL_n over a finite field).

[L3]

For $x \in M_{n} (F_{q})$ and $1 \leq i, j \leq n$ let $r_{i, j} (x)$ be the rank of the submatrix on the rows $i, \dots, n$ and the columns $1, \dots, j$ . Then $r_{i, j} (b x) = r_{i, j} (x) = r_{i, j} (x b)$ for $b \in B$ , if $x \in B P_{σ} B$ then $r_{i, j} (x) = # {k \leq j : σ (k) \geq i}$ , and, for $x \in G$ , the rank matrix $(r_{i, j} (x))_{1 \leq i, j \leq n}$ determines $σ$ and hence the double coset $B x B$ (Southwest rank matrices determine Bruhat cells).

[L4]

$V_{i} = ⟨ e_{1}, \dots, e_{i} ⟩$ , $\dim_{F_{q}} V_{i} = i$ and $V_{i - 1} ⊊ V_{i}$ , and $e_{1}, \dots, e_{n}$ is an ordered basis of $V$ (Standard subgroups of finite general linear groups, The standard list $e : n \to F^{n}$ with $e_{i} (i) = 1_{F}$ and $e_{i} (j) = 0_{F}$ for $j \neq i$ is an ordered basis of $F^{n}$ ; hence $\dim_{F} F^{n} = n$ , and $F^{0}$ is the zero space with basis $\emptyset$ and dimension $0$ , Basis of a vector space: a linearly independent spanning subset; and ordered basis: an injective finite list whose image is a basis).

[L5]

For finite-dimensional linear subspaces $U, W$ of a vector space over a field one has $\dim_{F} (U + W) + \dim_{F} (U \cap W) = \dim_{F} U + \dim_{F} W$ (The dimension formula: for finite-dimensional linear subspaces $U$ and $W$ of $V$ , the subspaces $U + W$ and $U \cap W$ are finite-dimensional and $\dim_{F} (U + W) + \dim_{F} (U \cap W) = \dim_{F} U + \dim_{F} W$ ).

[L6]

If $V$ is finite-dimensional and $W \leq V$ is a linear subspace, then $\dim_{F} (V / W) = \dim_{F} V - \dim_{F} W$ (A quotient basis lifts to a basis adapted to $W$ ), and a linearly independent subset of a finite-dimensional space is contained in a basis (If $\dim_{F} V = n$ and $U$ is a linear subspace of $V$ , then $U$ is finite-dimensional, $\dim_{F} U \leq n$ , and $\dim_{F} U = n$ if and only if $U = V$ ).

[L7]

For ordered bases $B$ of $V$ and $C$ of $W$ the matrix $[T]_{B}^{C}$ of a linear map $T : V \to W$ has as its $j$ -th column the coordinate column of $T (b_{j})$ (Coordinate columns $[v]_{B}$ and matrices $[T]_{B}^{C}$ of linear maps relative to ordered bases).

[L8]

For a matrix $A$ over a field, the rank is the dimension of its column space and equals the dimension of its row space (Row space, column space, nullspace, row rank, column rank and matrix rank).

[L9]

A function $f : A \to B$ is injective when $f (x) = f (y)$ implies $x = y$ , surjective when every $b \in B$ equals $f (x)$ for some $x \in A$ , and bijective when it is both; $f [S]$ denotes the image of $S$ under $f$ and $f^{- 1} [T]$ its preimage (Injection, surjection, bijection). An invertible linear map, called a linear isomorphism, satisfies two inverse equations that make it bijective (Invertible linear maps, linear isomorphisms, and inverse linear maps).

[L10]

A finite list $v_{0}, \dots, v_{m - 1}$ of vectors is linearly independent when every list of scalars with $\sum_{i} λ_{i} v_{i} = 0$ has all $λ_{i} = 0$ , and a basis is a linearly independent spanning set (Linear independence: a finite list $v : n \to V$ is independent when $\sum_{i < n} λ_{i} v_{i} = 0_{V}$ forces every $λ_{i} = 0_{F}$ , and a subset $S \subseteq V$ is independent when every injective finite list into $S$ is independent, Basis of a vector space: a linearly independent spanning subset; and ordered basis: an injective finite list whose image is a basis).

Proof

technique · direct

1.1

Well-definedness of $Ψ$ . Suppose $h V_{∙} = h^{'} V_{∙}$ and $g V_{∙} = g^{'} V_{∙}$ in $X$ . Then $h^{- 1} h^{'}$ stabilises every $V_{i}$ , hence $h^{- 1} h^{'} \in B$ by [L1], so $h^{'} = h b$ with $b \in B$ ; likewise $g^{'} = g c$ with $c \in B$ . Therefore $h^{' - 1} g^{'} = b^{- 1} h^{- 1} g c \in B (h^{- 1} g) B$ , so $B h^{' - 1} g^{'} B = B h^{- 1} g B$ : the class $Ψ (\overline{h}, \overline{g})$ does not depend on the chosen representatives.

1.2

A quotient identification. Fix $x \in G$ and $1 \leq i, j \leq n$ , and let $φ : F_{q}^{j} \to V / V_{i}$ be the linear map $φ (v) : = x (v, 0) + V_{i}$ , where $(v, 0) \in F_{q}^{n}$ denotes $v$ placed in the first $j$ coordinates. Its image is ${x v + V_{i} : v \in F_{q}^{j}} = (x V_{j} + V_{i}) / V_{i}$ , so by [L6], [L5] and $\dim_{F_{q}} V_{i} = i$ of [L4] we have $\dim_{F_{q}} im φ = \dim_{F_{q}} (x V_{j} + V_{i}) - \dim_{F_{q}} V_{i} = i + j - \dim_{F_{q}} (V_{i} \cap x V_{j}) - i = j - \dim_{F_{q}} (V_{i} \cap x V_{j})$ , where $\dim_{F_{q}} x V_{j} = j$ because $x$ is bijective by [L9] and $x V_{j}$ is the image of $V_{j}$ . The images $e_{i + 1} + V_{i}, \dots, e_{n} + V_{i}$ of the basis vectors of [L4] form a basis of $V / V_{i}$ : they span, because $e_{1}, \dots, e_{i}$ lie in $V_{i}$ , so the class of every $v$ lies in their span; and they are linearly independent, because a relation $\sum_{k > i} c_{k} (e_{k} + V_{i}) = 0$ means $\sum_{k > i} c_{k} e_{k} \in V_{i} \cap ⟨ e_{i + 1}, \dots, e_{n} ⟩ = {0}$ , by [L4] and [L10]. Therefore, by [L7], the matrix of $φ$ with respect to the standard basis of $F_{q}^{j}$ and this basis of $V / V_{i}$ is the submatrix of $x$ on the rows $i + 1, \dots, n$ and the columns $1, \dots, j$ , whose rank equals $\dim_{F_{q}} im φ$ by [L8]. Comparing the two computations gives $\dim_{F_{q}} (V_{i} \cap x V_{j}) = j - r_{i + 1, j} (x)$ for $i \leq n - 1$ , and for $i = n$ both sides equal $j$ because $V_{n} = V$ and $r_{n + 1, j} (x) = 0$ by the convention of the statement.

L4L5L6L7L8L9L10

2.1

$G$ -invariance. For $γ \in G$ the representatives $γ h, γ g$ give $(γ h)^{- 1} (γ g) = h^{- 1} γ^{- 1} γ g = h^{- 1} g$ , so $Ψ (γ \cdot \overline{h}, γ \cdot \overline{g}) = Ψ (\overline{h}, \overline{g})$ : the map $Ψ$ is constant on diagonal orbits. It is surjective, since $Ψ (V_{∙}, x V_{∙}) = B x B$ for every $x \in G$ .

step 1.1L1

2.2

Pairs of flags. Let $(\overline{h}, \overline{g}) \in X \times X$ and $1 \leq i, j \leq n$ . The invertible linear map $h^{- 1}$ satisfies $h^{- 1} (F_{i} \cap E_{j}) = V_{i} \cap h^{- 1} g V_{j}$ , and it preserves dimensions by [L9]; hence by step 1.2 with $x : = h^{- 1} g$ we get $\dim_{F_{q}} (F_{i} \cap E_{j}) = j - r_{i + 1, j} (h^{- 1} g)$ . For $F = V_{∙}$ the representative may be taken to be $h = I_{n}$ , so $\dim_{F_{q}} (V_{i} \cap E_{j}) = j - r_{i + 1, j} (g)$ for any $g \in G$ with $g V_{∙} = E$ .

step 1.2L1L9

3.1

The fibres of $Ψ$ are the orbits. Suppose $Ψ (\overline{h}, \overline{g}) = Ψ (\overline{h^{'}}, \overline{g^{'}})$ , that is $B h^{- 1} g B = B h^{' - 1} g^{'} B$ . Then $h^{' - 1} g^{'} = b_{1} h^{- 1} g b_{2}$ for some $b_{1}, b_{2} \in B$ , so $b_{1} h^{- 1} g = h^{' - 1} g^{'} b_{2}^{- 1}$ . Put $ρ : = h^{'} b_{1} h^{- 1} \in G$ . Then $ρ h = h^{'} b_{1}$ , so $ρ (h V_{∙}) = h^{'} (b_{1} V_{∙}) = h^{'} V_{∙}$ because $b_{1}$ stabilises $V_{∙}$ by [L1]; and $ρ g = h^{'} b_{1} h^{- 1} g = h^{'} (h^{' - 1} g^{'} b_{2}^{- 1}) = g^{'} b_{2}^{- 1}$ , so $ρ (g V_{∙}) = g^{'} V_{∙}$ as well. Hence $(\overline{h^{'}}, \overline{g^{'}}) = ρ \cdot (\overline{h}, \overline{g})$ lies in the same diagonal orbit. Together with step 2.1 this shows that two pairs have the same image under $Ψ$ exactly when they lie in the same diagonal orbit.

step 1.1step 2.1L1

4.1

The dimension function is a complete invariant. Suppose $\dim (F_{i} \cap E_{j}) = \dim (F_{i}^{'} \cap E_{j}^{'})$ for all $i, j$ . By step 2.2 the rank matrices of $x : = h^{- 1} g$ and $x^{'} : = h^{' - 1} g^{'}$ satisfy $r_{i + 1, j} (x) = j - \dim (F_{i} \cap E_{j}) = j - \dim (F_{i}^{'} \cap E_{j}^{'}) = r_{i + 1, j} (x^{'})$ for all $i, j$ ; since $r_{n + 1, j} = 0$ is fixed by the convention of the statement and $r_{1, j} (x) = r_{1, j} (x^{'}) = j$ because $x, x^{'}$ are invertible, this determines the whole southwest rank matrix of [L3], so $x$ and $x^{'}$ lie in one double coset $B x B = B x^{'} B$ by [L3]. Then step 3.1 shows that the two pairs lie in the same diagonal orbit. Conversely, if the pairs lie in the same orbit, say $(\overline{F^{'}}, \overline{E^{'}}) = γ \cdot (\overline{F}, \overline{E})$ with $γ \in G$ , then $F_{i}^{'} = γ F_{i}$ and $E_{j}^{'} = γ E_{j}$ , so $F_{i}^{'} \cap E_{j}^{'} = γ (F_{i} \cap E_{j})$ and the dimensions agree by [L9].

step 2.2step 3.1L3L9

5.1

By step 4.1 the fibres of the composite assignment (pair $\mapsto$ intersection-dimension function $\mapsto$ southwest rank matrix $\mapsto$ double coset) are exactly the diagonal orbits, and by step 3.1 the fibres of $Ψ$ are the same orbits; the Bruhat decomposition [L2] identifies the double cosets $B x B$ bijectively with $S_{n}$ through $σ \mapsto B P_{σ} B$ . Hence $σ (F, E)$ is well defined, is determined by the intersection dimensions $\dim (F_{i} \cap E_{j})$ , and classifies the diagonal $G$ -orbits on $X \times X$ . In particular, when $F = V_{∙}$ the southwest rank matrix of the single matrix $g$ with $E = g V_{∙}$ determines $σ$ by [L3], while two choices $g, g^{'}$ with $g V_{∙} = g^{'} V_{∙}$ differ by right multiplication by an element of $B$ and give the same rank matrix by the first assertion of [L3]. ∎

step 1.1step 2.1step 3.1step 4.1L2L3

Remark. The relative position is the analogue for complete flags of the Bruhat index of a matrix: the double coset $B h^{- 1} g B$ records how the two flags are positioned, and the intersection dimensions $\dim (F_{i} \cap E_{j})$ are the coordinate-free form of the southwest rank matrix. The dimension identity of step 1.2 is the only place where the direction of the picture enters: the ranks are taken on the rows $i + 1, \dots, n$ , so the formula pairs the prefix flag $V_{j}$ with the suffix quotient $V / V_{i}$ .

Depends on

Used by

Dependency tree · two levels

71 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)