# Bipartite maximum matching size from eigenvalues

Supposing we know the adjacency matrix $\mathcal{A}_{G}$ of a given regular (or irregular) bipartite graph $G$. Are there good lower and upper bounds to the size of maximum matching from the graph's adjacency matrix's or its Laplacian's eigenvalues (without using an algorithm to calculate explicitly a maximum matching)?

• maximal or maximum ? Nov 29 '11 at 16:44
• $K_{1,2n-1}$ and $K_{n,n}$ share the same spectrum, so I doubt that there's anything that you can conclude based just on the eigenvalues. Nov 29 '11 at 21:47
• @JohnMoeller: Maybe this should be an answer ? Nov 30 '11 at 3:27
• @JohnMoeller Do you mean spectrum of the adjacency matrix?
– v s
Nov 30 '11 at 18:26
• Spectrum of the adjacency matrix or its Laplacian. I'll write this up as an answer but I don't have time at the moment. Nov 30 '11 at 18:41

I'll just talk about maximum matchings, since that will demonstrate the point. Suppose that we consider both $K_{1,2n-1}$ and $K_{n,n}$. The first has a maximum matching of size 1, since it's a star graph, and the other has $n$ for obvious reasons.
It's easiest to reason about the normalized adjacency matrix $D^{-1}A$, but the same applies to the normalized Laplacian. Both of these graphs have an eigenvalue of 1, because every connected graph does. The corresponding eigenvector is the vector of all ones (this is easy enough to see because $A\mathbf{1} = D\mathbf{1}$). Since they're bipartite, they both also have eigenvalues of -1, with eigenvectors corresponding to being negative on one side and positive on the other: e.g. the column vector with parts $\mathbf{1}_L$ and $-\mathbf{1}_R)$.