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.

 A: 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.
