There are several ways to associate a matrix with a graph. The properties of these matrices, especially spectral properties (eigenvalues and eigenvectors) tell us things about the structure of the corresponding graph. This post is a brief reference for keeping these various matrices straight.

The most basic matrix associated with a graph is its **adjacency matrix**, denoted *A*. For a graph with *n* nodes, create an *n*×*n* matrix filled with zeros, then fill in a 1 in the *i*th row and *j*th column if there is an edge between the *i*th and *j*th node.

Next let *D* be the diagonal matrix whose *i*th element is the degree of the *i*th node, i.e. the number of edges attached to the *i*th node. The **Laplacian matrix** of the graph is

*L* = *A *– *D*.

The Laplacian matrix of a graph is analogous to the Laplacian operator in partial differential equations. It is sometimes called the Kirchhoff matrix or the admittance matrix.

The **signless Lapacian matrix** is

*Q* = *A *+ *D*.

There are connections between the signless Laplacian and bipartite components. For example, the multiplicity of 0 as an eigenvalue of *Q* equals the number of bipartite components in the graph.

There are other variations of the Laplacian matrix. The **normalized Laplacian matrix** has 1’s down the diagonal. If there is an edge between the *i*th and *j*th nodes, the *ij* entry is

-1/√*d*_{i}*d*_{j}

where *d*_{i} and *d*_{j} are the degrees of the *i*th and *j*th nodes. If there is no edge between the *i*th and *j*th nodes, the *ij* entry is 0.

The **distance matrix** of a graph is the matrix *D* whose *ij*th entry is the distance from the *i*th node to the *j*th node. (Sorry, this *D* is different than the one above. Books often write this as a script *D*, something I can’t do in plain HTML.) The **transmission** of a node *v*, *Tr*(*v*), is the sum of the distances from *v* to every element connected to *v*. The **distance Laplacian** of a graph is Diag(*Tr*) – *D* where Diag(Tr) is the diagonal matrix whose *i*th entry is the transmission of the *i*th node and *D* here is the distance matrix. The **signless distance Laplacian** of a graph is Diag(*Tr*) + *D.*

**Reference**: Inequalities for Graph Eigenvalues

**Related posts**:

The wonders of Unicode let you use both D and . I would hope it’s safe to assume adequate font coverage in this world of 2015.

Ha ha. I saw the math bold script D (U+1D4D3) in the comment entry box, but it’s gone now that the comment has been posted.

2015 indeed 🙁

Marius: Unfortunately Unicode support is indeed disappointing. I blogged a while back about which Unicode characters you can depend on and this list is pretty small, only a small portion of the Basic Multilingual Plane and nothing in the extended planes where things like U+1D4D3 live.

Nice entry!

By the way, it seems someone in the Baltimore Ravens has devised a fast way to compute the Fiedler vector (that’s the second smallest eigenvector of the Laplacian, I think) http://its-interesting.com/2015/03/19/baltimore-ravens-offensive-lineman-john-urschel-publishes-paper-in-math-journal/

“the multiplicity of 0 as an eigenvalue of Q equals the number of bipartite components in the graph”

Does this just mean the nullity of Q is equal to the number of bipartite components of the graph, or an I misreading this?

Using MathJax, you can use AMSTex fonts.

Yes and no. MathJax will automate creating an image file from LaTeX and inserting it into your HTML, but it looks like a foreign symbol pasted into the text. That’s OK, and maybe that would be better than what I did, but it’s not great. I like to use LaTeX for displayed equations if necessary, but not in the middle of a paragraph.

In most cases adjacency matrices are sparse and there are a lot of techniques to manipulate (multiply or store) sparse matrices.

There is a method to know whether a given graph is connected (i.e. any two vertexes can achievable).

Let A is adjacency matrix of the graph. if the matrix B = I+A+A^2+.. +A^n has zero entries the the graph is disconnected and vice versa

Great post!

Can you recommend sources or texts to learn more about these topics?

Rob: You could start by going to Fan Chung’s site.