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

[leo255]

Hello,

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.

 

[mfb]

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.