Problem 5 Let [n] = {1, 2, . . . ,n}. Suppose A1, . . .,Am are sets such that each |A| has even size and each intersection A; H A, has even size. In this problem we will prove that m g 2ng . Let IF = {0,1} be the eld of two elements and V = 11\"\". Let 51, . . . ,En, be the standard basis of V. Dene (,) : V x V > ]F as (vyw) = 'va. (1) Which properties of inner product does (,) satisfy, and which ones does it not? Let 1P([n]) be the power set of [n]. We have a map F : 1P([n]) > V dened as: F(X) = Z 61-. tax (ii) Prove that F is a bijection. (iii) Prove that X has even size if and only if ||F(X)|| = 0. (iv) For X,Y Q [n], prove that X F] Y has even size if and only if (Foo, PM) = 0. (v) Let W = Span(F(A1), F(A2), . . . , F(Am))- Prove that W g Wi. (vi) Prove that dim(W) + dim(WJ') = dim(V). Hint: Consider the m X to matrix whose rows are F(A1)T, . . . , F(Am)T. (vii) Prove that 2m 5 n