The other day I ran across a linear algebra problem which asked the reader to enumerate all possible 2x2 and 3x3 row canonical matrices (RCMs, aka row echelon form matrices) with binary entries {0, 1}. For those unfamiliar, a row canonical matrix is a matrix with the following properties: As it turns out there are five 2x2 and sixteen 3x3 matrices of this form:
`[[1,1],[0,0]]` `[[1,0],[0,1]]` `[[1,0],[0,0]]` `[[0,1],[0,0]]` `[[0,0],[0,0]]`
`[[1,1,1],[0,0,0],[0,0,0]]` `[[1,1,0],[0,0,1],[0,0,0]]` `[[1,1,0],[0,0,0],[0,0,0]]` `[[1,0,1],[0,1,1],[0,0,0]]` `[[1,0,1],[0,1,0],[0,0,0]]` `[[1,0,1],[0,0,0],[0,0,0]]` `[[1,0,0],[0,1,1],[0,0,0]]` `[[1,0,0],[0,1,0],[0,0,1]]` `[[1,0,0],[0,1,0],[0,0,0]]` `[[1,0,0],[0,0,1],[0,0,0]]` `[[1,0,0],[0,0,0],[0,0,0]]` `[[0,1,1],[0,0,0],[0,0,0]]` `[[0,1,0],[0,0,1],[0,0,0]]` `[[0,1,0],[0,0,0],[0,0,0]]` `[[0,0,1],[0,0,0],[0,0,0]]` `[[0,0,0],[0,0,0],[0,0,0]]`

This problem gave me the hankering to develop a formula to determine the number of RCMs with binary entries for a square matrix of order N. The first order of business in this endeavour was to develop a program to count the number of RCMs with binary entries of order N to see if there was an obvious pattern and spot-check the formula once completed.
public class RowCanonicalForm {
	public static void main(String...args) {
		for(int n = 1; n < 10; System.out.println(n + "x" + n + ": " + populate(new boolean[n][n++], 0, 0)));
	}
	
	private static int populate(boolean[][] matrix, int i, int j) {
		if (!isRowCanonicalForm(matrix)) return 0;
		if (j == matrix.length) {i++; j = 0;}
		if (i == matrix.length) return 1;
		return populate(matrix, true, i, j) + populate(matrix, false, i, j);
	}
	
	private static int populate(boolean[][] matrix, boolean value, int i, int j) {
		matrix[i][j] = value;
		return populate(matrix, i, j+1);
	}

	private static boolean isRowCanonicalForm(boolean[][] matrix) {
		int minZeroRow = Integer.MAX_VALUE, maxNonZeroRow = 0;
		Integer pivot = null, lastPivot = null;
		for(int i = 0; i < matrix.length; i++) {
			pivot = null;
			for(int j = 0; j < matrix.length; j++) {
				if (matrix[i][j]) {
					if (i >= 1 && (((lastPivot==null)?Integer.MAX_VALUE-1:lastPivot) >= j)) return false;
					for(int i2 = 0; i2 < matrix.length; i2++) if ((i2 != i) && matrix[i2][j]) return false;
					pivot = j;
					maxNonZeroRow = i;
					break;
				}
			}
			minZeroRow = (pivot == null)?Math.min(minZeroRow, i):minZeroRow;
			if (maxNonZeroRow > minZeroRow) return false;
			lastPivot = pivot;
		}
		return true;
	}	
}
This program produces the following results:
nxn   f(n)
1x12
2x25
3x316
4x467
5x5374
6x62,825
7x729,212
8x8417,199
9x98,283,458

After a bit of research and some fiddling around it became clear that f(n) was equivalent to the summation of Gaussian binomial coeffecients with a q-number of 2. So, what does the final formula look like?




As you can see, even the formula requires a bit of work to determine the number of RCMs with binary entries! The below program implements the formula in an attempt to make calculation simpler. Feel free to verify that the results from this program matches that of the above.
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.text.NumberFormat;

public class RowCanonicalFormCount {
	public static void main(String...args) {
		NumberFormat format = DecimalFormat.getNumberInstance();
		for(int i = 1; i <= 50; System.out.println(i + "\t" + format.format(f(i++))));
	}
	
