Inverses of Boolean Matrices
Derek OConnor March 1, 2012*
Here are two related questions that I asked on Math Stack Exchange 1 D.E. Rutherford2 gives this result: Theorem 1. If a Boolean matrix B has an inverse, then B1 = B T , or BB T = B T B = I. I have two related questions: 1. The only invertible Boolean matrices I can nd are permutation matrices. Are there others? 2. Is there an O(n2 ) test to determine if an n n Boolean matrix B has an inverse? Robert Israel3 answered the rst question with the following neat proof. Theorem 2. The only invertible Boolean matrices are permutation matrices. Proof. Suppose AB = BA = I where A and B are Boolean matrices. A and B must have at least one 1 in each row and column. If Aij = 1, then we must have Bjk = 0 for all k = i and Bki = 0 for all k = j. So B has only one 1 in each row and column, and is a permutation matrix. This leads immediately to an answer to the second question: a Boolean matrix can be tested in O(n2 ) steps to see if it is a permutation matrix. The following M ATLAB function does this by checking if the row-sums and column-sums of B are 1.
* Started: 24 Feb 2012. web: [Link] 1 [Link] 2 [Link] 3 [Link]
email : derekroconnor@[Link]
Derek OConnor
Inverses of Boolean Matrices
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
% function answ = isInvBool3(B) % % If the boolean matrix B is invertible it must be a permutation % matrix. Hence this check reduces to: Is B a permutation matrix? % This is done by counting the number of TRUE values in each row % and column. A permutation matrix has one TRUE value in each row % and column. % Derek O'Connor 23 Feb 2012. derekroconnor@[Link] [n,n] = size(B); rowsum = zeros(1,n); colsum = zeros(1,n); answ = true; for i = 1:n for j = 1:n if B(i,j) rowsum(i) = rowsum(i)+1; colsum(j) = colsum(j)+1; end %if end %for j end %for i for k = 1:n if rowsum(k) = 1 || colsum(k) = 1 answ = false; return end end % End isInvBool3
D EREK OC ONNOR , M ARCH 1, 2012
Derek OConnor
Inverses of Boolean Matrices
Related Theorems
Theorem 3. 4 An invertible n n matrix M with non-negative integer entries, whose inverse also has non-negative integer entries, is necessarily a permutation matrix. Proof. The condition that M has nonnegative integer entries means that it maps the monoid Zn 0 to itself. The condition that M1 is likewise means that M is an automor phism of this monoid. The basis elements (0, 0, . . . , 0, 1, 0, . . . , 0) in Zn 0 are the only elements which cannot be written as u + v for some nonzero u and v in Zn 0 . This description makes it clear that any automorphism of Zn 0 must permute this basis. So M is a permutation matrix. Theorem 4. 5 If A is invertible and both matrices A and A1 have only non-negative real coefcients, then A is a permutation matrix times a diagonal matrix with strictly positive diagonal coefcients. Proof. Suppose A and B = A1 have all coefcients in N. Then the same is true for the symmetric matrix AAt and its inverse Bt B. Since these matrices are of the form AAt = I + a and Bt B = I + b with a and b having coefcients in N and I denoting the identity matrix, we get a = b = 0 by considering the product ( I + a)( I + b) = I + a + b + ab. The matrix A is thus an orthogonal matrix with coefcients in N, which implies that it is a permutation matrix.
4 [Link] 5 [Link]
D EREK OC ONNOR , M ARCH 1, 2012