uniolympiads English

IMC 2012, Ημέρα 1, Θέμα 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.

Πρωτότυπο από το επίσημο 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.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 1–2. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;