	private static BigInteger f(int n) {
		BigInteger sum = BigInteger.ZERO;
		for(int m = 0; m <= n; m++) {
			BigInteger num = BigInteger.ONE, den = BigInteger.ONE;
			for(int r = 0; r <= (m - 1); r++) {
				num = num.multiply(BigInteger.ONE.subtract(BigInteger.valueOf(2).pow(n-r)));
			}
			for(int r = 1; r <= m; r++) {
				den = den.multiply(BigInteger.ONE.subtract(BigInteger.valueOf(2).pow(r)));
			}
			sum = sum.add(num.divide(den));
		}
		return sum;
	}	
}

Non-Binary Entries

What about RCMs with non-binary entries? The table below contains the valid RCM permutation counts for the number of allowed digits (q=2 means {0, 1}, q=3 means {0, 1, 2}, ...). These values are generated by the code below the table, a modified version of the code at the top of this page, which for each "free" entry (doesn't have to be zero or one for the matrix to remain an RCM matrix) accounts for all possible values.

nxn   q=2q=3q=4q=5q=6
1x122222
2x256789
3x31628446488
4x4672125291,1202,111
5x53742,66412,27842,176118,182
6x62,82556,632565,7233,583,23216,649,389
7x729,2122,052,6565,1409,856666,124,2885,547,079,988
8x8417,199127,902,8649,371,059,621281,268,665,3444,671,840,869,691
public class RowCanonicalFormNonBinary {
	// The number of int values allowed (including 0 and 1)
	// 2 = binary entries {0, 1}
	// 3 = entries of possible values {0,1,2} (so long as the leading non-zero entry in a row is 1)
	// 4 = {0,1,2,3}
	// ...
	private static final long Q = 4;
	
	public static void main(String...args) {
		for(int n = 1; n < 10; System.out.println(n + "x" + n + ": " + populate(new boolean[n][n++], 0, 0)));
	}
	
	private static long populate(boolean[][] matrix, int i, int j) {
		if (!isRowCanonicalForm(matrix)) return 0;
		if (j == matrix.length) {i++; j = 0;}
		if (i == matrix.length) return pow(Q-1, getVariableEntriesCount(matrix));
		return populate(matrix, true, i, j) + populate(matrix, false, i, j);
	}
	
	private static long populate(boolean[][] matrix, boolean value, int i, int j) {
		matrix[i][j] = value;
		return populate(matrix, i, j+1);
	}

	private static boolean isRowCanonicalForm(boolean[][] matrix) {
		long minZeroRow = Integer.MAX_VALUE, maxNonZeroRow = 0;
		Integer pivot = null, lastPivot = null;
		for(int i = 0; i < matrix.length; i++) {
			pivot = null;
			for(int j = 0; j < matrix.length; j++) {
				if (matrix[i][j]) {
					if (i >= 1 && (((lastPivot==null)?Integer.MAX_VALUE-1:lastPivot) >= j)) return false;
					for(int i2 = 0; i2 < matrix.length; i2++) if ((i2 != i) && matrix[i2][j]) return false;
					pivot = j;
					maxNonZeroRow = i;
					break;
				}
			}
			minZeroRow = (pivot == null)?Math.min(minZeroRow, i):minZeroRow;
			if (maxNonZeroRow > minZeroRow) return false;
			lastPivot = pivot;
		}
		return true;
	}
	
	private static long pow(long b, long p) {
		long r = 1;
		for(long i = 1; i <= p; i++) {
			r *= b;
		}
		return r;
	}
	
	private static long getVariableEntriesCount(boolean[][] matrix) {
		long count = 0;
		for(int i = 0; i < matrix.length; i++) {
			boolean found = false;
			for(int j = 0; j < matrix.length; j++) {
				if (matrix[i][j]) {
					if (found) count++;
					found = true;
				}
			}
		}
		return count;
	}
}
Unsurprisingly, the values are equivalent to the summation of Gaussian binomial coeffecients with the specified q-number, with the same formulation as the original formula, with the "2" replaced by the q-number you are working with. You can verify this by replacing the line "BigInteger.valueOf(2)" in the second code sample with "BigInteger.valueOf(q)", where q represents the q-number.