Maths Olympiad Prep

Library / /19 of 64

Algebra Difficulty 7.7 National olympiad, round 2 Find the answer

For which positive integers nn is there an n×nn \times n matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

A number or a short expression. Spacing and $ signs are ignored.

Solution

The answer is nn odd. Let II denote the n×nn\times n identity matrix, and let AA denote the n×nn\times n matrix all of whose entries are 11. If nn is odd, then the matrix AIA-I satisfies the conditions of the problem: the dot product of any row with itself is n1n-1, and the dot product of any two distinct rows is n2n-2. Conversely, suppose nn is even, and suppose that the matrix MM satisfied the conditions of the problem. Consider all matrices and vectors mod 22. Since the dot product of a row with itself is equal mod 22 to the sum of the entries of the row, we have Mv=0M v = 0 where vv is the vector (1,1,,1)(1,1,\ldots,1), and so MM is singular. On the other hand, MMT=AIM M^T = A-I; since (AI)2=A22A+I=(n2)A+I=I, (A-I)^2 = A^2-2A+I = (n-2)A+I = I, we have (detM)2=det(AI)=1(\det M)^2 = \det(A-I) = 1 and detM=1\det M = 1, contradicting the fact that MM is singular.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.