Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that a zero-one matrix can only have 1's after 5th power

  1. Oct 12, 2015 #1

    I couldn't give the full explanation in the title - I am talking about a particular matrix. Given the matrix:

    A[1] =

    0 0 1
    1 0 0
    1 1 0

    A[5] =

    1 1 1
    1 1 1
    1 1 1

    Once it gets to the 5th boolean power, it becomes all 1's, and any power greater than or equal to 5 will always produce a matrix of all 1's. I know that this will always be true because A[5], A[6], A[N] will always have only 1's, and that since A[1] has at least one "1" in each column, that will always be enough to produce a one in each column, when taking the boolean product of each row of A. I understand this, but am not sure how to put it into a proof. Would appreciate any tips.
  2. jcsd
  3. Oct 12, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    A proof for this specific A[1]? Just calculate it. For 6+, you can show formally via induction that it doesn't change any more.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook