The rank of the adjacency matrix $A$ of a bipartite graph is not directly linked to the size of the maximum matching, as shown in the following graphs; $$ \begin{pmatrix} 0 & 0 & 1 & 1\\ 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0\\ \end{pmatrix} \text{ and } \begin{pmatrix} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ \end{pmatrix} $$ both have a perfect matching, but the rank of the first adjacency matrix is 2 while the second has a rank of 4.

Rank $2n$ $\rightarrow$ matching of $n$

If the adjacency matrix has a rank of $2n$, we can show that a matching of size $n$ must exists as the maximum rank of the Edmonds matrix is at least $n$, and the maximum rank of the Edmonds matrix is equal to the size of the maximum matching. However, the converse does not hold, as shown in the first example.

Matching of $n$ $\rightarrow$ Rank of $2n$ for twin-free graphs

I wonder if the converse holds for bipartite graphs that are twin-free, meaning that no two nodes in the same part of the graph are connected to the sames nodes in the other parts.

In terms of the adjacency matrix, this implies that there are no duplicate lines or columns.

We can also assume that there is no node that is not connected (no all 0 line or column), and that there is no node that is connected to every node in the other part (no all 1 line or column in the upper right or lower left blocks).


I have not been able to find a way to approach the problem, and have not found reference to this problem in the litterature. Any hint on how to try to prove that it holds or keyword recommendation (I might not know the correct vocabulary to search for this) would be appreciated.

And obviously any counterexample is welcome.


Cycles of length $4n$ with $n\ge2$ have perfect matching, no twins, but have rank $4n-2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.