math - Get the maximum permutation matrix from logical matrix

Question

A (m rows, n columns) is a (0,1)-Matrix (or logical matrix).

How to get a sub matrix B (p rows, p columns) from A, satisfying that B is a permutation matrix and p is the maximum? For instance,

PS: A permutation matrix is a square binary matrix that has exactly one entry 1 in each row and each column and 0s elsewhere.

Answer 1

One possibility is to exploit that every permutation matrix can be built up one row and column at a time. So we can take every permutation matrix of a certain size, try to extend it by all possible rows or columns, and see what results in a permutation matrix that is one size larger.

The running time isn't that great. I think it's something like O(2^(m+n)). (And I've used Python, FWIW.)

#!/usr/local/bin/python3

import itertools

A = ((0,1,0,0),
     (0,0,1,0),
     (0,1,1,0),
     (1,0,0,1))
maximalSubmatrices = { ( (), () ), }
# each tuple is a tuple of rows and then columns
maxP = 0

def isPerm(rows,cols):
    if ( len(rows) != len(cols) ):
        return False
    for row in rows:
        if not exactlyOne( A[row][col] for col in cols ):
            return False
    for col in cols:
        if not exactlyOne( A[row][col] for row in rows ):
            return False
    return True

def exactlyOne(sequence):
    return sum( 1 for elt in sequence if elt ) == 1

while True:
    moreMaxl = set()
    for submatrix in maximalSubmatrices:
        for row,col in itertools.product(range(len(A)),range(len(A[0]))):
            if ( row not in submatrix[0] and col not in submatrix[1] ):
                moreMaxl.add( ( tuple(sorted(submatrix[0]+(row,))) , tuple(sorted(submatrix[1]+(col,))) ) )
    moreMaxl = set( ( maxl for maxl in moreMaxl if isPerm(*maxl) ) )
    if ( len(moreMaxl) ):
        maxP += 1
        maximalSubmatrices = moreMaxl
    else:
        break

for maxl in maximalSubmatrices:
    print("maximal rows: ",maxl[0],"
maximal cols: ",maxl[1],end="

")
print("maximum permutation size is: ",maxP)

The output is:

maximal rows:  (0, 1, 3) 
maximal cols:  (0, 1, 2)

maximal rows:  (0, 1, 3) 
maximal cols:  (1, 2, 3)

maximum permutation size is:  3

Explanation:

In Python, a tuple is an immutable array of objects. Because it’s immutable, it can be hashed and made an element of a set. So maximalSubmatrices is a set of the rows and columns needed to make a submatrix. In Java, we’d do something like:

class Submatrix {
    List<Integer> rows;
    List<Integer> columns;
    public int hashCode();
    public boolean equals(Object);
}
Set<Submatrix> maximalSubmatrices;

but Python can take care of all that by itself.

We start with the rows and columns needed to make a submatrix of size 0: both are the empty tuple (). Each time through the while loop, we take all possible row,column pairs and see if that row,column could extend a current permutation matrix (in other words, they’re not already in the matrix). If so, we add the extended matrix to the set moreMaxl. Then we go through moreMaxl and keep only the permutation matrices. If there’s still elements in moreMaxl, then they’re permutation matrices that are one size larger than the matrices in maximalSubmatrices. Since we could extend, the while loop continues.