uniolympiads English

IMC 2007, Ημέρα 1, Θέμα 2

Let n≥2n \ge 2 be an integer. What is the minimal and maximal possible rank of an n×nn \times n matrix whose n2n^2 entries are precisely the numbers 1,2,…,n21, 2, \dots, n^2?

Πρωτότυπο από το επίσημο PDFLet n ≥ 2 be an integer. What is the minimal and maximal possible rank of an n × n matrix whose n 2 entries are precisely the numbers 1, 2, . . . , n 2 ?

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

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

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

Επίσημη λύση

Solution. The minimal rank is 2 and the maximal rank is nn. To prove this, we have to show that the rank can be 2 and nn but it cannot be 1.

(i) The rank is at least 2. Consider an arbitrary matrix A=[aij]A=[a_{ij}] with entries 1,2,…,n21,2,\dots,n^2 in some order. Since permuting rows or columns of a matrix does not change its rank, we can assume that 1=a11<a21<⋯<an11=a_{11}<a_{21}<\dots<a_{n1} and a11<a12<⋯<a1na_{11}<a_{12}<\dots<a_{1n}. Hence an1≥na_{n1}\ge n and a1n≥na_{1n}\ge n and at least one of these inequalities is strict. Then det⁡[a11a1nan1ann]<1⋅n2−n⋅n=0\det\begin{bmatrix}a_{11}&a_{1n}\\a_{n1}&a_{nn}\end{bmatrix}<1\cdot n^2-n\cdot n=0 so rk⁡(A)≥rk⁡[a11a1nan1ann]≥2\operatorname{rk}(A)\ge\operatorname{rk}\begin{bmatrix}a_{11}&a_{1n}\\a_{n1}&a_{nn}\end{bmatrix}\ge2.

(ii) The rank can be 2. Let

T=[12…nn+1n+2…2n⋮⋮⋱⋮n2−n+1n2−n+2…n2]T=\begin{bmatrix}1&2&\dots&n\\n+1&n+2&\dots&2n\\\vdots&\vdots&\ddots&\vdots\\n^2-n+1&n^2-n+2&\dots&n^2\end{bmatrix}
The ithi^{\text{th}} row is (1,2,…,n)+n(i−1)⋅(1,1,…,1)(1,2,\dots,n)+n(i-1)\cdot(1,1,\dots,1) so each row is in the two-dimensional subspace generated by the vectors (1,2,…,n)(1,2,\dots,n) and (1,1,…,1)(1,1,\dots,1). We already proved that the rank is at least 2, so rk⁡(T)=2\operatorname{rk}(T)=2.

(iii) The rank can be nn, i.e. the matrix can be nonsingular. Put odd numbers into the diagonal, only even numbers above the diagonal and arrange the entries under the diagonal arbitrarily. Then the determinant of the matrix is odd, so the rank is complete.

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

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

Πώς πήγε;