Triangular elimination produces a pivot permutation

Write $E_{ab}$ for the matrix with entry $1$ at $(a,b)$ and $0$ elsewhere. For $1\le i<n$ and $\lambda \in {\mathbb{F}}_q$ the matrix $I_n+\lambda E_{in}$ is unitriangular, hence lies in $B$ by [L2]; by the product formula of [L3] left multiplication by it adds $\lambda$ times row $n$ to row $i$ and leaves all other rows unchanged. Likewise for $1\le j<k\le n$ the matrix $I_n+\lambda E_{jk}$ is unitriangular, hence lies in $B$, and right multiplication by it adds $\lambda$ times column $j$ to column $k$ and leaves all other columns unchanged. Finally, for $c\mathrm{\ne }0$ the diagonal matrix $\mathrm{diag}(1,\dots ,1,c^{-1})$ lies in $B$ and scales row $n$ by $c^{-1}$.

Reduction of the last row and its column. Since $g$ is invertible, its last row is nonzero: if it were zero, then $gx=e_n$ would have no solution, contradicting [L4]. Let $j$ be the leftmost column with $g_{nj}\mathrm{\ne }0$ and put $c:=g_{nj}$. First, for $k=j+1,\dots ,n$ multiply on the right by the unitriangular matrix that adds $g_{nk}\mathrm{/}c$ times column $j$ to column $k$ (with the sign chosen so as to cancel the entry); this successively kills every entry of the last row strictly to the right of $j$ and does not change column $j$, so afterwards the last row is $c{e}_j^T$. Second, for $i=1,\dots ,n-1$ multiply on the left by the unitriangular matrix that adds a suitable multiple of row $n$ to row $i$; since row $n$ is $c{e}_j^T$, this only changes the entry $(i,j)$ of the matrix and makes it $0$, leaving the last row and all the zeros in it unchanged. Third, multiply on the left by $\mathrm{diag}(1,\dots ,1,c^{-1})$. All factors lie in $B$ by step 1.1, so the resulting matrix satisfies $M=LgR$ with $L,R\in B$ and has $M_{nb}={\delta }_{bj}$ and $M_{aj}={\delta }_{an}$ for all admissible $a,b$.

Let $C=(c_1<c_2<\cdots <c_{n-1})$ be the increasing list of the elements of $\{1,\dots ,n\}\setminus \{j\}$ and let $A$ be the $(n-1)\times (n-1)$ matrix $A_{ab}:=M_{a,c_b}$ formed from the first $n-1$ rows of $M$ and the columns in $C$. Then $A$ is invertible: if $Av=0$ with $v\mathrm{\ne }0$ and $x\in {\mathbb{F}}_q^n$ is the vector with $x_{c_b}:=v_b$ for all $b$ and $x_j:=0$, then $(Mx{)}_a={\sum }_b{M}_{a,c_b}{v}_b=(Av{)}_a=0$ for $a<n$ by [L3], while $(Mx{)}_n={\sum }_b{M}_{nb}{x}_b=0$ because $M_{nb}={\delta }_{bj}$ and $x_j=0$; thus $Mx=0$ with $x\mathrm{\ne }0$, contradicting the invertibility of $M$ by [L4].

We prove the asserted factorisation by induction on $n$. For $n=1$ every nonzero $g\in G$ is a $1\times 1$ matrix, so $B=G$ and $g=g\cdot I_1\cdot I_1$ is a factorisation with the permutation matrix $I_1=P_{\mathrm{i}\mathrm{d}}$; assume now that $n\ge 2$ and that every invertible matrix of size $n-1$ over ${\mathbb{F}}_q$ admits such a factorisation. Applying this hypothesis to the invertible matrix $A$ of step 3.1 gives $A=b_1^{\mathrm{\prime }}{P}_{{\sigma }^{\mathrm{\prime }}}{b}_2^{\mathrm{\prime }}$ with $b_1^{\mathrm{\prime }},b_2^{\mathrm{\prime }}$ upper triangular matrices of size $n-1$ and ${\sigma }^{\mathrm{\prime }}\in \mathrm{Sym}(\{1,\dots ,n-1\})$.

Separate triangular extensions. Let $L$ be the block diagonal matrix with upper-left $(n-1)\times (n-1)$ block $b_1^{\mathrm{\prime }}$ and last diagonal entry $1$. Let $R$ fix the $j$-th coordinate and act on the coordinates indexed by the increasing list $C=(c_1,\dots ,c_{n-1})$ through $b_2^{\mathrm{\prime }}$: explicitly, $R_{c_a,c_b}=(b_2^{\mathrm{\prime }}{)}_{ab}$, $R_{j,j}=1$, and all other entries are zero. Both $L$ and $R$ are invertible and upper triangular. This is immediate for $L$; for $R$, an entry $(b_2^{\mathrm{\prime }}{)}_{ab}\mathrm{\ne }0$ has $a\le b$ and therefore $c_a\le c_b$, and the inverse is obtained by the same extension of $(b_2^{\mathrm{\prime }}{)}^{-1}$. Define $\sigma$ by $\sigma (c_b)={\sigma }^{\mathrm{\prime }}(b)$ for $1\le b<n$ and $\sigma (j)=n$. These assignments give a permutation of $\{1,\dots ,n\}$, and its permutation matrix $P_{\sigma }$ has ones exactly at $({\sigma }^{\mathrm{\prime }}(b),c_b)$ and $(n,j)$ by [L5]. For $a<n$ and $1\le b<n$, the $(a,c_b)$ entry of $L{P}_{\sigma }R$ is $(b_1^{\mathrm{\prime }}{P}_{{\sigma }^{\mathrm{\prime }}}{b}_2^{\mathrm{\prime }}{)}_{ab}=A_{ab}=M_{a,c_b}$; its last row has a single $1$ in column $j$, and its $j$-th column has a single $1$ in row $n$. Thus $M=L{P}_{\sigma }R$ entry by entry.

By step 5.1, $M=L{P}_{\sigma }R$ with $L,R\in B$ and $P_{\sigma }$ a permutation matrix; by step 2.1 also $M=L_{0}g{R}_0$ with $L_0,R_0\in B$. Hence $g=L_0^{-1}L{P}_{\sigma }R{R}_0^{-1}$. Since $B$ is a subgroup of $G$ by [L1], both $L_0^{-1}L$ and $R{R}_0^{-1}$ lie in $B$; writing them as $b_1$ and $b_2$ gives $g=b_1{P}_{\sigma }{b}_2$, as asserted. ∎