1 Adjacency Matrix Fundamentals

1.1 Definition and construction from a graph

An adjacency matrix is a square matrix used to represent a finite graph by encoding which vertex pairs are connected. For a graph with \(n\) vertices, the adjacency matrix \(A\) has size \(n \times n\). Its entry \(A_{ij}\) records the presence or weight of an edge from vertex \(i\) to vertex \(j\). This encoding turns graph structure into an object suitable for algebraic manipulation and algorithmic computation.

1.2 Vertex ordering and indexing conventions

Because matrix rows and columns correspond to vertex indices, the adjacency matrix depends on how vertices are labeled. Choosing an ordering \(v_1,\dots,v_n\) determines the mapping between vertex pairs and matrix positions. With a different ordering, the same underlying graph produces a permuted matrix: if vertices are relabeled by a permutation, the adjacency matrix changes by simultaneous permutation of rows and columns. This matters for interpretation and for comparing matrices coming from different labelings.

1.3 Interpreting matrix entries (binary vs weighted)

For simple unweighted graphs, \(A_{ij}\) is often binary: \(A_{ij}=1\) if an edge exists between the relevant vertices (or in the directed case, if there is an edge from \(i\) to \(j\)), and \(A_{ij}=0\) otherwise. For weighted graphs, entries store a numerical weight associated with each edge. In that setting, matrix operations capture weighted relationships, and quantities derived from \(A\) reflect how weights influence connectivity, walk counts (when interpreted appropriately), and spectral behavior.

1.4 Undirected vs directed graph representations

For an undirected graph, edges have no orientation, so the connection between \(i\) and \(j\) is reciprocal. The adjacency matrix typically satisfies \(A_{ij}=A_{ji}\). For a directed graph (digraph), edges are oriented, so \(A_{ij}\) indicates whether a directed edge goes from \(i\) to \(j\). In general, \(A_{ij}\) and \(A_{ji}\) can differ, making the matrix asymmetric in most nontrivial cases.

2 Properties and Structural Variants

2.1 Symmetry and diagonal entries

Symmetry characterizes undirected graphs: when the underlying graph is undirected and labels are consistent, the adjacency matrix is symmetric. Diagonal entries \(A_{ii}\) encode whether a vertex is connected to itself. Whether diagonal entries are allowed to be nonzero depends on the modeling choice: some conventions forbid self-connections (leading to zeros on the diagonal), while others permit them.

2.2 Loops and multiple edges (representation choices)

A loop at vertex \(i\) is represented by a nonzero diagonal entry \(A_{ii}\). For graphs that allow multiple edges between the same ordered pair of vertices, there are two common approaches: either aggregate them into a single entry (e.g., store the count of edges or the sum of weights) or represent the graph in a more granular structure such as a multigraph incidence encoding. With aggregation, the adjacency matrix remains a standard square matrix but carries combined information rather than edge-by-edge detail.

2.3 Complement graphs and matrix relationships

The complement of a simple graph swaps adjacency and non-adjacency for every distinct vertex pair. In matrix terms for an \(n\)-vertex simple undirected graph, this can be expressed using an all-ones matrix \(J\) and adjusting for the diagonal. Roughly, off-diagonal entries change from 1 to 0 and from 0 to 1; diagonal entries are handled according to whether self-loops are included in the model. This relationship provides algebraic ways to reason about how complement operations affect spectra and derived counts.

2.4 Bipartite graphs and block structure

A bipartite graph splits vertices into two disjoint sets such that edges run only between the sets. With an ordering that places vertices from the first part first and the second part last, the adjacency matrix acquires a block form where edges appear only in off-diagonal blocks and the diagonal blocks are zero (assuming no edges within each part). This block structure is a useful structural signature and can simplify certain spectral or algorithmic analyses.

3 Algebraic Relationships

3.1 Degree information from row/column sums

Row sums and column sums connect adjacency matrices to degrees. In an undirected simple graph, the degree of vertex \(i\) equals the sum of the entries in row \(i\) (equivalently, column \(i\)). In a directed graph, the row sum typically corresponds to out-degree (edges leaving \(i\)), while the column sum corresponds to in-degree (edges entering \(i\)). With weighted edges, these sums generalize to weighted degrees.

3.2 Adjacency matrix powers and walks

3.2.1 Counting walks using (A^k) entries

