Adjacency matrix

Imagine dots joined by lines.

We can use a grid of numbers to show these dots. This grid is called an adjacency matrix. It uses ones and zeros to show connections. A one means two dots are joined. A zero means they are not.

In some grids, the lines only go one way. This makes the grid look different on each side. The grid can also show how far apart dots are. It is a smart way for computers to map things.

Imagine a group of dots joined by lines.

In math, we call these dots vertices. We can use a square grid of numbers to map them. This grid is an adjacency matrix. It tells us if dots are connected.

In a simple graph, we use ones and zeros. A one means a line joins two dots. A zero means there is no connection.

If the lines go both ways, the grid is symmetric. This means the top and bottom match. If lines only go one way, the grid is not symmetric.

Computers use these grids to store data. One way is to use an adjacency list. This is a different way to show connections. An adjacency matrix is great for checking if two dots connect. It can even help us count paths. We can find the shortest path between dots using these grids. This helps computers solve many puzzles.

Imagine a collection of dots connected by lines. In math, we call these dots vertices and the lines edges. An adjacency matrix is a special square grid used to map these connections. This grid acts like a map for the whole group. It tells us exactly which vertices are adjacent, or neighbors, to each other.

Scientists and computer experts use these matrices to study how things are linked. It turns a picture of connections into a clear set of numbers.

How does this grid actually work? For a simple graph, we use a (0,1)-matrix. This means the grid only contains zeros and ones. A one shows that an edge connects two specific vertices. A zero shows there is no connection between them.

In these simple graphs, the diagonal line of numbers from top-left to bottom-right is always zero. This is because a simple graph does not allow a loop from a dot back to itself. If the lines go both ways, the matrix is symmetric. This means the top half looks like a mirror image of the bottom half.

Mathematicians have found many different ways to use these grids. Sometimes, they use a distance matrix instead. This grid does not just show if dots connect. It shows the length of the shortest path between any two dots.

There is also a special version for bipartite graphs. These are graphs where vertices are split into two separate groups. In these cases, we can use a smaller grid called a biadjacency matrix. This smaller grid is much more efficient for representing the connections.

These matrices can also tell us about the structure of the graph through math. For example, we can use the matrix to count triangles. If we multiply the matrix by itself, the new numbers tell us about paths. The number of ways to walk from one dot to another in a certain number of steps is hidden in the math.

We can even use eigenvalues to study the spectrum of a graph. This helps us understand if the graph is connected or if it has special patterns.

Computers use adjacency matrices as a way to store data. They are very fast when we need to check if two specific dots are connected. However, they can take up a lot of space if there are very few connections. In those cases, a computer might use an adjacency list instead.

An adjacency list only stores the connections that actually exist. This saves memory when the graph is sparse. Choosing between a matrix and a list depends on the job the computer is doing.

An adjacency matrix is a square grid used to represent a finite graph. In graph theory, a graph consists of vertices, which are points, and edges, which are lines connecting them. The matrix serves as a mathematical map for these connections. Each element in the matrix indicates whether a specific pair of vertices is adjacent. This means the matrix turns a visual network into a structured set of numbers. This transformation allows mathematicians and computer scientists to use algebra to study complex networks.

To build an adjacency matrix, you create a grid with the same number of rows and columns as there are vertices. For a simple graph, the matrix is a (0,1)-matrix. This means every entry is either a 0 or a 1. A 1 represents an existing edge between two vertices. A 0 represents the absence of an edge. In a simple graph, loops are not allowed. A loop is an edge that connects a vertex to itself. Because of this, the diagonal elements from the top-left to the bottom-right are always 0.

Different types of graphs change how the matrix looks. If a graph is undirected, the edges are bidirectional. This means the connection works both ways. In these cases, the adjacency matrix is symmetric. A symmetric matrix looks like a mirror image across its main diagonal. If the graph is directed, edges have a specific direction. The matrix may be asymmetric in directed graphs. You can define these matrices in two ways. One way shows an edge from vertex $i$ to vertex $j$. The other way shows an edge from $j$ to $i$. Social network analysis often uses the first definition. Physics and network science often use the second.

There are several specialized versions of this matrix. A bipartite graph has vertices split into two distinct parts. For these, you can use a smaller biadjacency matrix. This smaller grid uniquely represents the connections between the two parts. Another version is the distance matrix. Instead of showing if vertices are connected, it shows the shortest path length. The distance is the number of edges in the shortest path between two points. There is also the Seidel adjacency matrix. This is a (-1,0,1)-matrix used to study strongly regular graphs.

Algebraic properties provide deep insights into a graph's structure. One major area of study is spectral graph theory. This field looks at the eigenvalues and eigenvectors of the adjacency matrix. The set of these eigenvalues is called the spectrum of the graph. For undirected simple graphs, the matrix is symmetric. This ensures it has a complete set of real eigenvalues. The largest eigenvalue is always less than or equal to the maximum degree of the vertices. In bipartite graphs, if a number is an eigenvalue, its opposite is also an eigenvalue.

Matrix math can also reveal physical patterns within the graph. If you multiply the adjacency matrix by itself, the resulting matrix tells you about walks. The element in the $i$-th row and $j$-th column shows how many walks of length $k$ exist between those vertices. This is very useful for counting triangles. In an undirected graph, you can find the number of triangles by taking the trace of the matrix cubed and dividing by 6. The trace is the sum of the diagonal elements. This method accounts for the fact that each triangle is counted multiple times.

In computer science, the adjacency matrix is a vital data structure. It is very efficient for testing if an edge exists between two specific vertices. This check happens almost instantly. However, matrices can be wasteful for sparse graphs. A sparse graph has many vertices but very few edges. In these cases, a large portion of the matrix is filled with zeros. To save space, programmers might use an adjacency list instead. An adjacency list only stores the connections that actually exist. This makes it much more memory-efficient for large, thin networks.