How to quickly determine if a matrix is a permutation matrix

Question

How to quickly determine if a square logical matrix is a permutation matrix? For instance,

is not a permutation matrix since the 3rd row have 2 entries 1.

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

I define a logical matrix like

numpy.array([(0,1,0,0), (0,0,1,0), (0,1,1,0), (1,0,0,1)])

Here is my source code:

#!/usr/bin/env python
import numpy as np

### two test cases
M1 = np.array([
    (0, 1, 0, 0),
    (0, 0, 1, 0),
    (0, 1, 1, 0),
    (1, 0, 0, 1)]);

M2 = np.array([
    (0, 1, 0, 0),
    (0, 0, 1, 0),
    (1, 0, 0, 0),
    (0, 0, 0, 1)]);

### fuction 
def is_perm_matrix(M) :
    for sumRow in np.sum(M, axis=1) :
        if sumRow != 1 :
            return False
    for sumCol in np.sum(M, axis=0) :
        if sumCol != 1 :
            return False
    return True

### print the result
print is_perm_matrix(M1) #False
print is_perm_matrix(M2) #True

Is there any better implementation?

Answer 1

Here's a simple non-numpy solution that assumes that the matrix is a list of lists and that it only contains integers 0 or 1. It also functions correctly if the matrix contains Booleans.

def is_perm_matrix(m):
    #Check rows
    if all(sum(row) == 1 for row in m):
        #Check columns
        return all(sum(col) == 1 for col in zip(*m))
    return False

m1 = [
    [0, 1, 0],
    [1, 0, 0],
    [0, 0, 1],
]

m2 = [
    [0, 1, 0],
    [1, 0, 0],
    [0, 1, 1],
]

m3 = [
    [0, 1, 0],
    [1, 0, 0],
    [1, 0, 0],
]

m4 = [
    [True, False, False],
    [False, True, False],
    [True, False, False],
]

print is_perm_matrix(m1)
print is_perm_matrix(m2)
print is_perm_matrix(m3)
print is_perm_matrix(m4)

output

True
False
False
False

Answer 2

What about this:

def is_permuation_matrix(x):
    x = np.asanyarray(x)
    return (x.ndim == 2 and x.shape[0] == x.shape[1] and
            (x.sum(axis=0) == 1).all() and 
            (x.sum(axis=1) == 1).all() and
            ((x == 1) | (x == 0)).all())

Quick test:

In [37]: is_permuation_matrix(np.eye(3))
Out[37]: True

In [38]: is_permuation_matrix([[0,1],[2,0]])
Out[38]: False

In [39]: is_permuation_matrix([[0,1],[1,0]])
Out[39]: True

In [41]: is_permuation_matrix([[0,1,0],[0,0,1],[1,0,0]])
Out[41]: True

In [42]: is_permuation_matrix([[0,1,0],[0,0,1],[1,0,1]])
Out[42]: False

In [43]: is_permuation_matrix([[0,1,0],[0,0,1]])
Out[43]: False