"Nice" eigenvectors for (square of) adjacency matrix of a bipartite graph?

Question

Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix.

I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be especially interested if one could read off information about graph theoretic matchings (such as how large a matching is possible) from information about the eigenvectors and eigenvalues of $A^2$ (or of $A$ itself). One thing that made me start wondering about this was to notice that in the very, very special case of a graph that is a single even cycle, one can get an eigenvector for $A^2$ by putting 1's in the entries indexed by the vertices of a single color in a 2-coloring of this cycle and 0's for the other entries. It seems like this eigenvector reflects the fact that the cycle can be decomposed into a pair of matchings. I wondered if there is still any related nice structure that persists even after one has many interacting cycles in a bipartite graph.

Perhaps this is too much to ask in the generality of bipartite graphs, in which case I'd also be interested in conditions under which there are eigenvectors encoding information about matchings.

Thanks!

Answer 1

Write the vectors indexed by $V(G)$ in the form $(x,y)$, where $x$ is indexed by the vertices in one colour class and $y$ by the vertices in the other. (And I am being sloppy regarding transposes.) Then $(x,y)$ is an eigenvector for $A$ with eigenvalue $\theta$ if and only if $(x,-y)$ is an eigenvector for $A$ with eigenvalue $-\theta$. Hence $(x,y)$ and $(x,-y)$ are eigenvectors for $A^2$ (with eigenvalue $\theta^2$), and therefore their sum and difference, $(2x,0)$ and $(0,2y)$ are eigenvectors for $A^2$.

What you are seeing in your $C_4$ example is the above applied to the vector where all entries of $x$ and $y$ are equal to 1. The same thing will hold for any regular bipartite graph. But it will also hold for graphs such as $K_{2,3}$, where the vectors $(\textbf{1},0)$ and $(0,\textbf{1})$ will be eigenvectors for $A^2$. Despite the lack of perfect matchings.

So as far as I can see you have not identified any relation between perfect matchings and eigenvectors.