uniolympiads Ελληνικά

IMC 2016, Day 1, Problem 2

Let kk and nn be positive integers. A sequence (A1,…,Ak)(A_1, \dots, A_k) of n×nn \times n real matrices is preferred by Ivan the Confessor if Ai2≠0A_i^2 \ne 0 for 1≤i≤k1 \le i \le k, but AiAj=0A_iA_j = 0 for 1≤i,j≤k1 \le i, j \le k with i≠ji \ne j. Show that k≤nk \le n in all preferred sequences, and give an example of a preferred sequence with k=nk = n for each nn.

Original from the official PDFLet k and n be positive integers. A sequence (A 1 , . . . , A k ) of n × n real matrices is preferred by Ivan the Confessor if A 2 i 6 = 0 for 1 ≤ i ≤ k , but A i A j = 0 for 1 ≤ i, j ≤ k with i 6 = j . Show that k ≤ n in all preferred sequences, and give an example of a preferred sequence with k = n for each n . Problem 2.

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

(Proposed by Fedor Petrov, St. Petersburg State University)

Solution 1. For every i=1,…,ni = 1,\ldots,n, since Ai⋅Ai≠0A_i\cdot A_i \ne 0, there is a column vi∈Rnv_i\in\mathbb{R}^n in AiA_i such that Aivi≠0A_iv_i \ne 0. We will show that the vectors v1,…,vkv_1,\ldots,v_k are linearly independent; this immediately proves k≤nk\le n.

Suppose that a linear combination of v1,…,vkv_1,\ldots,v_k vanishes:

c1v1+…+ckvk=0,c1,…,ck∈R.c_1v_1 + \ldots + c_kv_k = 0, \quad c_1,\ldots,c_k\in\mathbb{R}.
For i≠ji\ne j we have AiAj=0A_iA_j = 0; in particular, Aivj=0A_iv_j = 0. Now, for each i=1,…,ni = 1,\ldots,n, from
0=Ai(c1v1+…+ckvk)=∑j=1kcj(Aivj)=ci(Aivi)0 = A_i(c_1v_1 + \ldots + c_kv_k) = \sum_{j=1}^k c_j(A_iv_j) = c_i(A_iv_i)
we can see that ci=0c_i = 0. Hence, c1=…=ck=0c_1 = \ldots = c_k = 0.

The case k=nk = n is possible: if AiA_i has a single 11 in the main diagonal at the iith position and its other entries are zero then Ai2=AiA_i^2 = A_i and AiAj=0A_iA_j = 0 for i≠ji\ne j.

Remark. The solution above can be re-formulated using block matrices in the following way. Consider

(A1A2…Ak)(A1A2⋮Ak)=(A120…00A22…0⋮⋮⋱⋮00…Ak2).\begin{pmatrix} A_1 & A_2 & \ldots & A_k \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ \vdots \\ A_k \end{pmatrix} = \begin{pmatrix} A_1^2 & 0 & \ldots & 0 \\ 0 & A_2^2 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & A_k^2 \end{pmatrix}.
It is easy to see that the rank of the left-hand side is at most nn; the rank of the right-hand side is at least kk.

Solution 2. Let UiU_i and KiK_i be the image and the kernel of the matrix AiA_i (considered as a linear operator on Rn\mathbb{R}^n), respectively. For every pair i,ji,j of indices, we have Uj⊂KiU_j\subset K_i if and only if i≠ji\ne j.

Let X0=RnX_0 = \mathbb{R}^n and let Xi=K1∩K2∩⋯∩KiX_i = K_1\cap K_2\cap\cdots\cap K_i for i=1,…,ki = 1,\ldots,k, so X0⊃X1⊃…⊃XkX_0\supset X_1\supset\ldots\supset X_k. Notice also that Ui⊂Xi−1U_i\subset X_{i-1} because Ui⊂KjU_i\subset K_j for every j<ij<i, and Ui⊄XiU_i\not\subset X_i because Ui⊄KiU_i\not\subset K_i. Hence, Xi≠Xi−1X_i\ne X_{i-1}; XiX_i is a proper subspace of Xi−1X_{i-1}.

Now, from

n=dim⁡X0>dim⁡X1>…>dim⁡Xk≥0n = \dim X_0 > \dim X_1 > \ldots > \dim X_k \ge 0
we get k≥nk\ge n.

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?