IMC 2023 · Day 2 · P6

Hint: Construct an invariant quantity that does not change during Ivan's prcedure.

We show that starting from $A = \begin{pmatrix} 2 & 3 \\ 2 & 4 \end{pmatrix}$, Ivan cannot reach the matrix $B = \begin{pmatrix} 2 & 4 \\ 2 & 3 \end{pmatrix}$.

Notice first that the allowed operations preserve the positivity of entries; all matrices Ivan can reach have only positive entries.

For every matrix $X = \begin{pmatrix} x_{11} & x_{12} \\ x_{21} & x_{22} \end{pmatrix}$ with positive entries, let $L(X) = \begin{pmatrix} \log_2 x_{11} & \log_2 x_{12} \\ \log_2 x_{21} & \log_2 x_{22} \end{pmatrix}$. By taking logarithms of the entries, the steps in Ivan game will be replaced by adding or subtracting a row or column to the other row. Such standard row and column operations preserve the determinant. Hence, if the matrices in the game are $A = X_0, X_1, X_2, \dots$, then we have $\det L(A) = \det L(X_1) = \det L(X_2) = \dots$, and it suffices to verify that $\det L(A) \ne \det L(B)$.

Indeed, $$\det L(A) = \log_2 2 \cdot \log_2 4 - \log_2 4 \cdot \log_2 3$$

= \log_2 (4/3) > 0 and similarly $\det L(B) < 0$, so $\det L(A) \ne \det L(B)$.