Adjacency matrices and their powers

Result 1. Proof. v_iv_j and v_jv_i are the same edge, so a_{ij} = a_{ji}, and no vertex is adjacent to itself, so a_{ii} = 0. Row i has a 1 for each neighbor of v_i, so it sums to \deg(v_i), and by symmetry so does column i. The row sums add to the sum of the degrees, which is 2\lvert E \rvert by the handshake lemma. In M, each arc puts one 1 in its tail’s row and its head’s column. \square

Result 3. Proof. By induction on k. For k = 0, A^0 = I, and the only walk of length 0 from v_i is (v_i): one walk to v_j when i = j, none otherwise, matching the entries of I.

Suppose the statement holds for some k \ge 0. Since A^{k+1} = A^k A,

Sort the walks of length k + 1 from v_i to v_j by their next-to-last vertex v_m. Such a walk is a walk of length k from v_i to v_m followed by the step v_mv_j, which is allowed exactly when a_{mj} = 1. By the induction hypothesis there are (A^k)_{im} choices for the first part, so (A^k)_{im}a_{mj} walks have next-to-last vertex v_m. Each walk has exactly one next-to-last vertex, so adding over m counts every walk once. The directed case is the same with arcs (v_m, v_j). \square

Result 2. Proof. In the new order, position i holds v_{\sigma(i)}, so row i, column j records whether v_{\sigma(i)} and v_{\sigma(j)} are adjacent. An isomorphism is a matching of vertices that keeps adjacency, which says exactly that the matrices agree once the vertices of G_2 are listed as the images of v_1, \ldots, v_n. By Result 3, (B^k)_{ii} counts closed walks of length k at v_{\sigma(i)}, which is (A^k)_{\sigma(i)\sigma(i)}: the diagonal of B^k is that of A^k reordered, and the traces agree. \square

Result 4. Proof. (a) A walk (v_i, x, v_j) is a choice of a common neighbor x; when i = j every neighbor of v_i qualifies.

(b) (A^3)_{ii} counts closed walks (v_i, x, y, v_i). Consecutive vertices are adjacent and there are no loops, so x \ne v_i, y \ne x, y \ne v_i: the three are different and pairwise adjacent, a triangle through v_i. Conversely a triangle \{v_i, x, y\} gives exactly two such walks, one in each direction. Adding over i counts each triangle at each of its 3 vertices, twice, so \operatorname{tr}(A^3) = 6 \cdot (\text{number of triangles}).

(c) d(v_i, v_j) is the least length of a walk from v_i to v_j, and by Result 3 a walk of length k exists exactly when (A^k)_{ij} \ne 0.

(d) Entries of powers are never negative, so s_{ij} > 0 exactly when some (A^k)_{ij} > 0 with k \le n - 1. If v_i and v_j are joined, a shortest walk between them is a path (Result 1 of Walks, paths, cycles and connected graphs), with at most n vertices and so length at most n - 1. If they are not joined, there is no walk and s_{ij} = 0. \square

