# 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. • Thanks, but is this the same statement ? - one of the matrices is unipotent lower triangular and there is also a diagonal matrix ? – Shuzheng Apr 18 '14 at 15:23
• I will give it a try. Thank you. – Shuzheng Apr 18 '14 at 20:09
• This is the so-called Bruhat decomposition in the algebraic group $\operatorname{GL}_n$. – darij grinberg Nov 14 '18 at 0:11

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 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, 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 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.

• Thank you @Ewan ! I didn't knew the proof was this hard. The exercise is given in a basic course of Linear Algebra for people that haven't taken any Algebra course yet. Anyways I thank you for your answer. – Shuzheng Jun 3 '14 at 7:51
• I've taken the liberty to remove a parenthetical which was IMHO confusing: Being $r$-normalized requires more than just some submatrix being the identity. – darij grinberg Nov 14 '18 at 0:27