# Boolean squaring of adjacency matrix

1. May 12, 2014

### s3a

1. The problem statement, all variables and given/known data
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.:
2. Relevant equations
Boolean Squaring.

3. 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!

2. May 13, 2014

### HallsofIvy

Staff Emeritus
"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.

3. May 13, 2014

### 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)?

4. May 14, 2014

### Ray Vickson

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.

5. May 14, 2014

### s3a

So does it not make sense to ask:

?

6. May 15, 2014

### s3a

Edit: I accidentally double-posted.

7. May 15, 2014

### s3a

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

Thank you both.