uniolympiads English

IMC 2007, Ημέρα 2, Θέμα 5

For each positive integer kk, find the smallest number nkn_k for which there exist real nk×nkn_k \times n_k matrices A1,A2,…,AkA_1, A_2, \dots, A_k such that all of the following conditions hold:

(1) A12=A22=⋯=Ak2=0A_1^2 = A_2^2 = \dots = A_k^2 = 0,

(2) AiAj=AjAiA_iA_j = A_jA_i for all 1≤i,j≤k1 \le i, j \le k, and

(3) A1A2…Ak≠0A_1A_2 \dots A_k \ne 0.

Πρωτότυπο από το επίσημο PDFFor each positive integer k, find the smallest number n k for which there exist real n k × n k matrices A 1 , A 2 , . . . , A k such that all of the following conditions hold: (1) A 21 = A 22 = . . . = A 2 k = 0, (2) A i A j = A j A i for all 1 ≤ i, j ≤ k, and (3) A 1 A 2 . . . A k 6 = 0.

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

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

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

Επίσημη λύση

Solution. The anwser is nk=2kn_k=2^k. In that case, the matrices can be constructed as follows: Let VV be the nn-dimensional real vector space with basis elements [S][S], where SS runs through all n=2kn=2^k subsets of {1,2,…,k}\{1,2,\dots,k\}. Define AiA_i as an endomorphism of VV by

Ai[S]={0if i∈S[S∪{i}]if i∉SA_i[S]=\begin{cases}0&\text{if }i\in S\\{}[S\cup\{i\}]&\text{if }i\notin S\end{cases}
for all i=1,2,…,ki=1,2,\dots,k and S⊂{1,2,…,k}S\subset\{1,2,\dots,k\}. Then Ai2=0A_i^2=0 and AiAj=AjAiA_iA_j=A_jA_i. Furthermore,
A1A2…Ak[∅]=[{1,2,…,k}],A_1A_2\ldots A_k[\emptyset]=[\{1,2,\dots,k\}],
and hence A1A2…Ak≠0A_1A_2\ldots A_k\ne0.

Now let A1,A2,…,AkA_1,A_2,\dots,A_k be n×nn\times n matrices satisfying the conditions of the problem; we prove that n≥2kn\ge2^k. Let vv be a real vector satisfying A1A2…Ak v≠0A_1A_2\ldots A_k\,v\ne0. Denote by P\mathcal P the set of all subsets of {1,2,…,k}\{1,2,\dots,k\}. Choose a complete ordering ≺\prec on P\mathcal P with the property

X≺Y⇒∣X∣≤∣Y∣for all X,Y∈P.X\prec Y\quad\Rightarrow\quad|X|\le|Y|\quad\text{for all }X,Y\in\mathcal P.
For every element X={x1,x2,…,xr}∈PX=\{x_1,x_2,\dots,x_r\}\in\mathcal P, define AX=Ax1Ax2…AxrA_X=A_{x_1}A_{x_2}\ldots A_{x_r} and vX=AXvv_X=A_Xv. Finally, write Xˉ={1,2,…,k}∖X\bar X=\{1,2,\dots,k\}\setminus X for the complement of XX.

Now take X,Y∈PX,Y\in\mathcal P with X⪵YX\precneqq Y. Then AXˉA_{\bar X} annihilates vYv_Y, because X⪵YX\precneqq Y implies the existence of some y∈Y∖X=Y∩Xˉy\in Y\setminus X=Y\cap\bar X, and

AXˉvY=AXˉ∖{y}AyAyvY∖{y}=0,A_{\bar X}v_Y=A_{\bar X\setminus\{y\}}A_yA_yv_{Y\setminus\{y\}}=0,
since Ay2=0A_y^2=0. So, AXˉA_{\bar X} annihilates the span of all the vYv_Y with X⪵YX\precneqq Y. This implies that vXv_X does not lie in this span, because AXˉvX=v{1,2,…,k}≠0A_{\bar X}v_X=v_{\{1,2,\dots,k\}}\ne0. Therefore, the vectors vXv_X (with X∈PX\in\mathcal P) are linearly independent; hence n≥∣P∣=2kn\ge|\mathcal P|=2^k.

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

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

Πώς πήγε;