code maple
Maple
To count matrices over finite fields by rank and with restricted support we use procedures built around Stembridge's reduce package. You will need the files "reduce.txt" and "kc_test.txt".
The text file "matqresuppV1-2.txt" has the following main procedures:
matq(m,n,S,r) computes the number of m-by-n matrices of rank r matrices whose support avoids the complement of S. In particular, the function matq(m × n, S, r) from paper would be matq(m,n,compsh(m,n,S),r). REQUIREMENTS "reduce.txt" and "kc_test.txt" from Stembridge's reduce package. Must input/read these files.
qRkNum(m,n,r,S,q,dir) computes the q-rook number sum_C q^(inv^(dir)(C,S)) where inv^(dir)(C,S) is the number of dir-inversions on S and dir is NE or NW or SE or SW and C is a rook placement on S of r rooks.
fastMatqRothe(w) computes matq(n,n,Rw,n) where Rw is the Rothe diagram of w. This procedure removes rows and columns full of free entries to speed up computations REQUIREMENTS "reduce.txt" and "kc_test.txt" from Stembridge's reduce package. Must read/input these files.
getRP(n,r,S) computes the set of r-partial permutations that avoid subset S of [n] × [n].
strsh(m,n,lam) returns the subset of [m] × [n] indexed by partition lam, option 'nocomp' at the end gives complement.
skewsh(m,n,lam,mu) returns the subset of [m] × [n] indexed by skew partition lambda/mu, option 'nocomp' at the end gives the complement of the skew shape.
Rothesh(w) returns the SE-Rothe diagram of the permutation w on n letters.
LHullsh(w) returns the left hull of the permutation w.
compsh(m,n,S) returns complement of set S in [m] × [n].
getMatrixXs(m,n,S) returns [X,nument] where X is the m × n matrix (x[i,j]) such that x[i,j]=0 if [i,j] is in S and nument is the number of free entries in X, i.e., n*m - #S.
NEW procedure in version 1.2:
matqBruhat(n,S,r) computes the number of n-by-n rank r matrices whose support avoids S using intersection with Bruhat cells of permutations (in the case r=n) or partial permutations (in the case r<n). This procedure appears to be faster than matq(n,n,S,r). This algorithm was suggested by Alexander Woo and it was used to compute the number of rank r 7-by-7 matrices whose support avoids the incidence matrix of the Fano plane.
new procedure in version 1.1:
recurmatq(m,n,S,r) computes RECURSIVELY the number of m-by-n rank r matrices whose supports avoids COMPLEMENT OF S. REQUIREMENT: set S in [m] by [n] needs to satisfy the following property: either S or its transpose contains at most two entries in a row OR the complement(S) or its transpose contains at most two entries in a row (uses Theorems 3.5 and 3.7 from here).
There is also a maple worksheet "suppMatResPos.mw.xml" with these functions and most of the examples and figures from the paper.