---
title: "AdjacencyMatrix"
language: "en"
type: "Symbol"
summary: "AdjacencyMatrix[g] gives the vertex\\[Dash]vertex adjacency matrix of the graph g. AdjacencyMatrix[{v -> w, ...}] uses rules v -> w to specify the graph g."
keywords: 
- connectivity matrix
- node-node matrix
- vertex-vertex matrix
- node-node relation
- vertex-vertex relation
- matrix as graph
- sociomatrix
- sociogram
canonical_url: "https://reference.wolfram.com/language/ref/AdjacencyMatrix.html"
source: "Wolfram Language Documentation"
related_guides: 
  - 
    title: "Graphs and Matrices"
    link: "https://reference.wolfram.com/language/guide/GraphsAndMatrices.en.md"
  - 
    title: "Graph Construction & Representation"
    link: "https://reference.wolfram.com/language/guide/GraphConstructionAndRepresentation.en.md"
  - 
    title: "Graph Programming"
    link: "https://reference.wolfram.com/language/guide/GraphProgramming.en.md"
  - 
    title: "Computation on Graphs"
    link: "https://reference.wolfram.com/language/guide/ComputationOnGraphs.en.md"
related_functions: 
  - 
    title: "AdjacencyGraph"
    link: "https://reference.wolfram.com/language/ref/AdjacencyGraph.en.md"
  - 
    title: "WeightedAdjacencyMatrix"
    link: "https://reference.wolfram.com/language/ref/WeightedAdjacencyMatrix.en.md"
  - 
    title: "IncidenceMatrix"
    link: "https://reference.wolfram.com/language/ref/IncidenceMatrix.en.md"
  - 
    title: "KirchhoffMatrix"
    link: "https://reference.wolfram.com/language/ref/KirchhoffMatrix.en.md"
  - 
    title: "VertexIndex"
    link: "https://reference.wolfram.com/language/ref/VertexIndex.en.md"
  - 
    title: "DistanceMatrix"
    link: "https://reference.wolfram.com/language/ref/DistanceMatrix.en.md"
---
# AdjacencyMatrix

AdjacencyMatrix[g] gives the vertex–vertex adjacency matrix of the graph g.

AdjacencyMatrix[{v -> w, …}] uses rules v -> w to specify the graph g.

## Details

* An adjacency matrix is also known as a connectivity matrix.

[image]

* ``AdjacencyMatrix`` returns a ``SparseArray`` object, which can be converted to an ordinary matrix using ``Normal``.

* An entry ``aij`` of the adjacency matrix is the number of directed edges from vertex ``νi`` to vertex ``νj``.

* The diagonal entries ``aii`` count the number of loops for vertex ``vi``.

* An undirected edge is interpreted as two directed edges with opposite directions.

* The vertices ``vi`` are assumed to be in the order given by ``VertexList[g]``.

* The adjacency matrix for a graph will have dimensions $n$×$n$, where $n$ is the number of vertices.

## Background & Context

``AdjacencyMatrix`` returns a square matrix whose rows and columns correspond to the vertices of a graph and whose elements ``aij`` are non-negative integers that give the numbers of (directed) edges from vertex ``vi`` to vertex ``vj``. An adjacency matrix provides a useful representation of a graph that can be used to compute many properties by means of simple operations on matrices. Examples of computations on graphs that can be performed efficiently given an adjacency matrix include vertex degrees, in- and out-degrees, counts of paths between vertices in at most $k$ steps, graph spectrum, and many others.

For a graph on $n$ vertices, the adjacency matrix has dimensions $n$×$n$. For an undirected graph, the adjacency matrix is symmetric. For a finite simple graph (i.e. an undirected, unweighted graph with no self-loops or multiple edges), the adjacency matrix must have 0s on the diagonal, and its matrix elements are given by $a_{ij}=1$ if $v_i$ is adjacent to $v_j$ and $a_{ij}=0$ otherwise.

An explicit adjacency matrix representation of a graph based on a particular ordering of vertices is unique. However, since the vertices of a graph may be permuted, there is a class of adjacency matrices that represents the corresponding isomorphism class of graphs. Nonetheless, the adjacency matrix for an isomorphism class is unique modulo permutation of rows and columns of the matrix (corresponding precisely to relabeling of the graph vertices).

