Inversion of a boolean matrix

52 views (last 30 days)
Macarel
Macarel on 19 Sep 2011
Edited: Jan on 25 Oct 2013
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 Comment
Jan
Jan on 20 Sep 2011
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.

Sign in to comment.

Accepted Answer

Derek O'Connor
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
  4 Comments
Derek O'Connor
Derek O'Connor on 25 Feb 2012
I meant to add this final sentence: "But early detection of row(col)sums > 1 may still be worthwhile."
Walter Roberson
Walter Roberson on 25 Feb 2012
Good point about detecting 0's.

Sign in to comment.

More Answers (2)

Derek O'Connor
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.
  7 Comments
Walter Roberson
Walter Roberson on 2 Nov 2011
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
Derek O'Connor on 21 Feb 2012
Walter, |IUBool| is wrong. See my correction above and the link about it.

Sign in to comment.


Derek O'Connor
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.
  4 Comments
Walter Roberson
Walter Roberson on 23 Feb 2012
Picky mathematicians would not object to a mapping function, (false -> 0, true -> 1)

Sign in to comment.

Categories

Find more on Loops and Conditional Statements in Help Center and File Exchange

Community Treasure Hunt

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

Start Hunting!