Maths Olympiad Prep

Library / /512 of 520

Algebra Difficulty 8.3 Shortlist Prove it

Let AA be an nnxnn matrix with integer entries and b1,b2,...,bkb_{1},b_{2},...,b_{k} be integers satisfying detA=b1b2...bkdetA=b_{1}\cdot b_{2}\cdot ...\cdot b_{k}. Prove that there exist nnxnn-matrices B1,B2,...,BkB_{1},B_{2},...,B_{k} with integers entries such that A=B1B2...BkA=B_{1}\cdot B_{2}\cdot ...\cdot B_{k} and detBi=bidetB_{i}=b_{i} for all i=1,...,ki=1,...,k.

Solution

1. **Reduction to the case k=2 k = 2 **:
- We start by noting that it suffices to prove the result for k=2 k = 2 . If detA=b1b2bk \det A = b_1 b_2 \cdots b_k , we can write detA=(b1bk1)bk \det A = (b_1 \cdots b_{k-1}) b_k . Then, we can find integer matrices Bk1 B_{k-1}' and Bk B_k such that A=Bk1Bk A = B_{k-1}' B_k with detBk1=b1bk1 \det B_{k-1}' = b_1 \cdots b_{k-1} and detBk=bk \det B_k = b_k . We can repeat this process iteratively.

2. **Case k=2 k = 2 **:
- Suppose A A is an n×n n \times n matrix with integer entries and detA=bc \det A = bc for some integers b b and c c . We need to show that there exist n×n n \times n integer matrices B B and C C such that A=BC A = BC and detB=b \det B = b , detC=c \det C = c .

3. Upper Triangular Matrices:
- Multiplying a matrix A A by elementary matrices representing row-addition operations does not alter the determinant of A A . If A=EA A' = E A is a row-reduced form of A A with E E a product of elementary matrices, then detE=1 \det E = 1 and E E has integer entries. Hence, it suffices to prove the problem for upper triangular matrices.

4. **Induction on n n **:
- Suppose A A is an upper triangular matrix with integer entries and detA=bc \det A = bc . We will use induction on n n .

5. **Base Case n=2 n = 2 **:
- Consider A=(mx0n) A = \begin{pmatrix} m & x \\ 0 & n \end{pmatrix} . We need to find B B and C C of the form:
B=(t1y0t2),C=(mt1z0nt2) B = \begin{pmatrix} t_1 & y \\ 0 & t_2 \end{pmatrix}, \quad C = \begin{pmatrix} \frac{m}{t_1} & z \\ 0 & \frac{n}{t_2} \end{pmatrix}
for some integers t1,t2,y,z t_1, t_2, y, z such that t1m t_1 \mid m and t2n t_2 \mid n . We have detA=mn=bc \det A = mn = bc and thus we need t1t2=b t_1 t_2 = b . Finally, y y and z z must satisfy x=t1z+nt2y x = t_1 z + \frac{n}{t_2} y . For a given x x , we can guarantee a solution (y,z) (y, z) exists only if gcd(t1,nt2)=1 \gcd(t_1, \frac{n}{t_2}) = 1 .

6. Lemma:
- If bmn b \mid mn , then we can find t1m t_1 \mid m and t2n t_2 \mid n such that b=t1t2 b = t_1 t_2 and gcd(t1,nt2)=1 \gcd(t_1, \frac{n}{t_2}) = 1 .
- Proof of Lemma: Assume mn mn and b b have the same set of prime factors. It suffices to prove the lemma when b b , m m , and n n are all powers of the same prime. If bn b \mid n , choose t1=bn t_1 = \frac{b}{n} and t2=n t_2 = n . If nb n \mid b , choose t1=1 t_1 = 1 and t2=b t_2 = b .

7. Inductive Step:
- Suppose A A is an n×n n \times n matrix and let A A' be the lower-right (n1)×(n1) (n-1) \times (n-1) submatrix of A A . Denote m=A1,1 m = A_{1,1} and n=detA n = \det A' . In block form:
A=(mX0A) A = \begin{pmatrix} m & X \\ 0 & A' \end{pmatrix}
Since A A is upper triangular, detA=A1,1detA=mn=bc \det A = A_{1,1} \det A' = mn = bc . By the lemma, we can find b1,c1,b2,c2 b_1, c_1, b_2, c_2 such that m=b2c2 m = b_2 c_2 and n=b1c1 n = b_1 c_1 with gcd(b2,c1)=1 \gcd(b_2, c_1) = 1 . By the inductive hypothesis, we can find (n1)×(n1) (n-1) \times (n-1) matrices B B' and C C' such that A=BC A' = B' C' and detB=b1 \det B' = b_1 , detC=c1 \det C' = c_1 .

8. **Constructing B B and C C **:
- Take B B and C C in block form:
B=(b2Y0B),C=(c2Z0C) B = \begin{pmatrix} b_2 & Y \\ 0 & B' \end{pmatrix}, \quad C = \begin{pmatrix} c_2 & Z \\ 0 & C' \end{pmatrix}
We need row vectors Y Y and Z Z such that b2Z+YC=X b_2 Z + Y C' = X . Write Y=[y1,,yn1] Y = [y_1, \ldots, y_{n-1}] and Z=[z1,,zn1] Z = [z_1, \ldots, z_{n-1}] and X=[x1,,xn1] X = [x_1, \ldots, x_{n-1}] .

9. **Solving for Y Y and Z Z **:
- Matching the first coordinate, we have b2z1+y1C1,1=x1 b_2 z_1 + y_1 C'_{1,1} = x_1 . There exists an integer solution (y1,z1) (y_1, z_1) because gcd(b2,C1,1)gcd(b2,det(C))=gcd(b2,c1)=1 \gcd(b_2, C'_{1,1}) \mid \gcd(b_2, \det(C')) = \gcd(b_2, c_1) = 1 .
- Matching the second coordinate, we have b2z2+y1C1,2+y2C2,2=x2 b_2 z_2 + y_1 C'_{1,2} + y_2 C'_{2,2} = x_2 , which becomes b2z2+y2C2,2=x2y1C1,2 b_2 z_2 + y_2 C'_{2,2} = x_2 - y_1 C'_{1,2} . This admits a solution (y2,z2) (y_2, z_2) for the same reason as above.
- Continue in this manner to determine Y Y and Z Z satisfying the relation. The key is that b2 b_2 is relatively prime to c1=detC c_1 = \det C' and thus to all the diagonal entries of C C' .

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.