Adjacency Matrix

The adjacency matrix is a fundamental way to represent a graph as a square matrix. Each entry indicates whether a pair of vertices is connected by an edge. This representation enables the application of linear algebra to graph problems, revealing deep connections between graph structure and matrix properties. This page covers the definition, properties, and applications of adjacency matrices for both simple and weighted graphs.

Definition

Simple Graphs

For a simple graph G=(V,E) with n vertices labeled 1,2,…,n, the adjacency matrix A is an n×n matrix where:

(A_i*j)={[1,if *(i,j)∈E],[0,otherwise])

In other words, the entry in row i and column j is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

Directed Graphs

For a directed graph (digraph), the adjacency matrix is defined similarly, but it is generally not symmetric:

(A_i*j)={[1,if there is an edge from *i* to *j],[0,otherwise])

Here (A_i*j)=1 means there is a directed edge from vertex i to vertex j.

Weighted Graphs

For a weighted graph with edge weights w(i,j), the adjacency matrix becomes:

(A_i*j)={[w(i,j),if *(i,j)∈E],[0* or *∞,otherwise])

The choice of 0 or ∞ for non-edges depends on the application. For shortest path problems, ∞ is often used; for other applications, 0 may be appropriate.

Basic Properties

Symmetry

For an undirected graph, the adjacency matrix is symmetric:

A=AT

This is because an undirected edge (i,j) implies both (A_i*j)=1 and (A_j*i)=1. For directed graphs, the matrix is generally not symmetric.

Degree and Row/Column Sums

For an undirected simple graph, the degree of vertex i equals the sum of row i (or column (i):

deg*(i)=(∑_j=1^n)((A_i*j))=(∑_j=1^n)((A_j*i))

For directed graphs, the row sum gives the out-degree and the column sum gives the in-degree:

deg+*(i)=(∑_j=1^n)((A_i*j)),deg−*(i)=(∑_j=1^n)((A_j*i))

Number of Edges

The total number of edges can be computed from the trace or the sum of entries:

|E|=1/2*(∑_i,j^)((A_i*j)) (undirected), |E|=(∑_i,j^)((A_i*j)) (directed)

Path Counting

One of the most powerful properties of the adjacency matrix is its connection to counting paths.

Theorem: Powers of the Adjacency Matrix

The (i,j) entry of Ak gives the number of walks of length k from vertex i to vertex j:

(Ak)(i*j)= number of walks of length kfrom i to j

Proof by Induction

Base case (k=1): A1=A, and (A_i*j)=1 if and only if there is an edge (a walk of length 1) from i to j.

Inductive step: Assume (Ak)(i*j) counts walks of length k. Then:

(A(k+1))(i*j)=(∑_m=1^n)(Ak)*(A_m*j)

A walk of length k+1 from i to j consists of a walk of length k from i to some vertex m, followed by an edge from m to j. Summing over all possible intermediate vertices m gives the total count.

Application: Triangles

The number of triangles in an undirected graph is:

triangles =1/6*tr(A3)=1/6*(∑_i=1^n)(A3)

The diagonal entry (A3)(i*i) counts closed walks of length 3 starting and ending at vertex i. Each triangle is counted 6 times (once for each starting vertex and direction), hence the factor of 1/6.

Spectral Properties

The eigenvalues and eigenvectors of the adjacency matrix reveal important structural information about the graph.

Real Eigenvalues

For undirected graphs, the adjacency matrix is symmetric, so all eigenvalues are real. Let (λ_1)≥(λ_2)≥⋯≥(λ_n) be the eigenvalues.

Largest Eigenvalue

The largest eigenvalue (λ_1) (spectral radius) satisfies:

δ≤(λ_1)≤Δ

where δ is the minimum degree and Δ is the maximum degree. For regular graphs (all vertices have the same degree d), (λ_1)=d.

Connectivity and Eigenvalues

The multiplicity of the eigenvalue (λ_1) equals the number of connected components of the graph. For a connected graph, (λ_1) has multiplicity 1.

Bipartiteness

A graph is bipartite if and only if its spectrum is symmetric about 0. That is, λ is an eigenvalue if and only if −λ is also an eigenvalue with the same multiplicity.

Related Matrix Representations

Degree Matrix

The degree matrix D is a diagonal matrix where (D_i*i)=deg(i):

D=diag(deg*(1),deg*(2),…,deg*(n))

Laplacian Matrix

The graph Laplacian is defined as L=D-A:

(L_i*j)={[deg⁡(i),if *i=j],[−1,if *i≠j* and *(i,j)∈E],[0,otherwise])

The Laplacian is positive semidefinite with smallest eigenvalue 0. The multiplicity of the zero eigenvalue equals the number of connected components.

Normalized Adjacency Matrix

The normalized adjacency matrix is often used in spectral clustering and random walks:

A=D(−1/2)*A*D(−1/2)

The eigenvalues of lie in [-1,1] for connected graphs.

Computational Considerations

Space Complexity

The adjacency matrix requires O(n2) space regardless of the number of edges. For sparse graphs (|E|≪n2), this is inefficient. Alternative representations like adjacency lists use O*(n+|E|) space.

Time Complexity of Operations

Checking if edge (i,j) exists: O(1) with adjacency matrix, O*(deg*(i)) with adjacency list.

Iterating over neighbors of vertex i: O(n) with adjacency matrix, O*(deg*(i)) with adjacency list.

Matrix multiplication Ak: O(n3) using standard multiplication, or O(n2.37) using fast matrix multiplication.

Applications

PageRank

The PageRank algorithm uses a modified adjacency matrix to rank web pages. The transition matrix
P=D(−1)*A represents random walk probabilities, and PageRank finds the dominant eigenvector of a damped version of P.

Spectral Clustering

The eigenvectors of the adjacency matrix (or Laplacian) are used to embed graph vertices into a low-dimensional space where clustering can be performed using standard algorithms like k-means.

Graph Neural Networks

Many graph neural network architectures use the adjacency matrix to aggregate information from neighboring nodes. The message passing operation often takes the form:

H(l+1)=σ*(A*H(l)*W(l))

where A is a normalized adjacency matrix, H(l) is the feature matrix at layer l, W(l) is a learnable weight matrix, and σ is an activation function.

Network Analysis

The adjacency matrix is fundamental in analyzing social networks, biological networks, and communication networks. Centrality measures, community detection, and influence propagation all use the adjacency matrix or its variants.

Special Cases

Complete Graph (K_n): The adjacency matrix is J−I, where J is the all-ones matrix. Eigenvalues: n−1 (with multiplicity 1) and −1 (with multiplicity n−1).

Cycle Graph (C_n): The adjacency matrix is a circulant matrix. Eigenvalues:
2*cos((2*π*k)/n) for k=0,1,…,n−1.

Path Graph (P_n): The adjacency matrix is tridiagonal with 1s on the super- and sub-diagonals.

Summary

The adjacency matrix A is an n×n matrix representing a graph, where
(A_i*j)=1 if there is an edge from vertex i to vertex j, and 0 otherwise. For undirected graphs, A is symmetric.

Key properties include: row/column sums give vertex degrees; (Ak)(i*j) counts walks of length k from i to j; the trace of A3 divided by 6 gives the triangle count.

The eigenvalues of A reveal structural properties: the largest eigenvalue is bounded by minimum and maximum degree; its multiplicity equals the number of connected components; symmetric spectrum indicates bipartiteness.

Related matrices include the Laplacian L=D−A. The adjacency matrix is widely used in network analysis, machine learning, and algorithm design.