uniolympiads English

IMC 2010, Ημέρα 2, Θέμα 4

Let AA be a symmetric m×mm \times m matrix over the two-element field all of whose diagonal entries are zero. Prove that for every positive integer nn each column of the matrix AnA^n has a zero entry.

Πρωτότυπο από το επίσημο PDFLet A be a symmetric m × m matrix over the two-element field all of whose diagonal entries are zero. Prove that for every positive integer n each column of the matrix A n has a zero entry.

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

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

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

Επίσημη λύση

Solution. Denote by eke_k (1≤k≤m)(1\le k\le m) the mm-dimensional vector over F2F_2, whose kk-th entry is 1 and all the other elements are 0. Furthermore, let uu be the vector whose all entries are 1. The kk-th column of AnA^n is AnekA^ne_k. So the statement can be written as Anek≠uA^ne_k\ne u for all 1≤k≤m1\le k\le m and all n≥1n\ge1.

For every pair of vectors x=(x1,…,xm)x=(x_1,\dots,x_m) and y=(y1,…,ym)y=(y_1,\dots,y_m), define the bilinear form (x,y)=xTy=x1y1+...+xmym(x,y)=x^Ty=x_1y_1+...+x_my_m. The product (x,y)(x,y) has all basic properties of scalar products (except the property that (x,x)=0(x,x)=0 implies x=0x=0). Moreover, we have (x,x)=(x,u)(x,x)=(x,u) for every vector x∈F2mx\in F_2^m.

It is also easy to check that (w,Aw)=wTAw=0(w,Aw)=w^TAw=0 for all vectors ww, since AA is symmetric and its diagonal elements are 0.

Lemma. Suppose that v∈F2mv\in F_2^m a vector such that Anv=uA^nv=u for some n≥1n\ge1. Then (v,v)=0(v,v)=0.

Proof. Apply induction on nn. For odd values of nn we prove the lemma directly. Let n=2k+1n=2k+1 and w=Akvw=A^kv. Then

(v,v)=(v,u)=(v,Anv)=vTAnv=vTA2k+1v=(Akv,Ak+1v)=(w,Aw)=0.(v,v)=(v,u)=(v,A^nv)=v^TA^nv=v^TA^{2k+1}v=(A^kv,A^{k+1}v)=(w,Aw)=0.
Now suppose that nn is even, n=2kn=2k, and the lemma is true for all smaller values of nn. Let w=Akvw=A^kv; then Akw=Anv=uA^kw=A^nv=u and thus we have (w,w)=0(w,w)=0 by the induction hypothesis. Hence,
(v,v)=(v,u)=vTAnv=vTA2kv=(Akv)T(Akv)=(Akv,Akv)=(w,w)=0.(v,v)=(v,u)=v^TA^nv=v^TA^{2k}v=(A^kv)^T(A^kv)=(A^kv,A^kv)=(w,w)=0.
The lemma is proved.

Now suppose that Anek=uA^ne_k=u for some 1≤k≤m1\le k\le m and positive integer nn. By the Lemma, we should have (ek,ek)=0(e_k,e_k)=0. But this is impossible because (ek,ek)=1≠0(e_k,e_k)=1\ne0.

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

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

Πώς πήγε;