[Robert wrote](https://forum.azimuthproject.org/discussion/comment/18891/#Comment_18891):

> I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix.

The trace would give you the number of paths of length \\(n\\) either of type \\(x \to x\\) or of type \\(y \to y\\). For instance, the square of that matrix gives:

\[ \left( \begin{array}{cc} 2 & 1 \\\ 1 & 1 \end{array} \right) .\]

The trace of this matrix is 3, but we know there are only two paths of length 2 from x to itself. Do you see what's happening? (It has to do with the fact that the original matrix is, as you observed, the _adjacency matrix_ for this graph.)

Also, notice that the adjacency matrix doesn't have to be binary-valued here. If we have two self-loops on a vertex, we'd need to put a 2 down for that vertex.

(I love the matrix approach to this problem! It's a wonderful example of one of [PĆ³lya's principles](https://en.wikipedia.org/wiki/How_to_Solve_It): sometimes, in order to prove a thing, you should prove a stronger thing instead.)

> I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix.

The trace would give you the number of paths of length \\(n\\) either of type \\(x \to x\\) or of type \\(y \to y\\). For instance, the square of that matrix gives:

\[ \left( \begin{array}{cc} 2 & 1 \\\ 1 & 1 \end{array} \right) .\]

The trace of this matrix is 3, but we know there are only two paths of length 2 from x to itself. Do you see what's happening? (It has to do with the fact that the original matrix is, as you observed, the _adjacency matrix_ for this graph.)

Also, notice that the adjacency matrix doesn't have to be binary-valued here. If we have two self-loops on a vertex, we'd need to put a 2 down for that vertex.

(I love the matrix approach to this problem! It's a wonderful example of one of [PĆ³lya's principles](https://en.wikipedia.org/wiki/How_to_Solve_It): sometimes, in order to prove a thing, you should prove a stronger thing instead.)