uniolympiads Ελληνικά

IMC 2010, Day 2, Problem 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.

Original from the official 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.

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. 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.

Transcribed from the official solutions, pages 3–4. 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?