I came across this problem which boiled down to finding the maximum number of pairs of disjoint edges given a simple undirected graph. After doing some research I came across Edmond's Blossom algorithm for general graphs. But it seems unnecessary because I don't need to find what those edges should be, I only need how many edges will be there in the maximum matching. So can rank of the adjacency Matrix or something other property be used?
I naturally tried using the rank of the Matrix to check if it worked and gave the same result as the Blossom algorithm, it didn't. I did some more research and came across a theorem in some paper that said the number of maximum matching pairs is twice the rank of the skew symmetric adjacency matrix, it didn't work either. I'm hoping for any other ideas.
The blossom algorithm is the most computationally efficient option, but it is difficult to implement yourself.
An alternative, more algebraic method is to use the Tutte matrix. For a graph $G$ with vertices $v_1, v_2, \dots, v_n$, this is a $n \times n$ matrix $T$ in terms of $|E(G)|$ variables; it is given by $$T_{ij} = \begin{cases}x_{ij} & i<j \text{ and } v_i v_j \in E(G) \\ -x_{ji} & i >j \text{ and }v_iv_j \in E(G) \\ 0 & i=j\end{cases}$$ Lovász proved that the rank of $T$ is equal to the number of vertices covered by a maximum matching in $G$.
Computing the rank of $T$ is actually harder than it sounds; for a symbolic matrix, many of the computations we'd normally do start to take exponentially long, because as we manipulate the matrix, its entries grow into polynomials in $|E(G)|$ variables. There is a shortcut, but it turns the whole process into a randomized algorithm.
Choose a prime $p$ larger than $n$, and assign randomly chosen values mod $p$ to each variable. We can compute the rank of this numerical matrix by row-reducing it over $\mathbb F_p$. Unfortunately, this rank might end up being smaller than the rank of the symbolic matrix $T$, because our random substitution might create new linear dependencies. However, if $p$ is significantly larger than $n$, we're still in pretty good shape: by the Schwartz-Zippel lemma, we'll get the correct rank with probability at least $1 - \frac np$, which we can make close to $1$ by choosing a large value of $p$. (We can also perform multiple tests to further reduce the probability of error.)