Matrices with a given number of violations of Regular Minimality

A row (or column) of an n×n matrix complies with Regular Minimality (RM) if it has a unique minimum entry which is also a unique minimum entry in its column (respectively, row). The number of violations of RM in a matrix is defined as the number of rows (equivalently, columns) that do not comply with RM. We derive a formula for the proportion of n×n matrices with a given number of violations of RM among all n×n matrices with no tied entries. The proportion of matrices with no more than a given number of violations can be treated as the p-value of a permutation test whose null hypothesis states that all permutations of the entries of a matrix without ties are equiprobable, and the alternative hypothesis states that RM violations occur with lower probability than predicted by the null hypothesis. A matrix with ties is treated as being represented by all matrices without ties that have the same set of strict inequalities among their entries.