The answer to Question I is **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*][1].  


The answer to Question I characterizes the bipartite graphs with exactly one perfect matching.  The graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $2^n$ candidates, a set that fails Hall's Condition can be found in polynomial time.  

One way to decide if a graph has exactly zero or one perfect matchings is to compute a maximum matching (this can be done in polynomial time).  If the maximum matching is not a perfect matching, then the graph has zero perfect matchings.  If the maximum matching is a perfect matching, then you can easily test if it is unique (in polynomial time) using Godsil's theorem above.  


  [1]: https://link.springer.com/article/10.1007/BF02579440