uniolympiads Ελληνικά

IMC 2012, Day 1, Problem 2

Let nn be a fixed positive integer. Determine the smallest possible rank of an n×nn \times n matrix that has zeros along the main diagonal and strictly positive real numbers off the main diagonal.

Original from the official PDFLet n be a fixed positive integer. Determine the smallest possible rank of an n × n matrix that has zeros along the main diagonal and strictly positive real numbers off the main 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

(Proposed by Ilya Bogdanov and Grigoriy Chelnokov, MIPT, Moscow)

Solution. For n=1n=1 the only matrix is (0)(0) with rank 0. For n=2n=2 the determinant of such a matrix is negative, so the rank is 2. We show that for all n≥3n\ge 3 the minimal rank is 3.

Notice that the first three rows are linearly independent. Suppose that some linear combination of them, with coefficients c1,c2,c3c_1,c_2,c_3, vanishes. Observe that from the first column one deduces that c2c_2 and c3c_3 either have opposite signs or both zero. The same applies to the pairs (c1,c2)(c_1,c_2) and (c1,c3)(c_1,c_3). Hence they all must be zero.

It remains to give an example of a matrix of rank (at most) 3. For example, the matrix

(021222…(n−1)2(−1)20212…(n−2)2⋮⋮⋮⋱⋮(−n+1)2(−n+2)2(−n+3)2…02)=((i−j)2)i,j=1n==(1222⋮n2)(1,1,…,1)−2(12⋮n)(1,2,…,n)+(11⋮1)(12,22,…,n2)\begin{aligned} &\begin{pmatrix} 0^2 & 1^2 & 2^2 & \ldots & (n-1)^2\\ (-1)^2 & 0^2 & 1^2 & \ldots & (n-2)^2\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ (-n+1)^2 & (-n+2)^2 & (-n+3)^2 & \ldots & 0^2 \end{pmatrix} = \Big((i-j)^2\Big)_{i,j=1}^{n} = \\ &= \begin{pmatrix}1^2\\2^2\\\vdots\\n^2\end{pmatrix}(1,1,\ldots,1) - 2\begin{pmatrix}1\\2\\\vdots\\n\end{pmatrix}(1,2,\ldots,n) + \begin{pmatrix}1\\1\\\vdots\\1\end{pmatrix}(1^2,2^2,\ldots,n^2) \end{aligned}
is the sum of three matrices of rank 1, so its rank cannot exceed 3.

Transcribed from the official solutions, pages 1–2. 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?