``AdjacencyGraph`` can be used to construct a graph from an adjacency matrix. ``IncidenceMatrix`` gives another matrix representation of a graph that gives vertex-edge relationships instead of vertex-vertex relationships. ``AdjacencyMatrix`` does not take graph weights into account, so ``WeightedAdjacencyMatrix`` must be used when computing the adjacency matrix of a graph having edge weights.

---

## Examples (29)

### Basic Examples (2)

The adjacency matrix of an undirected graph:

```wl
In[1]:= Graph[{1\[UndirectedEdge]2, 2\[UndirectedEdge]3, 3\[UndirectedEdge]1}]

Out[1]= [image]

In[2]:= AdjacencyMatrix[%]//MatrixForm

Out[2]//MatrixForm=
(⁠|   |   |   |
| - | - | - |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |⁠)
```

---

The adjacency matrix of a directed graph:

```wl
In[1]:= Graph[{1\[DirectedEdge]2, 2\[DirectedEdge]3, 3\[DirectedEdge]1}]

Out[1]= [image]

In[2]:= AdjacencyMatrix[%]//MatrixForm

Out[2]//MatrixForm=
(⁠|   |   |   |
| - | - | - |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 0 |⁠)
```

### Scope (5)

The adjacency matrix of an undirected graph is symmetric:

```wl
In[1]:= Graph[{1\[UndirectedEdge]2, 1\[UndirectedEdge]3, 2\[UndirectedEdge]3, 2\[UndirectedEdge]4, 3\[UndirectedEdge]4}]

Out[1]= [image]

In[2]:= AdjacencyMatrix[%]//MatrixForm

Out[2]//MatrixForm=
(⁠|   |   |   |   |
| - | - | - | - |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |⁠)
```

---

The adjacency matrix of a directed graph can be unsymmetric:

```wl
In[1]:= Graph[{1\[DirectedEdge]2, 2\[DirectedEdge]1, 3\[DirectedEdge]1, 3\[DirectedEdge]2, 4\[DirectedEdge]1, 4\[DirectedEdge]2}]

Out[1]= [image]

In[2]:= AdjacencyMatrix[%]//MatrixForm

Out[2]//MatrixForm=
(⁠|   |   |   |   |
| - | - | - | - |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 |⁠)
```

---

Use rules to specify the graph:

```wl
In[1]:= AdjacencyMatrix[{1 -> 2, 2 -> 1, 3 -> 1, 3 -> 2, 4 -> 1, 4 -> 2}]//MatrixForm

Out[1]//MatrixForm=
(⁠|   |   |   |   |
| - | - | - | - |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 |⁠)
```

---

The adjacency matrix of the graph with self-loops has diagonal entries:

```wl
In[1]:= {Graph[{1\[UndirectedEdge]2, 2\[UndirectedEdge]3, 3\[UndirectedEdge]1, 2\[UndirectedEdge]2}], Graph[{1\[DirectedEdge]1, 1\[DirectedEdge]2, 2\[DirectedEdge]3, 3\[DirectedEdge]1}]}

Out[1]= {[image], [image]}

In[2]:= MatrixForm /@ AdjacencyMatrix /@ %

Out[2]=
{(⁠|   |   |   |
| - | - | - |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
| 1 | 1 | 0 |⁠), (⁠|   |   |   |
| - | - | - |
| 1 | 1 | 0 |
| 0 | 0 | 1 |
| 1 | 0 | 0 |⁠)}
```

---

``AdjacencyMatrix`` works with large graphs:

```wl
In[1]:= Graph[Table[i\[DirectedEdge]Mod[i ^ 2, 10 ^ 3], {i, 0, 10 ^ 3 - 1}]];

In[2]:= Timing[m = AdjacencyMatrix[%]]

Out[2]=
{0.000082, SparseArray[Automatic, {1000, 1000}, 0, 
 {1, {CompressedData["«2041»"], CompressedData["«1905»"]}, 
  CompressedData["«52»"]}]}
```

