  The row (resp. column) rank profile of a matrix describes the stair-case
shape of its row (resp. column) echelon form. We here propose a new matrix
invariant, the rank profile matrix, summarizing all information on the row and
column rank profiles of all the leading sub-matrices. We show that this normal
form exists and is unique over any ring, provided that the notion of McCoy's
rank is used, in the presence of zero divisors. We then explore the conditions
for a Gaussian elimination algorithm to compute all or part of this invariant,
through the corresponding PLUQ decomposition. This enlarges the set of known
Elimination variants that compute row or column rank profiles. As a consequence
a new Crout base case variant significantly improves the practical efficiency
of previously known implementations over a finite field. With matrices of very
small rank, we also generalize the techniques of Storjohann and Yang to the
computation of the rank profile matrix, achieving an $(r^\omega+mn)^{1+o(1)}$
time complexity for an $m \times n$ matrix of rank $r$, where $\omega$ is the
exponent of matrix multiplication. Finally, by give connections to the Bruhat
decomposition, and several of its variants and generalizations. Thus, our
algorithmic improvements for the PLUQ factorization, and their implementations,
directly apply to these decompositions. In particular, we show how a PLUQ
decomposition revealing the rank profile matrix also reveals both a row and a
column echelon form of the input matrix or of any of its leading sub-matrices,
by a simple post-processing made of row and column permutations.
