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.
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.