Inversion of a boolean matrix

Hello everybody,

to perform a post-processing, i need to manipulate matrix filled with boolean value (1 or 0). One of the operations consist on an inversion of a square matrix. Because i'm working with boolean valu, i can't use the inv function of matlab to perform the inversion. So a used a matlab program found in the Matlab Answer which use the gauss pivot principle. I modify this program for my application: instead of using multiplication, addition, soustraction and division, i use Xor and & function as logical operators. The results are reserved: - when the inversion (with inv function) give a results with integer numbers in the matrix, the modified program works very well. - when the inversion (with inv function) give a results with decimal numbers, the modified program found that the matrix is non inversible. So i'm not sure to understant what happened concerning the in version of boolean matrix. Is it possible to help me for thos problem. Thanks a lot in advance. Find here the modified program:

clc
close all
clear all

% exemple 1: it works
% C = [0 0 1; 0 1 1; 1 1 0];
% A = [0 0 1; 0 1 1; 1 1 0];

% exemple 2: it works
% C = [0 1 0 1; 1 0 1 0; 0 1 0 0; 1 0 0 0];
% A = [0 1 0 1; 1 0 1 0; 0 1 0 0; 1 0 0 0];

% exemple 3: inversible with inv function but not with the program
C = [0 0 1 1; 0 1 1 1; 1 1 1 0; 1 1 0 1];
A = [0 0 1 1; 0 1 1 1; 1 1 1 0; 1 1 0 1];

Bmatinv = inv(C)
n=size(A,1);
B=eye(n);

for p=1:n
    vec=[(1:p-1) n (p:n-1)];
    test=1;
    while A(p,p)==0
        if test==n
            error('Matrix is not inversible')
        end
        A=A(vec,:);
        B=B(vec,:);
        test=test+1;
    end
    B(p,:)=B(p,:)& A(p,p);
    A(p,:)=A(p,:)& A(p,p);
    for q=p+1:n
        B(q,:) = xor(B(q,:) , A(q,p)& B(p,:));
        A(q,:) = xor(A(q,:) , A(q,p)& A(p,:));
    end
end

for p=n:-1:2
    for q=p-1:-1:1
        B(q,:) = xor(B(q,:) , A(q,p)& B(p,:));
        A(q,:) = xor(A(q,:) , A(q,p)& A(p,:));
    end
end

% show the results to compare with inv function
B

[Jan]

Besides clearing the variables, CLEAR ALL removes all loaded functions from the memory. Reloading them needs several seconds, but there is no advantage. So better use CLEAR without ALL.

Answer 1

