Graphs interpreted as adjacency matrices

Question

Consider a real symmetric matrix. Such a matrix can be considered as an adjacency matrix of a graph, and in fact may be identified with the graph itself.

Now consider the equivalence class of the relation of isomorphism between graphs. All the graph invariants are same for all the graphs in the same equivalence class. Similarly all the algebraic properties for the adjacency matrices are same, i.e. rank, determinant, spectrum etc. This is just because any two graphs are isomorphic translates to saying that the adjacency matrices are similar(Or even more strongly it translates to that they are permutation equivalent matrices. Or is there some even more stronger term, because they are related as $B=PAP^T$ and not simply as $B=PAQ$ for permutation matrices $P,Q$?)

However I feel, that there is some more deeper interpretation here in the connection between adjacency matrices and the associated graph. All isomorphic graphs correspond to the same operator and can a deeper interpretation be derived from that? Specifically why do the graph theoretic properties translate to algebraic properties?

Answer 1

In two isomorphic graphs only labelling of vertices is different. So if we go for their adjacency matrices we need to permute same row and same column simaltaneously(just to preserve adjacency) that's why different P and Q will not work.

Answer 2

This is not a direct answer to your question (so do not shoot me down, please) but an observation to your tagging "spectral-graph-theory": The graphs in the picture are cospectral (I mean $K_{1,4}$ with $C^4 \sqcup K^1$, $G_1$ with $G_2$, $H_1$ with $H_2$) that is, they are non-isomorphic but have the same characteristic polynomial and so the same eigenvalues. If you consider the first pair, $K_{1,4}$ and $C^4 \sqcup K^1$, then you see that they are not even both connected. So, in the end, graphs and adjacency matrices (and their derived associated structures/quantities like polynomials and eigenvalues et cetera) are perhaps far less the "same" than we like to think.

Answer 3

There are a lot of graph theoretical properties of a graph that can be derived from algebraic properties of the adjacency matrix.

As an example, let $A=(a_{i,j})$ be the adjacency matrix of a bipartite graph $G=(X\cup Y, E)$ with $|X|=n$ rows and $|Y|=n$ columns, then $G$ has a perfect matching if, and only if every submatrix of $A$ of size $p\times q$ with $p+q>n$ has a nonzero entry.

Answer 4

For simultaneously diagonalizable matrices $A$ and $B$, it is easy to find a unitary $P$ such that $A=P^TBP$. E.g. WLOG diagonalize on some order the eigenvalues such that $A = V^TDV$ and $B=W^TDW$ for unitary $V, W$ and common diagonal matrix $D$; then we have a solution $P=V^TW$.

However, $P$ is not unique. In fact, the set of solutions for $P$ is a set $R$. To check isomorphism, you need to know is whether $R$ contains a permutation matrix. Given $A, B$, one can heuristically search for a $P$ that happens to be a permutation matrix by minimizingthe constrained convex relaxation $\|PA-BP\|_2^2$ over L-1 regularized bistochastic $P$.

A technically challenging but more fruitful approach involves reaching into group theory and modeling the automorphisms directly. Recently Bibai announced pseudo-polynomial time breakthrough on this front.