The Rank of Recurrence Matrices