If $A \in M_{n,n}(\mathbb F)$ is invertible then $A = UPB$, $U$ is unipotent upper triangular, $B$ is upper triangular and $P$ is a permutation.

Let $\mathbb{F}$ be a field. If $A \in M_{n,n}(\mathbb F)$ is invertible, then $A$ can be written as $A = UPB$, where $U$ is unipotent upper triangular, $B$ is upper triangular and $P$ a permutation matrix.

• A hint is given that one could relate the problem to elementary row and column operations.

I know that if $A$ is invertible then we can row reduce $A$ to $I_n$ and this corresponds to a sequence of elementary matrices $E_1, \ldots, E_n$.

Also, $A=UPB$ would imply $\det(A) = \det(U) \det(P) \det(B)$, which in turn implies that the diagonal entries of $B$ must be nonzero.

I guess that the permutation matrix corresponds to column exchange.

This is a twist to the standard Gauss reduction which produces one lower triangular and one upper triangular factor.

Denote by $E_{ij}$ the matrix all of whose coefficients are zero except the one at the intersection of the $i$-th line and the $j$-th column, set equal to $1$. Denote by $T_{ij}(\lambda)$ the transvection matrix $I_n+\lambda E_{ij}$, and by $R_i(\lambda)$ the rescaling matrix $I_n+(\lambda-1)E_{ii}$. Denote by $\cal T$ the group of upper triangular invertible matrices, and by $\cal U$ the subgroup of $\cal T$ consisting of the unipotent ones.

For any invertible $A$, ${\cal C}={\cal U}A{\cal T}$ is a two-sided coset on which $\cal U$ acts on the left and $\cal T$ acts on the right. We are looking for a permutation matrix inside $\cal C$.

Given $0\leq r\leq n$, say that a matrix $A=(a_{ij})$ is $r$-normalized iff there are distinct indices $i_1<i_2<\ldots<i_r$ such that for any $k\in\lbrace 1,2,\ldots,r \rbrace$, the $i_k$-th line has all its entries equal to zero except for the $k$-th one, equal to $1$, and the $k$-th column has all its entries equal to zero except for the $i_k$-th one, equal to $1$.

Thus, any matrix is $0$-normalized, and a $n$-normalized matrix is the same thing as a permutation matrix. Using induction, it will therefore suffice to show the following lemma :

Lemma If $A$ is a $r$-normalized matrix with $r<n$, then its coset ${\cal C}={\cal U}A{\cal T}$ contains a $(r+1)$-normalized matrix.

Proof of lemma Consider the $(r+1)$-th column of $A$. We know that all the entries at indices $i_1,\ldots,i_{r}$ are zero. On the other hand, the entries are not all zero since $A$ is invertible. Let then $i_{r+1}$ be the largest index satisfying $a_{i_{r+1},(r+1)} \neq 0$. Multiplying by a suitable rescaling matrix $R_{r+1}(\lambda)$ on the right, we may assume $a_{i_{r+1},(r+1)}=1$. For any $i<i_{r+1}$ with $i\not\in \lbrace i_1,\ldots,i_{r}\rbrace$, multiplying on the left by the transvection $T_{i,i_{r+1}}(\lambda)$ for a suitable $\lambda$, we may assume $a_{i,r+1}=0$. This ensures that the $(r+1)$-th column of $A$ is as we wish it to be. Similarly, for any $j>r+1$, multiplying on the right by the transvection $T_{r+1,j}(\lambda)$ for a suitable $\lambda$, we may assume $a_{i_{r+1},j}=0$. This ensures that the $i_{r+1}$-th line of $A$ is as we wish it to be. Now $A$ is fully $(r+1)$-normalized, which finishes the proof.