uniolympiads Ελληνικά

IMC 2005, Day 1, Problem 1

Let AA be the n×nn \times n matrix, whose (i,j)th(i, j)^{\text{th}} entry is i+ji + j for all i,j=1,2,…,ni, j = 1, 2, \dots, n. What is the rank of AA?

Original from the official PDFLet A be the n × n matrix, whose (i, j) th entry is i + j for all i, j = 1, 2, . . . , n. What is the rank of A?

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 1. For n=1n=1 the rank is 1. Now assume n≥2n\ge2. Since A=(i)i,j=1n+(j)i,j=1nA=(i)_{i,j=1}^n+(j)_{i,j=1}^n, matrix AA is the sum of two matrixes of rank 1. Therefore, the rank of AA is at most 2. The determinant of the top-left 2×22\times2 minor is −1-1, so the rank is exactly 2.

Therefore, the rank of AA is 1 for n=1n=1 and 2 for n≥2n\ge2.

Solution 2. Consider the case n≥2n\ge2. For i=n,n−1,…,2i=n,n-1,\dots,2, subtract the (i−1)th(i-1)^{\text{th}} row from the nthn^{\text{th}} row. Then subtract the second row from all lower rows.

rank(23…n+134…n+2⋮⋱⋮n+1n+2…2n)=rank(23…n+111…1⋮⋱⋮11…1)=rank(12…n11…100…0⋮⋱⋮00…0)=2.\mathit{rank}\begin{pmatrix} 2 & 3 & \dots & n+1\\ 3 & 4 & \dots & n+2\\ \vdots & & \ddots & \vdots\\ n+1 & n+2 & \dots & 2n \end{pmatrix} = \mathit{rank}\begin{pmatrix} 2 & 3 & \dots & n+1\\ 1 & 1 & \dots & 1\\ \vdots & & \ddots & \vdots\\ 1 & 1 & \dots & 1 \end{pmatrix} = \mathit{rank}\begin{pmatrix} 1 & 2 & \dots & n\\ 1 & 1 & \dots & 1\\ 0 & 0 & \dots & 0\\ \vdots & & \ddots & \vdots\\ 0 & 0 & \dots & 0 \end{pmatrix} = 2.

Transcribed from the official solutions, page 1. 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?