Matrix triangularisation through basis swaps exclusively

Question

Assume $A$ is a $n \times n$ Matrix with real valued elements. I would like to bring A into a (lower) triangular form. However, to do so I am only allowed to swap bases. Hence, I can only swap rows and columns together.

Q: Under which condition is this possible, and does somebody know of any algorithm to do so?

To give a picture, this is a valid operation: $$\left( \begin{array}{ccc} a & 0 & 0 \\ 0 & b & x \\ 0 & 0 & c \end{array} \right) \rightarrow \left( \begin{array}{ccc} a & 0 & 0 \\ 0 & c & 0 \\ 0 & x & b \end{array} \right) $$

However a matrix of the following form can not be brought to a triangular form under this conditions:

$$\left( \begin{array}{ccc} a & 0 & 0 \\ 0 & b & x_{2} \\ 0 & x_{1} & c \end{array} \right) \text{ or } \left( \begin{array}{ccc} a & 0 & 0 \\ x_{1} & c & x_{2} \\ x_{3} & x_{4} & b \end{array} \right) $$

Answer 1

Consider a directed graph with the nodes labeled $1$ through $n$ and an edge from node $i$ to $j$ iff $i\ne j$ and $A_{ij}\ne 0$.

Your operation is possible if and only if this graph is acyclic. If the graph is acyclic, you get a triangular matrix by arranging the basis vectors in an order corresponding to a topological sorting of the graph.

There are well-known algorithms to determine efficiently whether a graph is acyclic, e.g. Tarjan's -- or simply try to construct a topological sorting greedily (that is, repeatedly take a node whose predecessors have all been taken already) and see if you get stuck before you get to all nodes.