Boolean Matrix Multiplication in Matlab

Question

Does Matlab have a Boolean (sometimes called logical or binary) matrix multiplication function? I'm specifically talking about what's usually denoted by a circle with a dot in it to denote Boolean matrix multiplication:

cij = (ai1 & b1j) || (ai2 & b2j) || (ai3 & b3j)|| ... || (aik & bkj)

I have had a hard time locating one and am now assuming one does not exist. If that is the case, is there a quick way to write a .m file that will accomplish this task?

An example would be:

[1 1 1;                [1 0 1;      [1 1 1
 1 0 1;   *circledot*   1 0 0;   =   1 1 1
 1 0 0]                 0 1 0]       1 0 1]

Pizzicato

Answer 1

You can just allow MATLAB to perform standard matrix multiplication and convert the result to logical:

b1 = [1,1,1;1,0,1;1,0,0]
b2 = [1,0,1;1,0,0;0,1,0]
bout = (b1*b2)>0 % or logical(b1*b2) as per natan's answer!

bout =

     1     1     1
     1     1     1
     1     0     1

However, if you want to faithfully perform the logical AND-OR operations of the Boolean matrix multiplication operator, you can do it with bsxfun and any as follows:

bout = any(bsxfun(@and,permute(b2,[3 2 1]),permute(b1,[1 3 2])),3);

That pretty well obfuscates the process, but it follows the formula.

Quick test data: b1 = randi(2,M,N)-1; b2 = randi(2,N,M)-1;.

Encapsulate

Yep, missed that. Thanks. – Pizzicato

Answer 2

Matrix multiplication is a series of multiply-and-add operations. If the inputs are all ones and zeros, the result of such an operation will be "zero or greater than zero". So setting every value >0 to 1 in the product will solve your issue. Example:

booleanResult = (result > 0);

Or

booleanResult = logical(result);

I am sure you can think of others.

Kentigerma

Very good point. Had I realized that to begin with I wouldn't have asked the question. Smart people here, much appreciated. – Pizzicato

This is in fact the fastest way to perform the computation: a simple matrix multiplication over two binary matrices. This is a lot faster than bsxfun by orders of magnitude. – Beamy