Component Blocks And Adjacency Spectra

Why Connected Components Produce Matrix Blocks

An adjacency matrix records which pairs of vertices are joined by an edge. If a graph is disconnected, no edge joins vertices in different connected components. Consequently, when the vertices are listed component by component, the matrix entries connecting different components are all zero. The matrix separates into smaller square blocks, one for each component.

This structure also separates the eigenvalue calculation. The characteristic polynomial of the whole adjacency matrix is the product of the characteristic polynomials of the component matrices. Thus the eigenvalues of the graph are precisely the eigenvalues of its components, with repeated values counted as many times as they occur across those components.

Definition: A connected component of a graph $G$ is a maximal connected subgraph of $G$. The components partition $V(G)$. An isolated vertex is a component by itself. For a fixed ordering $v_1,\dots,v_n$ of the vertices, the adjacency matrix $\mathbf{A}(G)$ is the $n$ by $n$ matrix whose $i,j$ entry is $1$ when $v_i$ and $v_j$ are adjacent, and $0$ otherwise. For a simple graph its diagonal entries are zero.

A matrix is block diagonal if its diagonal is divided into square blocks and every entry outside those blocks is zero. To say that the adjacency matrix has a block form depends on the vertex ordering: the graph itself does not change when its vertices are listed differently.

Definition: The characteristic polynomial of an $n$ by $n$ matrix $A$ is $p_A(x)=\det(xI-A)$. Its eigenvalues are the roots of this polynomial, counted with their algebraic multiplicities (their multiplicities as polynomial roots). The adjacency spectrum of $G$ is the multiset of eigenvalues of $\mathbf{A}(G)$.

The Component Block Theorem

Theorem: Let $G$ be a finite simple graph with connected components $G_1,\dots,G_k$. Order the vertices by listing all vertices of $G_1$, then all vertices of $G_2$, and so on. In this ordering, $\mathbf{A}(G)$ is block diagonal, with diagonal blocks $\mathbf{A}(G_1),\dots,\mathbf{A}(G_k)$. Moreover, $$ p_{\mathbf{A}(G)}(x)=\prod_{i=1}^{k}p_{\mathbf{A}(G_i)}(x). $$ Therefore the adjacency spectrum of $G$ is the union of the component spectra, with algebraic multiplicities added.

Proof. Suppose the vertices of $G_i$ occupy one consecutive group of positions in the chosen ordering. If two positions belong to different groups, their vertices lie in different connected components. They cannot be adjacent, since an edge would connect those components. The corresponding adjacency-matrix entry is therefore zero. Within the positions for $G_i$, the entries record exactly the edges of $G_i$, so that diagonal block is $\mathbf{A}(G_i)$. This proves the block form.

Subtract this block matrix from $xI$. The result is block diagonal with diagonal blocks $xI_i-\mathbf{A}(G_i)$, where $I_i$ is the identity matrix of the order of $G_i$. The determinant of a block diagonal matrix is the product of the determinants of its diagonal blocks: in the determinant expansion, any term that selects an entry between distinct blocks is zero, and the remaining terms are exactly the products of the determinants of the separate blocks. Hence $$ p_{\mathbf{A}(G)}(x)=\det(xI-\mathbf{A}(G)) =\prod_{i=1}^{k}\det(xI_i-\mathbf{A}(G_i)) =\prod_{i=1}^{k}p_{\mathbf{A}(G_i)}(x). $$ The roots of a product of polynomials are the roots of its factors, and a root’s multiplicity in the product is the sum of its multiplicities in the factors. This gives the asserted spectrum, including repeated eigenvalues. $\square$

The theorem uses a convenient ordering, but the spectral conclusion does not depend on that choice. A different vertex ordering simultaneously permutes the rows and columns of the adjacency matrix. If $P$ is the permutation matrix for that reordering, the new matrix is $P^{T}\mathbf{A}(G)P$. Since $P^{T}P=I$, this is a similarity transformation, which preserves the characteristic polynomial: $\det(xI-P^{T}\mathbf{A}(G)P)=\det(P^{T}(xI-\mathbf{A}(G))P)=\det(xI-\mathbf{A}(G))$. Thus an interleaved ordering may hide the component blocks without changing the eigenvalues.

Worked Component Calculations

Worked Example: A Triangle and a Separate Edge

Let $G$ have vertex set $V(G)=\{a,b,c,d,e\}$ and edge set $E(G)=\{ab,bc,ca,de\}$. Its components are the triangle on $\{a,b,c\}$ and the edge on $\{d,e\}$. Order the vertices $a,b,c,d,e$. The adjacency matrix is

\mathbf{A}(G)= \begin{pmatrix} 0&1&1&0&0\\ 1&0&1&0&0\\ 1&1&0&0&0\\ 0&0&0&0&1\\ 0&0&0&1&0 \end{pmatrix}.

The first block is the triangle matrix $A_1$. Its characteristic polynomial is $$ \det(xI-A_1)= \det\begin{pmatrix}x&-1&-1\\-1&x&-1\\-1&-1&x\end{pmatrix} =x^3-3x-2=(x-2)(x+1)^2. $$ The second block, for the edge, has characteristic polynomial $$ \det\begin{pmatrix}x&-1\\-1&x\end{pmatrix}=x^2-1=(x-1)(x+1). $$ Therefore $$ p_{\mathbf{A}(G)}(x)=(x-2)(x+1)^2(x-1)(x+1). $$ The eigenvalues are $2$, $1$, and $-1$ with multiplicity $3$.

