IMC 2001 · Day 2 · P10

We will only prove (2), since it implies (1). Consider a directed graph $G$ with $n$ vertices $V_1, \dots, V_n$ and a directed edge from $V_k$ to $V_\ell$ when $a_{k,\ell} \ne 0$. We shall prove that it is acyclic.

Assume that there exists a cycle and take one of minimum length $m$. Let $j_1 < \dots < j_m$ be the vertices the cycle goes through and let $\sigma_0 \in S_n$ be a permutation such that $a_{j_k, j_{\sigma_0(k)}} \ne 0$ for $k = 1, \dots, m$. Observe that for any other $\sigma \in S_n$ we have $a_{j_k, j_{\sigma(k)}} = 0$ for some $k \in \{1, \dots, m\}$, otherwise we would obtain a different cycle through the same set of vertices and, consequently, a shorter cycle. Finally $$0 = \det (a_{j_k, j_\ell})_{k,\ell = 1,\dots,m} = (-1)^{\operatorname{sign} \sigma_0} \prod_{k=1}^{m} a_{j_k, j_{\sigma_0(k)}} + \sum_{\sigma \ne \sigma_0} (-1)^{\operatorname{sign} \sigma} \prod_{k=1}^{m} a_{j_k, j_{\sigma(k)}} \ne 0,$$ which is a contradiction.

Since $G$ is acyclic there exists a topological ordering i.e. a permutation $\sigma \in S_n$ such that $k < \ell$ whenever there is an edge from $V_{\sigma(k)}$ to $V_{\sigma(\ell)}$. It is easy to see that this permutation solves the problem.