The adjacency matrix, also called as the connection matrix, is a matrix containing rows and columns which is used to represent a simple labelled graph, with 0 or 1 in the position of (Vi , Vj) according to the condition whether Vi and Vj are adjacent or not. It is a compact way to represent the finite graph containing n vertices of a m x m matrix M. Sometimes adjacency matrix is also called as vertex matrix and it is defined in the general form as

$\left\{\begin{matrix} 1 & if \;P_{i}\rightarrow P_{j}\\ 0& otherwise \end{matrix}\right \}$

If the simple graph has no self-loops, Then the adjacency matrix should have 0s in the diagonal. The adjacency matrix is symmetric for the undirected graph. The adjacency matrix is considered as a square array where each row represents the out-nodes of a graph and each column represents the in-nodes of a graph. Entry 1 represents that there is an edge between two nodes.

## How to create an Adjacency Matrix?

If a graph G with n vertices, then the adjacency matrix n x n is given by

$A=\begin{bmatrix} a_{11} &a_{12} & \cdots &a_{1n} \\ a_{21} &a_{22} &\cdots &a_{2n} \\ \vdots & \vdots &\ddots & \vdots \\ a_{n1}& a_{n2} & \cdots & a_{nn} \end{bmatrix}$

Where, the value aij equals the number of edges from the vertex i to j. For an undirected graph, the value aij = aji for all i, j , so that the adjacency matrix becomes symmetric matrix.

From the given directed graph, the adjacency matrix is written as

The adjacency matrix = $\begin{bmatrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0\\ 0 & 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}$

## Matrix Properties

The adjacency matrix is an array of numbers which is used to represent the information about the graph. Some of the properties of the graph correspond to the properties of the adjacency matrix, and vice versa. The properties are given as follows:

### Powers

The most well-known approach to get information about the given graph from operations on the adjacency matrix is through its powers. The entries of the powers of the adjacency matrix give information about paths in the given graph. The theorem is given below to represent the powers of the adjacency matrix.

Theorem: Let us take, A be the adjacency matrix of a given graph. Then the entries i, j of An counts n-steps walks from vertex i to j.

### Spectrum

The study of the eigenvalues of the adjacency matrix of a graph is clearly defined in spectral graph theory. Assume that, A be the adjacency matrix of a k-regular graph and v be the all-ones column vector in Rn. Then the i-th entry of Av is equal to the sum of the entries in the ith row of A. This represents the number of edges proceeds from vertex i, which is exactly k. So

$A\begin{bmatrix} 1\\ 1\\ \vdots \\ 1\end{bmatrix}=\begin{bmatrix} k\\ k\\ \vdots \\ k\end{bmatrix}=k\begin{bmatrix} 1\\ 1\\ \vdots \\ 1\end{bmatrix}$

Where V is an eigenvector of the matrix A containing the eigenvalue k

### Isomorphisms

The given two graphs are said to be isomorphic if one graph can be obtained from the other by relabeling vertices of another graph. It is noted that the isomorphic graphs need not have the same adjacency matrix. Because the adjacency matrix depends on the labelling of the vertices. But the adjacency matrices of the given isomorphic graphs are closely related.

Theorem: Assume that, G and H be the graphs having n vertices with the adjacency matrices A and B. Then G and H are said to be isomorphic if and only if there is an occurrence of permutation matrix P such that B=PAP-1.

### Question:

Write down the adjacency matrix for the given undirected weighted graph

### Solution:

The weights on the edges of the graph are represented in the entries of the adjacency matrix as follows:

A = $\begin{bmatrix} 0 & 3 & 0 & 0 & 0 & 12 & 0\\ 3 & 0 & 5 & 0 & 0 & 0 & 4\\ 0 & 5 & 0 & 6 & 0 & 0 & 3\\ 0 & 0 & 6 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 10 & 7\\ 12 &0 & 0 & 0 & 10 & 0 & 2\\ 0 & 4 & 3 & 0 & 7 & 2 & 0 \end{bmatrix}$

For more such interesting information on adjacency matrix and other matrix related topics, register with BYJU’S -The Learning App and also watch interactive videos to clarify the doubts.

 Related Links Orthogonal Matrix Matrices Exponents And Powers Elementary Transformation Of Matrices

#### Practise This Question

The value of y′′(1) if x32x2y2+5x+y5=0 when y(1)=1, is equal to