Check: There are five eigenvalues counted with multiplicity, matching the five vertices. Their sum is $2+1+3(-1)=0$, matching the trace of the displayed adjacency matrix. The eigenvalue $-1$ occurs twice in the triangle block and once in the edge block, so its total multiplicity is $3$.

Worked Example: Interleaved Vertices and Isolates

Let $G$ have vertex set $V(G)=\{u,z,v,w\}$ and edge set $E(G)=\{uv,vw\}$. Its components are the path $u,v,w$ and the isolated vertex $z$. In the listed order $u,z,v,w$, the adjacency matrix is $$ \mathbf{A}(G)= \begin{pmatrix} 0&0&1&0\\ 0&0&0&0\\ 1&0&0&1\\ 0&0&1&0 \end{pmatrix}. $$ The path’s vertices are interleaved with the isolate, so the component blocks are not consecutive. Reorder the vertices as $u,v,w,z$. The matrix becomes $$ \begin{pmatrix} 0&1&0&0\\ 1&0&1&0\\ 0&1&0&0\\ 0&0&0&0 \end{pmatrix}. $$ The path block has characteristic polynomial $x(x^2-2)$: expanding the determinant of $\begin{pmatrix}x&-1&0\\-1&x&-1\\0&-1&x\end{pmatrix}$ along the first row gives $x(x^2-1)-x=x^3-2x$. The isolate contributes the $1$ by $1$ block $(0)$, whose characteristic polynomial is $x$. Hence the full polynomial is $x^2(x^2-2)$, and the eigenvalues are $\sqrt{2},-\sqrt{2},0,0$.

Check: The four values account for four vertices. Their sum is $\sqrt{2}-\sqrt{2}+0+0=0$, equal to the trace. The zero eigenvalue occurs once in the path block and once in the isolated-vertex block.

Worked Example: Repeated Zero Eigenvalues from Isolated Vertices

Let $G$ have vertex set $V(G)=\{1,2,3,4\}$ and edge set $E(G)=\{12\}$. The components are the edge on $\{1,2\}$ and the isolated vertices $3$ and $4$. In this component order, $$ \mathbf{A}(G)= \begin{pmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{pmatrix}. $$ The edge block has characteristic polynomial $x^2-1$. Each isolated vertex contributes the polynomial $x$. Thus $$ p_{\mathbf{A}(G)}(x)=(x^2-1)x^2, $$ so the spectrum is $1,-1,0,0$.

Check: The edge block has eigenvectors $(1,1)$ and $(1,-1)$, with eigenvalues $1$ and $-1$, respectively: multiplying by $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ gives $(1,1)$ and $(-1,1)=-(1,-1)$. The two isolate coordinates contribute two independent zero eigenvectors. This verifies both the values and their multiplicities.

Using the Result Carefully

Component blocks are useful because they reduce a potentially large characteristic-polynomial calculation to separate calculations on smaller matrices. If a graph has components of orders $n_1,\dots,n_k$, then each component contributes exactly $n_i$ eigenvalues counted with algebraic multiplicity, and $n_1+\cdots+n_k=|V(G)|$. Component eigenvalues that happen to be equal must still be counted separately. The theorem gives a multiset union, not a set of distinct values.

One can also reverse the reasoning: if the graph has been defined by separate components, calculate each component’s characteristic polynomial and multiply. This does not require the components to be isomorphic. If two components are isomorphic, their adjacency matrices differ only by a simultaneous row-and-column permutation, so their characteristic polynomials agree; that polynomial then appears as a repeated factor.

For the graph with no vertices, there are no components and the adjacency matrix is the $0$ by $0$ matrix. With the determinant of the $0$ by $0$ matrix taken to be $1$, its characteristic polynomial is $1$; it has no eigenvalues. The product over no components is also $1$, so the theorem remains consistent in this case.

Common Pitfall: Confusing Vertex Order with Graph Structure

A wrong conclusion is: “The matrix in the original ordering is not visibly block diagonal, so the graph does not split into component blocks.” In the second example, the order $u,z,v,w$ puts a zero row and column for $z$ between entries belonging to the path. The matrix is not displayed as two consecutive diagonal blocks in that order, but the graph still has exactly two components. Reordering to $u,v,w,z$ reveals the blocks. The correction is to identify components from the graph, then group their vertices together before reading off the blocks.

A second common error is to report only distinct eigenvalues. For the edge and two isolates, the distinct values are $1,-1,0$, but the spectrum has four entries counted with multiplicity: $1,-1,0,0$. The characteristic polynomial $x^2(x^2-1)$ makes the repeated zero explicit. Always compare the total multiplicity with the number of vertices.

Check Your Understanding

Use component blocks and characteristic polynomials to justify your answers.

Let $G$ have vertex set $\{1,2,3,4,5\}$ and edge set $\{12,23,45\}$. Identify its components and describe how the adjacency matrix can be ordered into blocks.
Suppose a graph has three components with characteristic polynomials $(x-2)(x+1)$, $x(x-1)$, and $x$. Write the characteristic polynomial of the whole graph and list its eigenvalues with multiplicity.
Explain why changing the vertex ordering cannot change the adjacency spectrum.
A graph has six vertices, and its component spectra have sizes $2$, $1$, and $3$, counting multiplicity. What consistency check can you make before combining the spectra?
Why does an isolated vertex contribute the eigenvalue $0$, and how does that affect multiplicities when there is more than one isolate?