uniolympiads Ελληνικά

IMC 2006, Day 1, Problem 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.

Original from the official 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)

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

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

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?