Common Errors In Interpreting Graph Matrices

Why Matrix Interpretation Needs Care

A graph matrix records information only after its rows and columns have been assigned to vertices. A correct-looking entry can describe the wrong pair of vertices if the ordering is forgotten. Other common errors come from treating powers of the adjacency matrix as though their diagonal entries were always zero, reversing the signs in the Laplacian, or confusing Laplacian nullity with connectedness when a graph has several components.

Throughout, graphs are finite and simple. Choose an ordering \(v_1,\dots,v_n\) of \(V(G)\). The adjacency matrix \(\mathbf A(G)\) has entry \(1\) in position \(i,j\) if \(v_iv_j\in E(G)\), and \(0\) otherwise. The degree matrix \(\mathbf D(G)\) is diagonal, with entry \(\deg(v_i)\) in position \(i,i\). The Laplacian is \(\mathbf L(G)=\mathbf D(G)-\mathbf A(G)\). These matrices are symmetric for undirected graphs.

Vertex Order Is Part of the Calculation

Suppose the original ordering is \(v_1,\dots,v_n\), and a new ordering is \(w_1,\dots,w_n\). Let \(P\) be the permutation matrix whose \(i\)th column is the coordinate vector of \(w_i\) in the original ordering. Then the adjacency and Laplacian matrices in the new ordering are \(P^{\mathsf T}\mathbf A P\) and \(P^{\mathsf T}\mathbf L P\). This simultaneously permutes rows and columns. Permuting just rows, or just columns, does not in general give the matrix of the same undirected graph in a new ordering.

Proof. The matrix \(P\) is invertible and \(P^{-1}=P^{\mathsf T}\). Thus \(P^{\mathsf T}\mathbf A P=P^{-1}\mathbf A P\), which is similar to \(\mathbf A\). Similar matrices have the same characteristic polynomial, because \(\det(xI-P^{-1}\mathbf A P)=\det(P^{-1}(xI-\mathbf A)P)=\det(xI-\mathbf A)\). The same argument applies to \(\mathbf L\). \(\square\)

What the Diagonal of an Adjacency Power Counts

Proof. For \(k=0\), \(\mathbf A^0=I\); its entry \(i,j\) is \(1\) if \(i=j\) and \(0\) otherwise, which counts the length-zero walks. Assume the claim holds for \(k\). By matrix multiplication, \((\mathbf A^{k+1})_{ij}=\sum_{r=1}^n(\mathbf A^k)_{ir}A_{rj}\). A walk of length \(k+1\) from \(v_i\) to \(v_j\) has a unique penultimate vertex \(v_r\). There are \((\mathbf A^k)_{ir}\) walks of length \(k\) to \(v_r\), and \(A_{rj}=1\) exactly when the final step from \(v_r\) to \(v_j\) is an edge. Summing over \(r\) counts each such walk once. This proves the claim by induction. \(\square\)

For a simple graph, \((\mathbf A)_{ii}=0\) because there are no loops. But \((\mathbf A^2)_{ii}=\deg(v_i)\): each length-two closed walk from \(v_i\) goes to one of its neighbors and immediately returns. For higher powers, diagonal entries can count closed walks that travel around cycles, including walks that revisit vertices.

Laplacian Signs and Disconnected Graphs

Since \(\mathbf L=\mathbf D-\mathbf A\), its diagonal entry at \(v_i\) is \(\deg(v_i)\), and its \(i,j\) entry for distinct vertices is \(-1\) when \(v_iv_j\) is an edge and \(0\) otherwise. In particular, the off-diagonal edge entries are negative, not positive. Each row sums to zero: the diagonal degree is cancelled by one \(-1\) for each neighbor.

Proof. For a vector \(x\) with coordinates \(x_v\), expansion of \(\mathbf L=\mathbf D-\mathbf A\) gives \(x^{\mathsf T}\mathbf Lx=\sum_{uv\in E(G)}(x_u-x_v)^2\). If \(\mathbf Lx=0\), then this sum is \(0\); every term is nonnegative, so \(x_u=x_v\) on every edge. Along paths, \(x\) is therefore constant on each connected component. Conversely, if \(x\) is constant on each component, then at every vertex \(v\), \((\mathbf Lx)_v=\deg(v)x_v-\sum_{u\in N(v)}x_u=0\), including at an isolated vertex where both terms are zero. The nullspace is exactly the set of vectors constant on each component. The indicator vectors of the components form a basis for this space, so its dimension is the number of components. If \(V(G)\) is empty, the space has dimension zero, as asserted. \(\square\)

Spectral Symmetry and Bipartiteness

The adjacency spectrum is the multiset of eigenvalues of \(\mathbf A(G)\), with each eigenvalue repeated according to its multiplicity. A spectrum is symmetric about \(0\) if every eigenvalue \(\lambda\) occurs as often as \(-\lambda\). A standard result proved earlier is that a bipartite graph has a symmetric adjacency spectrum. The reverse implication also holds; it is unsafe to call spectral symmetry merely a necessary condition.

Proof. Let the eigenvalues, counted with multiplicity, be \(\lambda_1,\dots,\lambda_n\). For every positive odd integer \(k\), symmetry pairs each \(\lambda\) with \(-\lambda\), whose \(k\)th powers sum to zero; any zero eigenvalues also contribute zero. Hence \(\sum_i\lambda_i^k=0\). Since \(\mathbf A\) is real symmetric, its eigenvalues are real and the spectral theorem gives \(\operatorname{tr}(\mathbf A^k)=\sum_i\lambda_i^k=0\).

By the walk-counting theorem, the diagonal entries of \(\mathbf A^k\) count closed walks, so they are nonnegative. If the graph had an odd cycle of length \(k\), traversing that cycle from any of its vertices gives a closed walk of length \(k\). Therefore at least one diagonal entry of \(\mathbf A^k\) would be positive, making its trace positive, a contradiction. Thus the graph has no odd cycle.

For completeness, a graph with no odd cycle is bipartite. In each connected component with at least one vertex, choose a root \(r\), and partition vertices according to whether their distance from \(r\) is even or odd. If an edge joined vertices \(u,v\) of the same parity, shortest paths from \(r\) to \(u\) and \(v\), together with \(uv\), would give an odd closed walk. Every odd closed walk contains an odd cycle: if it repeats a vertex other than its repeated start and end, split it at that repeated vertex into two shorter closed walks; their lengths sum to an odd number, so one is odd, and repetition of this reduction ends at an odd cycle. This contradicts the absence of odd cycles. Hence every edge crosses the parity partition in each component. Combining those partitions gives a bipartition of the whole graph; isolated vertices form singleton components and cause no difficulty. \(\square\)

Practical Checks Before Drawing Conclusions

When a matrix calculation seems to contradict the graph, check the vertex ordering first. Then check the defining formula and compare matrix entries with graph features: adjacency diagonals are zero for simple graphs, row sums of \(\mathbf A\) are degrees, Laplacian diagonals are degrees, and Laplacian row sums are zero. For powers of \(\mathbf A\), interpret entries as walk counts rather than as adjacency indicators. For component questions, use the Laplacian nullity theorem, not the multiplicity of zero as an adjacency eigenvalue.

Finally, distinguish a proved implication from a guess based on a familiar example. Bipartiteness gives spectral symmetry, and spectral symmetry also forces bipartiteness for finite simple undirected graphs. The reverse direction is not an unsupported assumption: the odd-power trace argument proves it. These conclusions rely on the adjacency matrix being real symmetric, as it is for the undirected graphs considered here.