Powers of the adjacency matrix encode walks in the graph. Specifically, for unweighted graphs, the entry \((A^k)_{ij}\) equals the number of length-\(k\) walks from vertex \(i\) to vertex \(j\), where a walk allows revisiting vertices and edges. This correspondence arises because matrix multiplication aggregates intermediate steps: each multiplication by \(A\) extends walks by one edge.

3.2.2 Cycles and path length interpretations

Walk-based interpretations extend beyond counting. In undirected or directed graphs, diagonal entries of \(A^k\) count length-\(k\) closed walks starting and ending at the same vertex. While counting closed walks differs from counting simple cycles (which forbid repeating vertices), the adjacency powers still provide a foundation for analyzing cycle-like structures and understanding how quickly information propagates along paths of bounded length.

3.3 Neighborhoods from the adjacency matrix

Neighborhoods can be read directly from the adjacency matrix: the set of vertices adjacent to \(i\) corresponds to indices \(j\) where \(A_{ij}\) is nonzero. For weighted graphs, “adjacent” can be interpreted as having positive (or nonzero) weight under the chosen convention. For distances beyond one step, neighborhoods at distance \(k\) can be related to whether \((A^k)_{ij}\) is positive (in unweighted cases), or whether there exists a walk of length \(k\) connecting \(i\) and \(j\).

3.4 Reachability via matrix-based methods

Reachability concerns whether some walk exists between two vertices. In unweighted graphs, the boolean version of matrix powers can be used: if a positive entry appears in \((A^k)_{ij}\) for some \(k\), then \(j\) is reachable from \(i\). More generally, reachability is captured by transitive closure. Standard approaches compute closure using repeated squaring or specialized algorithms, producing a matrix indicating which pairs of vertices are connected by at least one directed path.

4 Spectral Graph Theory Basics

4.1 Eigenvalues and eigenvectors interpretation

Spectral graph theory studies properties of graphs through the eigenvalues and eigenvectors of matrices such as the adjacency matrix. Eigenvectors can be interpreted as patterns over vertices, and eigenvalues quantify how strongly those patterns align with the graph’s connectivity structure. In practice, dominant eigenvalues and their associated vectors often correlate with global features like clustering tendencies, expansion behavior, or community-like separations in certain models.

4.2 Spectral radius and graph connectivity intuition

The spectral radius of the adjacency matrix (the largest magnitude among eigenvalues) serves as a summary statistic for connectivity and growth in walk counts. Because \(A^k\) counts walks, the long-run behavior of walk numbers is governed by the largest eigenvalue in magnitude. As a result, graphs with “more” or “denser” connectivity often exhibit larger spectral radius, though precise relationships depend on the graph class and normalization choices.

4.3 Laplacian vs adjacency matrices (comparison)

4.3.1 Derived matrices and their eigen-structure

While the adjacency matrix encodes direct edges, the Laplacian emphasizes differences between neighboring vertices. For an undirected graph, the combinatorial Laplacian is \(L=D-A\), where \(D\) is the diagonal degree matrix. The Laplacian’s eigenvalues have direct interpretations related to connectivity: the multiplicity of the zero eigenvalue corresponds to the number of connected components. Adjacency spectra and Laplacian spectra complement each other; adjacency is tied to walk counts and neighbor-weighting, whereas Laplacian focuses on smoothness and variation across the graph.

5 Computational and Practical Considerations

5.1 Storage formats (dense vs sparse matrices)

For graphs with many vertices but relatively few edges, the adjacency matrix is largely filled with zeros, making dense storage inefficient. Sparse matrix formats store only nonzero entries (and associated indices), reducing memory and improving speed for operations that avoid touching zeros. For smaller graphs or very dense graphs, dense representations can be faster due to simpler memory access patterns. The chosen format affects algorithm performance, particularly in iterative methods relying on repeated matrix-vector multiplications.

5.2 Complexity of basic operations

Basic tasks scale differently depending on the operation and representation. Accessing or modifying individual entries is straightforward for dense matrices, while sparse structures require traversal or indexing strategies. Multiplying by a vector is typically far cheaper in sparse form, roughly proportional to the number of edges rather than \(n^2\). Eigenvalue computations can be significantly more demanding than simple multiplication, often motivating specialized solvers and approximations.

5.3 Numerical stability and floating-point weights

When adjacency entries are floating-point weights, computations involving matrix powers, eigen-decompositions, or iterative solvers can accumulate rounding errors. Stability depends on conditioning, the magnitude and distribution of weights, and algorithmic choices such as normalization and stopping criteria. Careful handling may involve scaling, using numerically stable factorization methods, or preferring algorithms designed for sparse and potentially ill-conditioned matrices.