[Derek O'Connor]

WRONG AGAIN

In testing Walter's suggestion about row and column sums I realized that isInvBool2 is wrong. Try B = [true true; false false]. The column sums are correct but the row sums are not. Here is my third attempt, which I hope is correct. It can be speeded up but I'm more interested in correctness than speed at the moment.

% --------------------------------------------------------------
  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 24 Feb 2012. [e-mail]

    [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

[Walter Roberson]

I like the simultaneous row and column update, at least from a theoretical point of view.

In the "if B(i,j)" part, you could stop as soon as you detected that rowsum(i) or colsum(i) was already 1. That would also remove the need for the final "for" loop.

[Derek O'Connor]

@Walter,

The final for-loop is doing double duty: (1) detecting row(col)sums > 1, which could be detected in the "if B" part, and (2) detecting row(col)sums = 0, which cannot be detected in the "if B" part.

Try B = [false false; false false]

[Derek O'Connor]

I meant to add this final sentence: "But early detection of row(col)sums > 1 may still be worthwhile."

[Walter Roberson]

Good point about detecting 0's.

Answer 2

[Derek O'Connor]

THEOREM. If a Boolean matrix B possesses a one-sided inverse, that inverse is also a two-sided inverse. Furthermore such an inverse, if it exists, is unique and is B', [the transpose of B].

See Rutherford, D.E.: "Inverses of Boolean Matrices", 1962. http://www.scribd.com/doc/82204282/Rutherford-Inverses-of-Boolean-Matrices

This theorem says that if B is invertible then BB' = B'B = I = [true on diagonal, false elsewhere].

NOTE: You must not mix numerical with boolean (logical), even though Matlab and other languages use 1 for true and 0 for false. Matlab's built-in matrix inverse is for numerical matrices only.

function C = MMBool(A,B)

% Calculate C = A*B assuming A and B are logical,
% Derek O'Connor 20  Sep 2011

[n,n] = size(A);
C(1:n,1:n) = false;

for i = 1:n
    for j = 1:n
        for k = 1:n
            C(i,j) = C(i,j) || (A(i,k) && B(k,j));
        end
    end
end

Example: B is a permutation matrix (I can't find an invertible B that is not a permutation, so far.)

B= [0 1 0 0; 1 0 0 0; 0 0 0 1; 0 0 1 0]

>> C = MMBool(B,B')

C =

       1     0     0     0
       0     1     0     0
       0     0     1     0
       0     0     0     1
-------------------------------------------

This is an O(n^2) test for invertibility of A, based on Rutherford's paper:

function [IU,U] = IUBool(A)
% If A is (boolean) invertible then IU = true (1)
% and U(i) = true (1), i = 1:n.
% Derek O'Connor 20 Sep 2011

[n,n] = size(A);
U(n,1) = false;
IU = true;
for i = 1:n
    U(i) = A(i,1);
    for j = 2:n
        U(i) = U(i) || A(i,j);
    end
    IU = IU && U(i);
end
--------------------------------------

Warning (Added 21 Feb 2012) : IUBool is wrong but I'll leave it there to see if somebody can fix it. See the discussion about this problem here: http://math.stackexchange.com/questions/111357/

__________________________________________________________________

Additional Information

Warshall's Algorithm for calculating the transitive closure of a boolean matrix A is very similar to boolean matrix multiplication.

Initially, A is a boolean adjacency matrix where A(i,j) = true, if there is an arc (connection) between nodes i and j.

Finally, A(i,j) = true, if there is a path between nodes i and j.

function A = Warshall(A)

% Warshall's algorithm to calculate the
% Transitive Closure of A.
% Derek O'Connor 20  Sep 2011

[n,n] = size(A);
for k = 1:n
    for i = 1:n
        for j = 1:n
            A(i,j) = A(i,j) || (A(i,k) && A(k,j));
        end
    end
end

Notice that the k-loop is on the outside, but everything else is the same as boolean matrix multiplication.

A slight modification of the inner-most loop gives a considerable speed-up.

function A = WarshallM(A)
% Warshall's algorithm to calculate the
% Transitive Closure of the boolean matrix A.
% Derek O'Connor 20  Sep 2011

[n,n] = size(A);
for k = 1:n
    for i = 1:n
        for j = 1:n
            if ~A(i,j)
                A(i,j) = A(i,j) || (A(i,k) && A(k,j));
            end
        end
    end
end

For n = 1000, the inner-most statement is executed just 0.14% of the time so that most of the time is spent on the if-test and the inner-most j-loop control (about 50:50).

EDIT. The inner-most statement may be simplified to A(i,j) = A(i,k) && A(k,j);

Warshall's algorithm is easily modified to get the Floyd-Warshall All Pairs Shortest Path Algorithm.

function D = FWShortPaths(D)

% The Floyd-Warshall algorithm to calculate all
% shortest path pairs for the distance matrix D.
% Derek O'Connor 20  Sep 2011

[n,n] = size(D);
for k = 1:n
    for i = 1:n
        for j = 1:n
            D(i,j) = min(D(i,j), D(i,k) + D(k,j));
        end
    end
end

Again, the k-loop is on the outside. The function returns the distance matrix D, where D(i,j) is the length of the shortest path between nodes i and j.

Obviously, the complexity of these algorithms is the same as matrix multiplication: O(n^3). If we can speed up matrix multiplication then we can speed up these algorithms.

REFERENCE: Aho, A.V., Hopcroft, J.E., and Ullman, J.D. [1974]: The Design and Analysis of Computer Algorithms, ©Bell Labs, Addison-Wesley.

[Jan]

+1. I really like your references.

[Walter Roberson]

Hey, I used that book in university in the early 80's!

[Derek O'Connor]

@Walter,

AHU[1974] is a great book but not that easy to read. They wrote "Data Structures and Algorithms" in 1983, which is based on the first six chapters of AHU[1974], and is more accessible. Aho & Ullman, "Foundations of Computer Science", W.H. Freeman, 1992, is an excellent book, but seems to be over-shadowed by Cormen, Leiserson, and Rivest, "Introduction to Algorithms". All very useful books if you're interested in algorithms & data structures.

[Walter Roberson]

Now that I think of it, it was Data Structures and Algorithms instead; but I am confused because I think it was 1982 when I took that class. I will have to look at my copy.

[Derek O'Connor]

@Walter,

You're right. I have two copies of AHU's A&D. The second is a desk copy, which says it was 'reprinted with corrections, June 1983'. The first, which I bought, is dated 1982, so you must have got it 'hot off the presses'.

The book seems to be selling well still, with the latest corrections being 1987. I think it was typeset using Bell Labs' TROFF which looks a bit amateurish today but very good at the time when TeX was not well-developed or easy to use.

[Walter Roberson]

Say, Derek... in your IUBool routine, isn't your inner loop equivalent to U(i) = any(A(i,:)) ? But if so, then doesn't the entire routine reduce down to IU = all(any(A,2)) ??

[Derek O'Connor]

Walter, |IUBool| is wrong. See my correction above and the link about it.

Answer 3

[Derek O'Connor]

I am adding this crude O(n^2) invertibility test as a separate answer because my previous answer has become too long.

    % --------------------------------------------------------------
      function [answ,p] = isInvBool(B)
    % --------------------------------------------------------------
    % If B is (boolean) invertible it must be a permutation matrix.
    % Hence this check reduces to: Is B a permutation matrix?
    % As written, this is an inefficient function. Its only
    % purpose is to show that an O(n^2) algorithm is possible.
    %
    % Derek O'Connor 20 Feb 2012. [e-mail]

    [n,n] = size(B);
    p = [];
    for j = 1:n              % Builds a permutation vector p in O(n^2)
        for i = 1:n          % If B is not a permutation matrix then
            if B(i,j)        % we may have length(p) = 0 or > n.
                p = [p i];
            end
        end
    end

    %------- O(n) check to see if p(1:n) is a permutation --------

    answ = true;
    if length(p) < 1 || length(p) > n
        answ = false;
        return
    end
    mark(1,n) = false;
    for k = 1:n
        if p(k) < 1 || p(k) > n
            answ = false;
            return
        end
        if ~mark(p(k))
            mark(p(k)) = true;
        else               % p(k) has been marked for some j < k,
            answ = false;  % so this is the second occurence.
            return
        end
    end % for k
    % End isInvBool

____________________________________________________________________

Here is a much simpler version, using the "return-as-soon-as-possible" principle:

    % --------------------------------------------------------------
      function answ = isInvBool2(B)
    % --------------------------------------------------------------
    % If the boolean matrix B is  invertible it must be a permutation
    %  matrix. Hence this check reduces to: Is B a permutation matrix?
    %
    % Derek O'Connor 23 Feb 2012. [e-mail]

    [n,n] = size(B);
    dup = zeros(1,n);
    answ = true;
    for j = 1:n              
        for i = 1:n        
            if B(i,j)       
                dup(j) = dup(j)+1;
                if dup(j) > 1      % More than one TRUE in this column j
                    answ = false;  % B cannot be a permutation matrix
                    return
                end
            end
        end
        if dup(j) == 0             % Column j has no TRUE values
            answ = false;          % B cannot be a permutation matrix
            return
        end
    end

_______________________________________________________________________

Walter Roberson asked the question:

If the sum of the rows is a vector of 1's, and the sum of the columns is a vector of 1's, would that not be enough?

It depends on what you mean by "sum". Strictly speaking, the only operations allowed on the elements of a Boolean matrix are AND, OR, and NOT (&& | ~ in Matlab).

The Boolean sum of a Boolean vector is:

    % --------------------------------
      function S = BoolSum(Bvec)
    % --------------------------------
    % Boolean sum of a Boolean vector

      S = Bvec(1);
      for i = 2:length(Bvec)
          S = S || Bvec(i);
      end

Example: Let B = [true true; false true]. My function returns "false", but your method, using BoolSum, returns "true" because all row and column sums are "true" (=1). If you interpret B as a binary (0,1) matrix and use Matlab's numerical sum(vec) then your method works, but does more work than is necessary. Also, picky mathematicians might object to using any numerical operation on a Boolean.

Walter Roberson replied:

Picky mathematicians would not object to a mapping function, (false -> 0, true -> 1)

What you say is true or 1, but you would need to do map(BoolVec) -> BinVec and then do sum(BinVec). Yes, I know Matlab and other languages do this implicitly, but, as I pointed out to the original questioner, mixing logicals and numericals is confusing and possibly dangerous. Even picky mathematicians can get confused, as this comment from math stack exchange shows:

This question confused me at first: I suppose you are working over the semiring where addition is logical OR, i.e. 1+1=1, not over the field of order 2 where 1+1=0.

[Walter Roberson]

If the sum of the rows is a vector of 1's, and the sum of the columns is a vector of 1's, would that not be enough?

[Derek O'Connor]

@Walter, I answer you question above, at the end of my second answer.

[Walter Roberson]

Picky mathematicians would not object to a mapping function, (false -> 0, true -> 1)

[Derek O'Connor]

See above