289 views (last 30 days)

Show older comments

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
on 20 Sep 2011

Derek O'Connor
on 24 Feb 2012

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

Derek O'Connor
on 20 Sep 2011

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.

Derek O'Connor
on 21 Feb 2012

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

Derek O'Connor
on 21 Feb 2012

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.

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!