2019 ROMANIAN MATHEMATICAL OLYMPIAD

Question

Let G be a finite group, and let x_1, , x_n be a labeling of its elements. Consider the n n matrix (a_ij), where a_ij = 1 if x_i x_j^-1 x_j x_i^-1, and a_ij = 0 otherwise. Establish the parity of the integer (a_ij). Amer. Math. Monthly

Accepted Answer

The determinant under consideration is an even integer. To prove this, we show the determinant divisible by the cardinality of the set

S = {x : x \in G, x \neq = x^{- 1}}

. Since a member of

G

is one of

S

if and only if its inverse is,

∣ S ∣

is even (possibly zero), and the conclusion follows.

To establish divisibility, recall that the value of a determinant does not change upon replacing a column by the sum of all columns. It is therefore sufficient to show that every row contains exactly

∣ S ∣

units.

To prove the latter, fix any row — say, the

i

-th —, let

J_{i} = {j : a_{ij} = 1}

and notice that the assignment

j \mapsto x_{i} x_{j}^{- 1}

defines a one-to-one map of

J_{i}

onto

S

. Consequently,

∣ J_{i} ∣ = ∣ S ∣

.