5.4 Example workflows in graph algorithms

Many graph algorithms proceed through a pipeline involving adjacency construction, transformation, and computation. A typical workflow is: (1) build an adjacency representation from data (edges and weights), (2) select a computational model (dense or sparse), (3) compute derived objects such as degree matrices or Laplacians when needed, and (4) run an algorithm such as walk-based propagation, spectral embedding, or clustering using eigenvectors. Verification steps often include checking expected structural properties, such as symmetry for undirected graphs or zero diagonal when self-loops are excluded.

6 Examples and Worked Illustrations

6.1 Small undirected graph example

Consider an undirected graph with vertices \(\{1,2,3,4\}\) and edges \(\{(1,2),(1,3),(2,4),(3,4)\}\). Using the vertex order \(1,2,3,4\), the adjacency matrix is \[ A= \begin{pmatrix} 0&1&1&0\\ 1&0&0&1\\ 1&0&0&1\\ 0&1&1&0 \end{pmatrix}. \] This matrix is symmetric because the graph is undirected. The row sums give degrees: vertex 1 has degree 2, vertex 2 has degree 2, and so on.

6.2 Small directed graph example

Take a directed graph with vertices \(\{1,2,3\}\) and directed edges \((1,2)\), \((2,3)\), and \((1,3)\). With the order \(1,2,3\), \[ A= \begin{pmatrix} 0&1&1\\ 0&0&1\\ 0&0&0 \end{pmatrix}. \] Here \(A_{12}=1\) because there is an edge from 1 to 2, while \(A_{21}=0\) because there is no edge from 2 to 1. The entry \((A^2)_{13}=1\) reflects the unique length-2 walk from 1 to 3 via vertex 2.

6.3 Weighted graph example

Let a weighted undirected graph have vertices \(\{1,2,3\}\) with weights \(w(1,2)=2\), \(w(1,3)=0.5\), and \(w(2,3)=3\). The adjacency matrix is \[ A= \begin{pmatrix} 0&2&0.5\\ 2&0&3\\ 0.5&3&0 \end{pmatrix}. \] In this representation, matrix products combine weights along walks, so \((A^k)_{ij}\) aggregates the total weight contributions of length-\(k\) walks (under the convention that each step multiplies corresponding edge weights).

6.4 Verifying properties from a given matrix

Given a candidate adjacency matrix \(A\), one can check structural assumptions. For an undirected graph model, verify \(A=A^\top\). To exclude self-loops, confirm that \(\mathrm{diag}(A)\) is all zeros. For a bipartite claim under a known vertex partition, check that entries are zero within each part and possibly nonzero across parts after applying the chosen vertex ordering. These checks provide quick validation before running downstream computations.

7.1 Incidence matrix and alternative encodings

An incidence matrix represents graphs by relating vertices to edges rather than vertex pairs. Each column corresponds to an edge and indicates which vertices are incident to it. Compared with adjacency matrices, incidence matrices can handle certain modeling details (like edge-specific attributes) in a more direct way, at the cost of larger and less directly neighbor-oriented representations.

7.2 Incidence matrix vs adjacency matrix tradeoffs

Adjacency matrices emphasize connectivity between vertex pairs and are well suited to computations involving walks, spectra, and matrix powers. Incidence matrices are often preferable when edge identity matters, such as when different edges between the same vertices must be kept separate. Additionally, adjacency matrices can become memory-inefficient for very sparse graphs, whereas incidence matrices can remain compact depending on the data layout and the specific graph representation.

7.3 Common graph transformations affecting the matrix

Transformations such as relabeling vertices correspond to permuting rows and columns. Edge complementation alters off-diagonal entries (for simple graphs). Taking subgraphs corresponds to zeroing or removing entries associated with removed edges and adjusting dimensions when vertices are deleted. These operations change the adjacency matrix in predictable ways, which is important for correctness when composing algorithms or comparing results across different graph preprocessing steps.

7.4 Pointers to spectral and walk-based methods

Many advanced techniques leverage adjacency or related matrices. Spectral methods use eigenvalues/eigenvectors for embeddings, clustering, and diffusion-like processes. Walk-based methods use matrix powers or transitive closure ideas for reachability, connectivity via paths of limited length, and propagation dynamics. Familiarity with both viewpoints helps interpret algorithm outputs and diagnose unexpected behavior.