# Homework Help: 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

"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:

to which the answer is

?

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.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted