"Finding the rank profile of a matrix"
Cheryl Praeger (UWA)
Let $A$ be an $m\times n$ matrix over a field $F$. Suppose that
the first basis for the column space you come across as you traverse the
columns of $A$ from left to right consists of the columns $i_1,\dots,i_r$.
This list of positive integers is called the rank profile of $A$. The rank
profile is useful in several fast matrix algorithms that utilise fast
matrix multiplication, such as finding the characteristic polynomial.
I will describe an algorithm developed from an algorithm of Ibarra, Moran
and Hui that produces the rank profile. It was developed in collaboration
with Sophie Ambrose, and we have come to think that it is rather
beautiful. If there's time I'll indicate how it can be used in finding the
characteristic polynomial.