# Vanishing of principal minors implies upper triangular up to permutation

Let $$A$$ be a square matrix. If $$A$$ satisfies the following two conditions

(1) $$A$$ is upper triangular

(2) all diagonal entries of $$A$$ are zero

then it is easy to see that all principal minors of $$A$$ vanish.

Now the problem I can not solve is

If all principal minors of a square matrix (not necessarily symmetric) vanish, show that it is permutation-similar to a matrix $$A$$ satisfying above two conditions.

Let $$A=(a_{i,j})$$. The $$1\times 1$$ minors show that the diagonal entries $$a_{i,i}$$ have to be zero. The $$2\times 2$$ minors then show that for $$i\ne j$$, either $$a_{i,j}=0$$ or $$a_{j,i}=0$$. So we can form a directed graph on the vertices $$1,\dots,n$$ whose edges $$i\to j$$ correspond to the non-zero $$a_{i,j}$$. If there's a directed triangle $$i\to j\to k\to i$$ then the corresponding $$3\times 3$$ minor is non-zero, so there are no directed triangles. Continue this way by induction to show that there are no directed cycles of any length. Now we can choose a total order $$\prec$$ on the vertices so that if there is an arrow $$i\to j$$ then $$i\prec j$$. This gives a conjugating permutation matrix, reordering $$1,\dots,n$$ with respect to $$\prec$$.