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$.
I hope this wasn't homework.
