Question

Why is the cardinality of the class that contains a walk of length 2, the sum of all the entries in the matrix A^2?

Answer 1

@Michele_Laino @Zarkon @Blonde_Gangsta @AngusV @SithsAndGiggles @FibonacciChick666 @rational @jtvatsim @UnkleRhaukus

Answer 2

If you draw it out, or maybe do a smaller example it might make sense a bit. If not, you might just have to trust in the magic of the matrix multiplication. So that matrix shows that if we start at any of the IN if we follow to the right on the matrix, we put a 1 if it is going OUT at another spot. Since this matrix is to the first power, it represents where you go in 1 step. Just as a help to your intuition, anything to the 0 power is 1, similarly if we raise this matrix to the 0 power and accept that it would give us the identity matrix, then this means in zero steps every vertex starts and stops on the same spot.

So squaring the matrix there will tell you how many ways starting from that IN you get to that OUT. You can compute the square of the matrix without actually doing matrix multiplication, maybe that'll help make it more clear, or at least confirm that it works.