1. \begin{bmatrix}0&1&1&0&1\\1&0&1&0&0\\1&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{bmatrix}, in the order 1, \ldots, 5. Degrees 3, 2, 3, 2, 2, and 3 + 2 + 3 + 2 + 2 = 12 = 2 \cdot 6.
2. Swap rows 1 and 4 and also columns 1 and 4 (Result 2): \begin{bmatrix}0&0&1&0&1\\0&0&1&1&0\\1&1&0&1&0\\0&1&1&0&1\\1&0&0&1&0\end{bmatrix}. The old edge 15 is now 45, the 1 in row 4, column 5.
3. M = \begin{bmatrix}0&1&0&0\\0&0&1&0\\1&0&0&1\\0&1&0&0\end{bmatrix}. Out-degrees (row sums) 1, 1, 2, 1; in-degrees (column sums) 1, 2, 1, 1; each list adds to 5 arcs.
4. A^2 = \begin{bmatrix}3&1&1&2&0\\1&2&1&1&1\\1&1&3&0&2\\2&1&0&2&0\\0&1&2&0&2\end{bmatrix}, from the neighbor sets \{2, 3, 5\}, \{1, 3\}, \{1, 2, 4\}, \{3, 5\}, \{1, 4\}. The diagonal is the degree list, by Result 4(a).
5. (A^2)_{35} = 2: the walks (3, 1, 5) and (3, 4, 5). Row 1 of A^2 times column 5 of A is 3 + 2 = 5: (1, 2, 1, 5), (1, 3, 1, 5), (1, 3, 4, 5), (1, 5, 1, 5), (1, 5, 4, 5).
6. The diagonal of A^3 is 2, 2, 2, 0, 0, so the trace is 6 and there is 6 / 6 = 1 triangle, \{1, 2, 3\}.
7. The non-adjacent pairs \{1, 4\}, \{2, 4\}, \{2, 5\}, \{3, 5\} have entries 2, 1, 1, 2 in A^2. So I + A + A^2 has no zero entry, and by Result 4(c) every distance is at most 2.
8. M^2 = \begin{bmatrix}0&0&1&0\\1&0&0&1\\0&2&0&0\\0&0&1&0\end{bmatrix}, M^3 = \begin{bmatrix}1&0&0&1\\0&2&0&0\\0&0&2&0\\1&0&0&1\end{bmatrix}. d(1, 2) = 1; d(2, 1) = 2, along (2, 3, 1); d(1, 4) = 3, along (1, 2, 3, 4), since the (1, 4) entry is 0 in M and M^2.
9. Both degree sequences are (2, 2, 2, 1, 1). The cube of the matrix of G_1 has trace 0 and that of G_2 trace 6: G_2 has the triangle \{1, 2, 4\} and G_1 none, so they are not isomorphic. In G_2, rows 1, 2, 4 have 1s only in columns 1, 2, 4, so no power is nonzero in row 1, column 3: G_2 is disconnected. For G_1 the entry is 0 for k = 1, 2, 3 and 1 for k = 4; G_1 is the path (1, 3, 5, 2, 4), and d(1, 4) = 4.
10. Each diagonal entry of A^2 is a degree, 3, and two different vertices have 2 common neighbors, so A^2 = 2A + 3I. Then A^3 = 2A^2 + 3A = 2(2A + 3I) + 3A, which is 7A + 6I in the form asked. So 7 walks of length 3 join two different vertices, and \operatorname{tr}(A^3) = 4 \cdot 6 = 24 gives 24 / 6 = 4 = \binom{4}{3} triangles.
11. Proof. If (A^2)_{ij} \ge 2 with i \ne j, then v_i and v_j have two different common neighbors x and y (Result 4(a)). Neither is v_i or v_j, since no vertex is its own neighbor, so (v_i, x, v_j, y, v_i) is a cycle of length 4. Conversely a cycle (a, b, c, d, a) makes b and d two common neighbors of a \ne c. \square
12. Proof. By Result 3 the sum counts all walks (u, x, w) of length 2. For a middle vertex x, u and w are any neighbors of x, chosen independently and possibly equal: \deg(x)^2 walks. Adding over x gives the claim. \square
13. Proof. If (A^k)_{ii} > 0 for an odd k, Result 3 gives a closed walk of odd length k at v_i, and by Result 5 of Walks, paths, cycles and connected graphs it contains a cycle of odd length, a contradiction. \square
14. Proof. (M^3)_{ii} counts directed walks (v_i, x, y, v_i). With no loops, x \ne v_i, y \ne x, y \ne v_i: a directed cycle of length 3 starting at v_i. Arcs fix the direction, so each such cycle is counted once at each of its 3 vertices. \square For D the diagonal of M^3 is 1, 2, 2, 1, and 6 = 3 \cdot 2 for the cycles (1, 2, 3, 1) and (2, 3, 4, 2).
15. P_n is connected and d(1, n) = n - 1, so by Result 4(c) (A^k)_{1n} = 0 for every k \le n - 2, and I + A + \cdots + A^{n-2} has a zero in row 1, column n.
16. Counterexample: the path P_6, and a 4-cycle with a separate edge. Both have degree sequence (2, 2, 2, 2, 1, 1) and no triangle, so \operatorname{tr}(A^3) = 0 for both. An isomorphism carries walks to walks and so keeps connectedness; P_6 is connected and the other is not.