Library / Romanian Mathematical Olympiad /96 of 275

Romanian Mathematical Olympiad, 2019

Algebra Difficulty 5.4 AIME, harder Prove it Romania

Let $G$ be a finite group, and let $x_1, \dots, x_n$ be a labeling of its elements. Consider the $n \times n$ matrix $(a_{ij})$ , where $a_{ij} = 1$ if $x_i x_j^{-1} \neq x_j x_i^{-1}$ , and $a_{ij} = 0$ otherwise. Establish the parity of the integer $\det(a_{ij})$ .
Amer. Math. Monthly

Solution

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

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.