uniolympiads English

IMC 2006, Ημέρα 1, Θέμα 3

Let AA be an n×nn \times n-matrix with integer entries and b1,…,bkb_1, \dots, b_k be integers satisfying det⁡A=b1⋅…⋅bk\det A = b_1 \cdot \ldots \cdot b_k. Prove that there exist n×nn \times n-matrices B1,…,BkB_1, \dots, B_k with integer entries such that A=B1⋅…⋅BkA = B_1 \cdot \ldots \cdot B_k and det⁡Bi=bi\det B_i = b_i for all i=1,…,ki = 1, \dots, k.

Πρωτότυπο από το επίσημο PDFLet A be an n × n-matrix with integer entries and b 1 , . . . , b k be integers satisfying det A = b 1 · . . . · b k . Prove that there exist n × n-matrices B 1 , . . . , B k with integer entries such that A = B 1 · . . . · B k and det B i = b i for all i = 1, . . . , k. (20 points)

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

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

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

Επίσημη λύση

Solution. By induction, it is enough to consider the case m=2m=2. Furthermore, we can multiply AA with any integral matrix with determinant 1 from the right or from the left, without changing the problem. Hence we can assume AA to be upper triangular.

Lemma. Let AA be an integral upper triangular matrix, and let b,cb,c be integers satisfying det⁡A=bc\det A=bc. Then there exist integral upper triangular matrices B,CB,C such that det⁡B=b\det B=b, det⁡C=c\det C=c, A=BCA=BC.

Proof. The proof is done by induction on nn, the case n=1n=1 being obvious. Assume the statement is true for n−1n-1. Let AA, bb, cc as in the statement of the lemma. Define BnnB_{nn} to be the greatest common divisor of bb and AnnA_{nn}, and put Cnn=AnnBnnC_{nn}=\frac{A_{nn}}{B_{nn}}. Since AnnA_{nn} divides bcbc, CnnC_{nn} divides bBnnc\frac{b}{B_{nn}}c, which divides cc. Hence CnnC_{nn} divides cc. Therefore, b′=bBnnb'=\frac{b}{B_{nn}} and c′=cCnnc'=\frac{c}{C_{nn}} are integers. Define A′A' to be the upper-left (n−1)×(n−1)(n-1)\times(n-1)-submatrix of AA; then det⁡A′=b′c′\det A'=b'c'. By induction we can find the upper-left (n−1)×(n−1)(n-1)\times(n-1)-part of BB and CC in such a way that det⁡B=b\det B=b, det⁡C=c\det C=c and A=BCA=BC holds on the upper-left (n−1)×(n−1)(n-1)\times(n-1)-submatrix of AA. It remains to define Bi,nB_{i,n} and Ci,nC_{i,n} such that A=BCA=BC also holds for the (i,n)(i,n)-th entry for all i<ni<n.

First we check that BiiB_{ii} and CnnC_{nn} are relatively prime for all i<ni<n. Since BiiB_{ii} divides b′b', it is certainly enough to prove that b′b' and CnnC_{nn} are relatively prime, i.e.

gcd⁡(bgcd⁡(b,Ann),Anngcd⁡(b,Ann))=1,\gcd\left(\frac{b}{\gcd(b,A_{nn})},\frac{A_{nn}}{\gcd(b,A_{nn})}\right)=1,
which is obvious. Now we define Bj,nB_{j,n} and Cj,nC_{j,n} inductively: Suppose we have defined Bi,nB_{i,n} and Ci,nC_{i,n} for all i=j+1,j+2,…,n−1i=j+1,j+2,\dots,n-1. Then Bj,nB_{j,n} and Cj,nC_{j,n} have to satisfy
Aj,n=Bj,jCj,n+Bj,j+1Cj+1,n+⋯+Bj,nCn,nA_{j,n}=B_{j,j}C_{j,n}+B_{j,j+1}C_{j+1,n}+\dots+B_{j,n}C_{n,n}
Since Bj,jB_{j,j} and Cn,nC_{n,n} are relatively prime, we can choose integers Cj,nC_{j,n} and Bj,nB_{j,n} such that this equation is satisfied. Doing this step by step for all j=n−1,n−2,…,1j=n-1,n-2,\dots,1, we finally get BB and CC such that A=BCA=BC. □\square

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

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

Πώς πήγε;