Use ``MatrixPlot`` to visualize the matrix:

```wl
In[3]:= MatrixPlot[m]

Out[3]= [image]
```

### Applications (7)

Compute the degree for an undirected graph from its adjacency matrix:

```wl
In[1]:= adjacencyDegree[g_ ? UndirectedGraphQ] := With[{a = AdjacencyMatrix[g]}, Total[a] + Diagonal[a]]

In[2]:= adjacencyDegree[[image]]

Out[2]= {4, 2, 3, 1}

In[3]:= VertexDegree[[image]]

Out[3]= {4, 2, 3, 1}
```

---

Compute the in-degree for a directed graph from its adjacency matrix:

```wl
In[1]:= adjacencyInDegree[g_ ? DirectedGraphQ] := Total[AdjacencyMatrix[g]]

In[2]:= adjacencyInDegree[[image]]

Out[2]= {2, 1, 1, 1}

In[3]:= VertexInDegree[[image]]

Out[3]= {2, 1, 1, 1}
```

---

Compute the out-degree for a directed graph from its adjacency matrix:

```wl
In[1]:= adjacencyOutDegree[g_ ? DirectedGraphQ] := Total[AdjacencyMatrix[g]\[Transpose]]

In[2]:= adjacencyOutDegree[[image]]

Out[2]= {2, 1, 2, 0}

In[3]:= VertexOutDegree[[image]]

Out[3]= {2, 1, 2, 0}
```

---

Count the number of paths between all vertices in exactly $k$ steps for a directed graph:

```wl
In[1]:=
graphPathCountMatrix[g_ ? DirectedGraphQ, k_Integer ? Positive] := 
	MatrixPower[AdjacencyMatrix[g], k]
```

There are two paths from 1 to 5 in two steps:

```wl
In[2]:= graphPathCountMatrix[[image], 2]//MatrixForm

Out[2]//MatrixForm=
(⁠|   |   |   |   |   |   |   |   |   |
| - | - | - | - | - | - | - | - | - |
| 0 | 0 | 1 | 0 | 2 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 2 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 2 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |⁠)
```

---

Count the number of paths from $s$ to $t$ in exactly $k$ steps for a directed graph:

```wl
In[1]:=
graphPathCount[g_ ? DirectedGraphQ, s_, t_, k_Integer ? Positive] := 
	MatrixPower[AdjacencyMatrix[g], k][[VertexIndex[g, s], VertexIndex[g, t]]]

In[2]:= graphPathCount[[image], 1, 5, 2]

Out[2]= 2
```

---

Compute the co-citation matrix, where the co-citation for two vertices is the number of common ancestors:

```wl
In[1]:= cocitationMatrix[g_ ? DirectedGraphQ] := With[{a = AdjacencyMatrix[g]}, a\[Transpose].a - DiagonalMatrix[Diagonal[a\[Transpose].a]]]

In[2]:= g = [image];

In[3]:= cocitationMatrix[g]//MatrixForm

Out[3]//MatrixForm=
(⁠|   |   |   |   |   |   |   |
| - | - | - | - | - | - | - |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 2 | 0 | 0 | 0 | 1 |
| 0 | 2 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 |⁠)
```

The co-citation between $J_2$ and $J_3$ :

```wl
In[4]:= %[[VertexIndex[g, Subscript[J, 2]], VertexIndex[g, Subscript[J, 3]]]]

Out[4]= 2
```

---

Compute the coupling matrix, where the coupling between two vertices is the number of common descendants:

```wl
In[1]:= couplingMatrix[g_ ? DirectedGraphQ] := With[{a = AdjacencyMatrix[g]}, a.a\[Transpose] - DiagonalMatrix[Diagonal[a.a\[Transpose]]]]

In[2]:= g = [image];

In[3]:= couplingMatrix[g]//MatrixForm

Out[3]//MatrixForm=
(⁠|   |   |   |   |   |   |   |
| - | - | - | - | - | - | - |
| 0 | 0 | 0 | 1 | 1 | 2 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 2 | 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |⁠)
```

The coupling between $P_1$ and $P_4$ :

