IMC 2001, Day 2, Problem 4
Let be an complex matrix such that for each and the determinant of the matrix is zero. Prove that and that there exists a permutation such that the matrix
has all of its nonzero elements above the diagonal.
Original from the official PDF

This transcription was compared symbol by symbol with the original, but not yet by a person.
Work for at least 45 minutes before opening the solution.
Official solution
Solution. We will only prove (2), since it implies (1). Consider a directed graph with vertices and a directed edge from to when . We shall prove that it is acyclic.
Assume that there exists a cycle and take one of minimum length . Let be the vertices the cycle goes through and let be a permutation such that for . Observe that for any other we have for some , otherwise we would obtain a different cycle through the same set of vertices and, consequently, a shorter cycle. Finally
Since is acyclic there exists a topological ordering i.e. a permutation such that whenever there is an edge from to . It is easy to see that this permutation solves the problem.
Transcribed from the official solutions, page 4. This transcription has not been checked a second time; if in doubt, look at the original.
Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.
How did it go?
Moves you mark come back sooner in triage.