Inversion of a boolean matrix

Question

Macarel 2011-9-19

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/16192-inversion-of-a-boolean-matrix

编辑： Jan 2013-10-25

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

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Jan 2011-9-20

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 2012-2-24

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/16192-inversion-of-a-boolean-matrix#answer_38600

在 MATLAB Online 中打开

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. derekroconnor@eircom.net
    [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

4 个评论
显示 2更早的评论隐藏 2更早的评论

Derek O'Connor 2012-2-25

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

Walter Roberson 2012-2-25

Good point about detecting 0's.

请先登录，再进行评论。

Answer 2

Derek O'Connor 2011-9-20

4
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/16192-inversion-of-a-boolean-matrix#answer_22008

在 MATLAB Online 中打开

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.

7 个评论
显示 5更早的评论隐藏 5更早的评论

Walter Roberson 2011-11-2

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 2012-2-21

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

请先登录，再进行评论。

Answer 3

Derek O'Connor 2012-2-21

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/16192-inversion-of-a-boolean-matrix#answer_38158

在 MATLAB Online 中打开

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. derekroconnor@eircom.net
    [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. derekroconnor@eircom.net
    [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.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Walter Roberson 2012-2-23

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

Derek O'Connor 2012-2-23

See above

请先登录，再进行评论。

Inversion of a boolean matrix

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

采纳的回答

4 个评论
显示 2更早的评论隐藏 2更早的评论

更多回答（2 个）

7 个评论
显示 5更早的评论隐藏 5更早的评论

4 个评论
显示 2更早的评论隐藏 2更早的评论

另请参阅

类别

标签

Community Treasure Hunt

Inversion of a boolean matrix

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

采纳的回答

4 个评论 显示 2更早的评论隐藏 2更早的评论

更多回答（2 个）

7 个评论 显示 5更早的评论隐藏 5更早的评论

4 个评论 显示 2更早的评论隐藏 2更早的评论

另请参阅

类别

标签

Community Treasure Hunt

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

4 个评论
显示 2更早的评论隐藏 2更早的评论

7 个评论
显示 5更早的评论隐藏 5更早的评论

4 个评论
显示 2更早的评论隐藏 2更早的评论