Boolean squaring of adjacency matrix

[s3a]

Homework Statement

I have come across the following statement which I've written for myself a long time ago, and I don't remember what is going on.:

The adjacency matrix of R ◦ R is $M^{(2)}$, where (2) signifies the square using boolean algebra.

Homework Equations

Boolean Squaring.

The Attempt at a Solution

Sorry for the potentially stupid question, but I've been researching how to compute $M^{(2)}$, and the best I found was how to get an adjacency matrix from a graph, and computing $M^2$ (instead of $M^{(2)}$).

If someone could either explain to me the $M^{(2)}$ part or point me to something that explains that, I would very much appreciate it!

 

[HallsofIvy]

"Boolean algebra" is essentially algebra on "true", "false" or, equivalently "1", "0" with the addition rules that 0+ 0= 0, 1+ 0= 0+ 1= 1, and 1+ 1= 0 and multiplication rules 0*0= 0*1= 1*0= 0 and 1*1= 1.

 

[s3a]

For 1 + 1, I think you meant 1 + 1 = 1, but that's not my problem; my problem is the parentheses around the 2 . . . what's the difference between a power within parentheses and a power that's not within parentheses (in this context)?

 

[Ray Vickson]

For 1 + 1, I think you meant 1 + 1 = 1, but that's not my problem; my problem is the parentheses around the 2 . . . what's the difference between a power within parentheses and a power that's not within parentheses (in this context)?

The matrix $M^k$ has entries which specify the number of paths of length k; that is, the element $M^k(i,j)$ is the number of length-k paths from i to j. The matrix $M^{(k)}$ just says whether there are length-k paths; that is, $M^{(k)}(i,j)$ is 0 if there are no length-k paths from i to j and is equal to 1 if there is at least one length-k path from i to j.

 

[s3a]

So does it not make sense to ask:

Given that the matrix M is the adjacency matrix of the graph of some relation R.

What is the adjacency matrix of R◦R?"

to which the answer is

The adjacency matrix of R◦R is $M^{(2)}$, where (2) signifies the square using boolean algebra.

?

 

[s3a]

Edit: I accidentally double-posted.

 

[s3a]

Actually, Ray Vickson, what you said gave me the ammunition to better understand what someone else explained to me.

Thank you both.