1
$\begingroup$

This question originates from my “revelation” that the identity matrix generates the world's most boring graph: all the nodes are just connected to themselves and none of them are connected to each other.

Given an adjacency matrix $A$ for a graph $G$, what do things like the determinant and eigenvalues / eigenvectors of $A$ really tell us about $G$?

If $A$ forms an orthogonal basis, then $G$ is quite “boring”, as I said. So, clearly, for “interesting” graphs, no inner product will form in the vector space defined by $A$. But $A$ still has a unique determinant, eigenvalues and eigenvectors, a inverse, a minimal polynomial and characteristic polynomial, and a Jordan normal form. What do the characteristics of these properties of $A$ mean for $G$, or even $G^n$?

I understand these are likely loaded questions, but I want to find a clearer link from Graph Theory to Linear Algebra.

$\endgroup$
2
  • $\begingroup$ This is a rather broad question. You might want to narrow it down a bit. $\endgroup$
    – Math1000
    Jan 25, 2020 at 0:51
  • $\begingroup$ @Math1000 I know you’re right, I just don’t have enough esoteric knowledge about both to studies to narrow it down. Any recommendations to help narrow this down? $\endgroup$
    – Ty Jensen
    Jan 25, 2020 at 0:52

1 Answer 1

1
$\begingroup$

There are quite a few correspondences between Graph Theory and Linear Algebra.

The most prominent would probably be the linking of graphs to their adjacency matrices, together with a slightly different definition for "the length of a path":

Let $G=(V,E,\phi)$ be a graph, and $a_1\to a_2,...,a_{n-1}\to a_n\in E$ be a path. Then we define the length of the path $a_1\to a_2\to ...\to a_{n-1}\to a_n$ as $$ \prod_{i=1}^{n-1} \phi(a_i\to a_{i+1})$$.

Now, let $A$ be the adjancency matrix of the graph, and let $\begin{cases}A_{i,j}=1,\quad i\to j \in E\\ A_{i,j}=0,\quad i\to j\not\in E\end{cases}$ . Then the cell $(A^n)_{i,j}$ counts the number of ways to go from node $i$ to node $j$ using precisely $n$ edges.

You can then look at a normal form of $A$, e.g. diagonalization for undirected graphs, to argue that if we have an eigenvalue $\neq 0$, then we're bound to have a cycle in our graph.

A generalization of that to eigenvectors would be this question.

Not directly an application of the determinant of the matrix, but Kirchhoff's theorem uses the determinants of the Laplacian matrix of the graph to calculate the number of spanning trees the graph admits.

Building on Kirchoff's Theorem, there is also the BEST theorem, which let's one calculate the number of eulerian circuits in a directed graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.