uniolympiads English

IMC 2008, Ημέρα 2, Θέμα 5

Let nn be a positive integer, and consider the matrix A=(aij)1≤i,j≤nA = (a_{ij})_{1 \le i,j \le n}, where

aij={1if i+j is a prime number,0otherwise.a_{ij} = \begin{cases} 1 & \text{if } i + j \text{ is a prime number,} \\ 0 & \text{otherwise.} \end{cases}

Prove that ∣det⁡A∣=k2|\det A| = k^2 for some integer kk.

Πρωτότυπο από το επίσημο PDFLet n be a positive integer, and consider the matrix A = (a ij ) 1≤i,j≤n , where ( 1 if i + j is a prime number, a ij = 0 otherwise. Prove that | det A| = k 2 for some integer k.

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

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

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

Επίσημη λύση

Solution. Call a square matrix of type (B), if it is of the form

(0b120…b1,2k−20b210b23…0b2,2k−10b320…b3,2k−20⋮⋮⋮⋱⋮⋮b2k−2,10b2k−2,3…0b2k−2,2k−10b2k−1,20…b2k−1,2k−20).\begin{pmatrix} 0 & b_{12} & 0 & \ldots & b_{1,2k-2} & 0 \\ b_{21} & 0 & b_{23} & \ldots & 0 & b_{2,2k-1} \\ 0 & b_{32} & 0 & \ldots & b_{3,2k-2} & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ b_{2k-2,1} & 0 & b_{2k-2,3} & \ldots & 0 & b_{2k-2,2k-1} \\ 0 & b_{2k-1,2} & 0 & \ldots & b_{2k-1,2k-2} & 0 \end{pmatrix}.
Note that every matrix of this form has determinant zero, because it has kk columns spanning a vector space of dimension at most k−1k-1.

Call a square matrix of type (C), if it is of the form

C′=(0c110c12…0c1,kc110c120…c1,k00c210c22…0c2,kc210c220…c2,k0⋮⋮⋮⋮⋮⋮⋮0ck,10ck,2…0ck,kck,10ck,20…ck,k0)C' = \begin{pmatrix} 0 & c_{11} & 0 & c_{12} & \ldots & 0 & c_{1,k} \\ c_{11} & 0 & c_{12} & 0 & \ldots & c_{1,k} & 0 \\ 0 & c_{21} & 0 & c_{22} & \ldots & 0 & c_{2,k} \\ c_{21} & 0 & c_{22} & 0 & \ldots & c_{2,k} & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & c_{k,1} & 0 & c_{k,2} & \ldots & 0 & c_{k,k} \\ c_{k,1} & 0 & c_{k,2} & 0 & \ldots & c_{k,k} & 0 \end{pmatrix}
By permutations of rows and columns, we see that
∣det⁡C′∣=∣det⁡(C00C)∣=∣det⁡C∣2,|\det C'| = \left|\det\begin{pmatrix} C & 0 \\ 0 & C \end{pmatrix}\right| = |\det C|^2,
where CC denotes the k×kk\times k-matrix with coefficients ci,jc_{i,j}. Therefore, the determinant of any matrix of type (C) is a perfect square (up to a sign).

Now let X′X' be the matrix obtained from AA by replacing the first row by (100…0)\begin{pmatrix} 1 & 0 & 0 & \ldots & 0 \end{pmatrix}, and let YY be the matrix obtained from AA by replacing the entry a11a_{11} by 00. By multi-linearity of the determinant, det⁡(A)=det⁡(X′)+det⁡(Y)\det(A) = \det(X') + \det(Y). Note that X′X' can be written as

X′=(10vX)X' = \begin{pmatrix} 1 & 0 \\ v & X \end{pmatrix}
for some (n−1)×(n−1)(n-1)\times(n-1)-matrix XX and some column vector vv. Then det⁡(A)=det⁡(X)+det⁡(Y)\det(A) = \det(X) + \det(Y). Now consider two cases. If nn is odd, then XX is of type (C), and YY is of type (B). Therefore, ∣det⁡(A)∣=∣det⁡(X)∣|\det(A)| = |\det(X)| is a perfect square. If nn is even, then XX is of type (B), and YY is of type (C); hence ∣det⁡(A)∣=∣det⁡(Y)∣|\det(A)| = |\det(Y)| is a perfect square.

The set of primes can be replaced by any subset of {2}∪{3,5,7,9,11,…}\{2\} \cup \{3, 5, 7, 9, 11, \ldots\}.

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

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

Πώς πήγε;