Matrix triangularisation through basis swaps exclusively 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)
$$

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.