```wl
In[4]:= %[[VertexIndex[g, Subscript[P, 1]], VertexIndex[g, Subscript[P, 4]]]]

Out[4]= 2
```

### Properties & Relations (14)

Rows and columns of the adjacency matrix follow the order given by ``VertexList`` :

```wl
In[1]:= g = Graph[{2\[UndirectedEdge]3, 3\[UndirectedEdge]1, 1\[UndirectedEdge]2, 1\[UndirectedEdge]4}, VertexShapeFunction -> "Name", VertexStyle -> Blue]

Out[1]= [image]

In[2]:= VertexList[g]

Out[2]= {2, 3, 1, 4}

In[3]:= TableForm[Normal@AdjacencyMatrix[g], TableHeadings -> {c = Style[#, Blue]& /@ %, c}]

Out[3]//TableForm=
|   | 2 | 3 | 1 | 4 |
| :- | :- | :- | :- | :- |
| 2 | 0 | 1 | 1 | 0 |
| 3 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
```

---

Use ``VertexIndex`` to find the matrix row and column corresponding to a pair of vertices:

```wl
In[1]:= g = Graph[{2\[UndirectedEdge]3, 3\[UndirectedEdge]1, 1\[UndirectedEdge]2, 1\[UndirectedEdge]4}, VertexShapeFunction -> "Name"]

Out[1]= [image]

In[2]:= (a = AdjacencyMatrix[g])//MatrixForm

Out[2]//MatrixForm=
(⁠|   |   |   |   |
| - | - | - | - |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 |⁠)
```

Check whether ``1`` and ``4`` are adjacent vertices:

```wl
In[3]:= a[[VertexIndex[g, 1], VertexIndex[g, 4]]] == 1

Out[3]= True
```

Compare with ``EdgeQ`` :

```wl
In[4]:= % == EdgeQ[g, 1\[UndirectedEdge]4]

Out[4]= True
```

---

An undirected graph has a symmetric adjacency matrix:

```wl
In[1]:= g = CompleteGraph[4]

Out[1]= [image]

In[2]:= AdjacencyMatrix[g]//MatrixForm

Out[2]//MatrixForm=
(⁠|   |   |   |   |
| - | - | - | - |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |⁠)

In[3]:= SymmetricMatrixQ[%]

Out[3]= True
```

---

Use ``AdjacencyGraph`` to construct a graph from an adjacency matrix:

```wl
In[1]:= AdjacencyGraph[{{0, 1, 0}, {0, 0, 1}, {1, 1, 0}}]

Out[1]= [image]

In[2]:= AdjacencyMatrix[%]//Normal

Out[2]= {{0, 1, 0}, {0, 0, 1}, {1, 1, 0}}
```

---

The main diagonal of the adjacency matrix for any graph without loops has all zero entries:

```wl
In[1]:= GridGraph[{2, 3}]

Out[1]= [image]

In[2]:= Diagonal[AdjacencyMatrix[%]]//Normal

Out[2]= {0, 0, 0, 0, 0, 0}
```

---

The number of rows or columns of the adjacency matrix is equal to the number of vertices:

```wl
In[1]:= g = CompleteGraph[5]

Out[1]= [image]

In[2]:= Dimensions[AdjacencyMatrix[g]]

Out[2]= {5, 5}

In[3]:= VertexCount[g]

Out[3]= 5
```

---

Isomorphic graphs can have different adjacency matrices:

```wl
In[1]:= {g, h} = {PetersenGraph[4, 1], HypercubeGraph[3]}

Out[1]= {[image], [image]}

In[2]:= IsomorphicGraphQ[g, h]

Out[2]= True

In[3]:= AdjacencyMatrix[g] == AdjacencyMatrix[h]

Out[3]= False
```

Permute the adjacency matrix of ``g`` according to the mapping that gets an equal matrix of ``h`` :

```wl
In[4]:= perm = Values[First[FindGraphIsomorphism[g, h]]]

Out[4]= {1, 2, 4, 3, 5, 6, 8, 7}

In[5]:= AdjacencyMatrix[g][[perm, perm]] == AdjacencyMatrix[h]

Out[5]= True
```

