A two-dimensional array representation of a finite graph whose (i,j) entry records the presence and possibly the weight of an edge between node i and node j.

Principle

Encode discrete connectivity in a linear-algebraic object so that graph operations become matrix operations.

Demonstration

For an undirected simple graph with nodes {1,2,3,4} and edges {1–2,2–3,3–4}, the adjacency matrix A has zeros on the diagonal and ones at positions (1,2),(2,1),(2,3),(3,2),(3,4),(4,3).

Misapplication

Treating the same adjacency matrix as a complete descriptor for a multigraph without extending entries to counts leads to loss of multiplicity information.

Consequence

Enables use of matrix algebra (powers, products, index calculations) to study walks, connectivity, and combinatorial properties of the graph.

Reversal

An incidence matrix instead records node–edge incidences rather than direct node–node connections, shifting focus from adjacency to edge membership.

Boundary

Defined for finite graphs; for hypergraphs, multilayer networks, or labeled-edge structures the basic binary adjacency must be extended or replaced.

Semantic Tension

Versus a weighted adjacency: the unqualified adjacency matrix often implies binary entries, while many analyses assume or require real-valued weights.

Synthesis

A compact matrix whose pattern of entries is a direct linear-algebraic encoding of which nodes are connected and how strongly in a finite graph.