PlanetMath: adjacency matrix

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (194)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

adjacency matrix

(Definition)

Definition

Let be a graph with vertex set $V=\lbrace v_1,\ldots, v_n \rbrace$ and edge set . The adjacency matrix $M_G=(m_{ij})$ of is defined as follows: is an $n\times n$ matrix such that

$\begin{displaymath} % latex2html id marker 425m_{ij} = \left \lbrace \begin{ar... ...j\rbrace \in E$}\ 0 & \textrm{otherwise.} \end{array}\right. \end{displaymath}$

In other words, start with the $n\times n$ zero matrix, put a

in cell

if there is an edge whose endpoints are

and

Remarks. Let be a graph and be its adjacency matrix.

is symmetric with 0's in its main diagonal.
The sum of the cells in any given column (or row) is the degree of the corresponding vertex. Therefore, the sum of all the cells in is twice the number of edges in .
$M_G=\mathbf{1}-I$ iff is a complete graph. Here, $\mathbf{1}$ is the matrix whose entries are all and is the identity matrix.
If we are given a symmetric matrix of order whose entries are either or 0 and whose entries in the main diagonal are all 0, then we can construct a graph such that .

The above definition of an adjacency matrix can be extended to multigraphs (multiple edges between pairs of vertices allowed), pseudographs (loops allowed), and even directed pseudographs (edges are directional). There are two cases in which we can generalize the definition, depending on whether edges are directional.

(Edges are not directional).
Since a multigraph is just a special case of a pseudograph, we will define for a pseudograph . Let be a pseudograph with $V=\lbrace v_1,\ldots,v_n\rbrace$ The adjacency matrix $M_G=(m_{ij})$ of is an $n\times n$ matrix such that $m_{ij}$ is the number of edges whose endpoints are and . Again, is symmetric, but the main diagonal may contain non-zero entries, in case there are loops.
(Edges are directional).
Since a digraph is a special case of a directed pseudograph, we again define in the most general setting. Let be a directed pseudograph with $V=\lbrace v_1,\ldots,v_n\rbrace$ and $E\subseteq V\times V\times (\mathbb{N}\cup \lbrace 0\rbrace)$ . The adjacency matrix of is an $n\times n$ matrix such that

$\displaystyle m_{ij}=\vert\lbrace k\mid (v_i,v_j,k)\in E\rbrace\vert.$
In other words, $m_{ij}$ is the number of directed edges from to .

Remarks

If is a multigraph, then the entries in the main diagonal of must be all 0.
If is a graph, then corresponds to the original definition given in the previous section.
If is a digraph, then entries consists of 0's and 's and its main diagonal consists of all 0's.
Given any square matrix , there is a directed pseudograph with . In addition, corresponds to adjacency matrix of various types of graphs if appropriate conditions are imposed on
Generally, one can derive a pseudograph from a directed pseudograph by “forgetting” the order in the ordered pairs of vertices. If is a directed pseudograph and is the corresponding derived pseudograph. Let $M_G=(m_{ij})$ and $M_{G'}=(n_{ij})$ , then $n_{ij}=m_{ij}+m_{ji}$ .
In the language of category theory, the above operation is done via a forgetful functor (from the category of directed pseudographs to the category of pseudographs). Other forgetful functors between categories of various types of graphs are possible. In each case, the forgetful functor has an associated operation on the adjacency matrices of the graphs involved.