math111_logo Row Echelon Form


Exercise How many shapes of m by n row echelon forms are there?

Answer By the previous exercise, the shapes of row echelon forms can be counted by the pivot columns, which are some numbers between 1 and n. For example, the row echelon form

[ * # # # ]
0 0 * #
0 0 0 0

corresponds to the numbers {1, 3}, which means that [col 1] and [col 3] are pivot columns. Thus we count the number of ways of choosing no more than m numbers from {1, 2, ..., n}. The total number is

C(n,0) + C(n,1) + ... + C(n, min{m,n})

where C(n,s) = n!/s!(n-s)! is the number of ways of choosing s numbers from {1, 2, ..., n}.