Asked by Macarel
on 19 Sep 2011

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

*No products are associated with this question.*

Answer by 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

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.

Show 4 older comments

Derek O'Connor
on 21 Sep 2011

@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
on 2 Nov 2011

Derek O'Connor
on 21 Feb 2012

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

Answer by 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*

Show 1 older comment

Derek O'Connor
on 23 Feb 2012

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

Walter Roberson
on 23 Feb 2012

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

Answer by 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

Show 1 older comment

Derek O'Connor
on 25 Feb 2012

@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
on 25 Feb 2012

Opportunities for recent engineering grads.

## 1 Comment

## Jan Simon (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/16192#comment_35983

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.