uniolympiads Ελληνικά

IMC 2001, Day 2, Problem 4

Let A=(ak,ℓ)k,ℓ=1,…,nA = (a_{k,\ell})_{k,\ell=1,\dots,n} be an n×nn \times n complex matrix such that for each m∈{1,…,n}m \in \{1, \dots, n\} and 1≤j1<⋯<jm≤n1 \le j_1 < \dots < j_m \le n the determinant of the matrix (ajk,jℓ)k,ℓ=1,…,m(a_{j_k,j_\ell})_{k,\ell=1,\dots,m} is zero. Prove that An=0A^n = 0 and that there exists a permutation σ∈Sn\sigma \in S_n such that the matrix

(aσ(k),σ(ℓ))k,ℓ=1,…,n(a_{\sigma(k),\sigma(\ell)})_{k,\ell=1,\dots,n}

has all of its nonzero elements above the diagonal.

Original from the official PDFLet A = (a k,` ) k,`=1,...,n be an n × n complex matrix such that for each m ∈ {1, . . . , n} and 1 ≤ j 1 < . . . < j m ≤ n the determinant of the matrix (a j k ,j ` ) k,`=1,...,m is zero. Prove that A n = 0 and that there exists a permutation σ ∈ S n such that the matrix (a σ(k),σ(`) ) k,`=1,...,n 3 has all of its nonzero elements above the diagonal.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

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 GG with nn vertices V1,…,VnV_1,\dots,V_n and a directed edge from VkV_k to VℓV_\ell when ak,ℓ≠0a_{k,\ell}\ne0. We shall prove that it is acyclic.

Assume that there exists a cycle and take one of minimum length mm. Let j1<…<jmj_1<\ldots<j_m be the vertices the cycle goes through and let σ0∈Sn\sigma_0\in S_n be a permutation such that ajk,jσ0(k)≠0a_{j_k,j_{\sigma_0(k)}}\ne0 for k=1,…,mk=1,\dots,m. Observe that for any other σ∈Sn\sigma\in S_n we have ajk,jσ(k)=0a_{j_k,j_{\sigma(k)}}=0 for some k∈{1,…,m}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⁡(ajk,jℓ)k,ℓ=1,…,m0=\det(a_{j_k,j_\ell})_{k,\ell=1,\dots,m}
=(−1)sign σ0∏k=1majk,jσ0(k)+∑σ≠σ0(−1)sign σ∏k=1majk,jσ(k)≠0,=(-1)^{\mathrm{sign}\ \sigma_0}\prod_{k=1}^ma_{j_k,j_{\sigma_0(k)}}+\sum_{\sigma\ne\sigma_0}(-1)^{\mathrm{sign}\ \sigma}\prod_{k=1}^ma_{j_k,j_{\sigma(k)}}\ne0,
which is a contradiction.

Since GG is acyclic there exists a topological ordering i.e. a permutation σ∈Sn\sigma\in S_n such that k<ℓk<\ell whenever there is an edge from Vσ(k)V_{\sigma(k)} to Vσ(ℓ)V_{\sigma(\ell)}. 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?