1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean squaring of adjacency matrix

  1. May 12, 2014 #1

    s3a

    User Avatar

    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. jcsd
  3. May 13, 2014 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "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.
     
  4. May 13, 2014 #3

    s3a

    User Avatar

    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)?
     
  5. May 14, 2014 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. May 14, 2014 #5

    s3a

    User Avatar

    So does it not make sense to ask:

    to which the answer is

    ?
     
  7. May 15, 2014 #6

    s3a

    User Avatar

    Edit: I accidentally double-posted.
     
  8. May 15, 2014 #7

    s3a

    User Avatar

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

    Thank you both.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted