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.

enter image description here

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

  • $\begingroup$ 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. $\endgroup$
    – Shuzheng
    Jun 3 '14 at 7:51
  • $\begingroup$ 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. $\endgroup$ Nov 14 '18 at 0:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.