  Transforming a matrix over a field to echelon form, or decomposing the matrix
as a product of structured matrices that reveal the rank profile, is a
fundamental building block of computational exact linear algebra. This paper
surveys the well known variations of such decompositions and transformations
that have been proposed in the literature. We present an algorithm to compute
the CUP decomposition of a matrix, adapted from the LSP algorithm of Ibarra,
Moran and Hui (1982), and show reductions from the other most common Gaussian
elimination based matrix transformations and decompositions to the CUP
decomposition. We discuss the advantages of the CUP algorithm over other
existing algorithms by studying time and space complexities: the asymptotic
time complexity is rank sensitive, and comparing the constants of the leading
terms, the algorithms for computing matrix invariants based on the CUP
decomposition are always at least as good except in one case. We also show that
the CUP algorithm, as well as the computation of other invariants such as
transformation to reduced column echelon form using the CUP algorithm, all work
in place, allowing for example to compute the inverse of a matrix on the same
storage as the input matrix.
