Putnam 2025, Problem A-4

Find the minimal value of \( k \) such that there exist \( k \)-by-\( k \) real matrices \( A_1, \ldots, A_{2025} \) with the property that \( A_i A_j = A_j A_i \) if and only if \( |i - j| \in \{0, 1, 2024\} \).

Solution:
The minimal value of \( k \) is 3.

We first produce a suitable sequence of matrices with \( k = 3 \); for this, we conflate \( 3 \times 3 \) matrices with the linear transformations on \( \mathbb{R}^3 \) that they define. Choose unit vectors \( \mathbf{v}_1, \ldots, \mathbf{v}_{2025} \in \mathbb{R}^3 \) in general position (no two collinear, no three coplanar), interpreting the indices cyclically so that \( \mathbf{v}_i = \mathbf{v}_{2025 + i} \). Let \( A_i \) be the unique linear transformation for which
\[
A_i(\mathbf{v}_i) = \mathbf{v}_i, \quad A_i(\mathbf{v}_{i-1}) = A_i(\mathbf{v}_{i+1}) = 0.
\]
To check that \( A_i \) commutes with \( A_{i+1} \), note that the plane spanned by \( \mathbf{v}_{i-1} \) and \( \mathbf{v}_{i+1} \) intersects the plane spanned by \( \mathbf{v}_i \) and \( \mathbf{v}_{i+2} \) in a line; let \( \mathbf{w}_i \) be a nonzero vector along this line. (Explicitly, we may take \( \mathbf{w}_i = (\mathbf{v}_{i-1} \times \mathbf{v}_{i+1}) \times (\mathbf{v}_i \times \mathbf{v}_{i+2}) \).) Then \( \mathbf{v}_i, \mathbf{v}_{i+1}, \mathbf{w}_i \) is a basis of \( \mathbb{R}^3 \) with respect to which both \( A_i \) and \( A_{i+1} \) are diagonal, which implies that \( A_i \) and \( A_{i+1} \) commute.

To check that \( A_i \) does not commute with \( A_j \) when \( j - i \not\equiv 0, 1, -1 \pmod{2025} \), note that any (complex) eigenvector of \( A_i \) is either a scalar multiple of \( \mathbf{v}_i \) or a linear combination of \( \mathbf{v}_{i-1} \) and \( \mathbf{v}_{i+1} \). In particular \( \mathbf{v}_j \) is not an eigenvector of \( A_i \), whereas any matrix commuting with \( A_j \) must admit \( \mathbf{v}_j \) as an eigenvector.

We next show that no such sequence exists for \( k = 2 \). Assume by way of contradiction that such a sequence exists. Then none of the \( A_i \) can be a scalar matrix, as then it would commute with \( A_j \) for all \( j \). Also, no \( A_i \) can have two distinct complex eigenvalues: any matrix commuting with \( A_i \) would then be simultaneously diagonalizable with \( A_i \), and any two such matrices commute with each other. Hence each \( A_i \) has a unique real eigenvalue \( \lambda_i \) and a unique eigenvector \( \mathbf{v}_i \) up to scaling; we can replace each \( A_i \) with \( A_i - \lambda_i I \) (where \( I \) denotes the \( 2 \times 2 \) identity matrix) to reduce to the case where each \( A_i \) is nilpotent. However, at this point \( A_i \) can only commute with \( A_{i+1} \) if \( \mathbf{v}_i \) and \( \mathbf{v}_{i+1} \) are parallel, which again implies that all of the matrices commute with each other.

**Remark.** A special case of this construction is to take \( A_i := \mathbf{u}_i \mathbf{u}_i^T \) where the unit vectors \( \mathbf{u}_i \) and \( \mathbf{u}_j \) are orthogonal if and only if \( |j - i| \in \{1, 2024\} \).