# Maximum Trace over All Permutations: Official Solution

*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*

*Task 2 of the municipal stage (Moscow) of the All-Russian School Olympiad (VsOSh) 2025/26 in artificial intelligence, grades 9–11: official answer and solution (the statement is in a separate file). Original: [ans-ai-9-11-mun-msk-25-26.pdf](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/ans-ai-9-11-mun-msk-25-26.pdf).*

**a)** Find the largest possible value of $tr(AB)$.

**Answer:** 339

**Scoring criterion:** exact match of the answer — 50 points

**b)** Find the largest possible value of $tr(BA)$.

**Answer:** 339

**Scoring criterion:** exact match of the answer — 50 points

**Maximum score for the task — 100**

**Solution.** A useful property: for any square matrices of the same size, $\mathrm{tr}(AB) = \mathrm{tr}(BA)$. Therefore, it suffices to maximise $\mathrm{tr}(AB)$.

Let $B = \begin{pmatrix} x & y \\ z & w \end{pmatrix}$. Then

$$
AB = \begin{pmatrix} -1 & 4 \\ 5 & 10 \end{pmatrix} \begin{pmatrix} x & y \\ z & w \end{pmatrix} = \begin{pmatrix} -x + 4z & -y + 4w \\ 5x + 10z & 5y + 10w \end{pmatrix},
$$

and therefore

$$
\mathrm{tr}(AB) = (-x + 4z) + (5y + 10w) = -x + 4z + 5y + 10w.
$$

We need to assign $-5, -4, 20, 25$ to $x, y, z, w$ so as to maximise the linear form with coefficients $-1, 5, 4, 10$ respectively. By the rearrangement inequality, the maximum is attained when the largest coefficient is matched with the largest number, and so on in decreasing order:

$$
10 \leftrightarrow 25, \quad 5 \leftrightarrow 20, \quad 4 \leftrightarrow (-4), \quad (-1) \leftrightarrow (-5).
$$

That is, $w = 25$, $y = 20$, $z = -4$, $x = -5$. Then

$$
\mathrm{tr}(AB) = -(-5) + 4 \cdot (-4) + 5 \cdot 20 + 10 \cdot 25 = 5 - 16 + 100 + 250 = 339.
$$

By the property $\mathrm{tr}(AB) = \mathrm{tr}(BA)$, the same value is obtained for $BA$ as well.

Thus, the largest possible sum of the diagonal elements is 339.