Skip to main content
1 of 5
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, it is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris Godsil in Lemma 2.1 of the paper Inverses of trees.

The answer to your second question is no. For example, the biadjacency matrix of the complete bipartite graph $K_{n,n}$ obviously cannot be permuted to a lower triangular matrix, but this graph has many perfect matchings. A necessary and sufficient condition for the graph to have zero perfect matchings is to fail Hall's condition, which you can say in terms of the biadjacency matrix (if you like).

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187