---

A ``d``-regular graph ``g`` is connected if the multiplicity of its ``d`` eigenvalue is 1:

```wl
In[1]:= g = HypercubeGraph[3]

Out[1]= [image]
```

The graph is 3-regular:

```wl
In[2]:= VertexDegree[g]

Out[2]= {3, 3, 3, 3, 3, 3, 3, 3}
```

The multiplicity ``3`` is 1, so it is connected:

```wl
In[3]:= Count[Eigenvalues[AdjacencyMatrix[g]], 3]

Out[3]= 1

In[4]:= ConnectedGraphQ[g]

Out[4]= True
```

---

For a complete graph, all entries outside the diagonal are 1s in the adjacency matrix:

```wl
In[1]:= AdjacencyMatrix[CompleteGraph[10]]//MatrixPlot

Out[1]= [image]
```

---

A complete $k$-partite graph has zero diagonal block entries:

```wl
In[1]:= AdjacencyMatrix[CompleteGraph[{2, 3, 4}]]//MatrixPlot

Out[1]= [image]
```

---

A ``TuranGraph`` is bipartite:

```wl
In[1]:= BipartiteGraphQ[g = TuranGraph[5, 2]]

Out[1]= True

In[2]:= MatrixPlot[AdjacencyMatrix[g]]

Out[2]= [image]
```

---

A ``StarGraph`` has 1s in the first column and first row only:

```wl
In[1]:= AdjacencyMatrix@StarGraph[10]//MatrixPlot

Out[1]= [image]
```

---

For a path, rows of an adjacency matrix will contain one or two elements:

```wl
In[1]:= PathGraph[Range[20]]

Out[1]= [image]

In[2]:= MatrixPlot[AdjacencyMatrix[%]]

Out[2]= [image]
```

---

The adjacency matrix of a line graph can be computed by its ``IncidenceMatrix`` :

```wl
In[1]:= g = GridGraph[{2, 3}]

Out[1]= [image]

In[2]:= m = IncidenceMatrix[g];

In[3]:= MatrixPlot /@ {Transpose[m].m - 2IdentityMatrix[EdgeCount[g]], AdjacencyMatrix[LineGraph[g]]}

Out[3]= {[image], [image]}
```

### Possible Issues (1)

An empty graph has no adjacency matrix:

```wl
In[1]:= AdjacencyMatrix[Graph[{}, {}]]
```

AdjacencyMatrix::nadj: The null graph does not have an adjacency matrix.

```wl
Out[1]= AdjacencyMatrix[[image]]
```

## See Also

* [`AdjacencyGraph`](https://reference.wolfram.com/language/ref/AdjacencyGraph.en.md)
* [`WeightedAdjacencyMatrix`](https://reference.wolfram.com/language/ref/WeightedAdjacencyMatrix.en.md)
* [`IncidenceMatrix`](https://reference.wolfram.com/language/ref/IncidenceMatrix.en.md)
* [`KirchhoffMatrix`](https://reference.wolfram.com/language/ref/KirchhoffMatrix.en.md)
* [`VertexIndex`](https://reference.wolfram.com/language/ref/VertexIndex.en.md)
* [`DistanceMatrix`](https://reference.wolfram.com/language/ref/DistanceMatrix.en.md)

## Related Guides

* [Graphs and Matrices](https://reference.wolfram.com/language/guide/GraphsAndMatrices.en.md)
* [Graph Construction & Representation](https://reference.wolfram.com/language/guide/GraphConstructionAndRepresentation.en.md)
* [Graph Programming](https://reference.wolfram.com/language/guide/GraphProgramming.en.md)
* [Computation on Graphs](https://reference.wolfram.com/language/guide/ComputationOnGraphs.en.md)

## Related Links

* [An Elementary Introduction to the Wolfram Language: Graphs and Networks](https://www.wolfram.com/language/elementary-introduction/21-graphs-and-networks.html)

## History

* [Introduced in 2010 (8.0)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn80.en.md) \| [Updated in 2015 (10.3)](https://reference.wolfram.com/language/guide/SummaryOfNewFeaturesIn103.en.md)