uniolympiads English

IMC 2025, Ημέρα 1, Θέμα 3

Denote by S\mathcal{S} the set of all real symmetric 2025×20252025 \times 2025 matrices of rank 1 whose entries take values −1-1 or +1+1. Let A,B∈SA, B \in \mathcal{S} be matrices chosen independently uniformly at random. Find the probability that AA and BB commute, i.e. AB=BAAB = BA.

Πρωτότυπο από το επίσημο PDFDenote by S the set of all real symmetric 2025 × 2025 matrices of rank 1 whose entries take values −1 or +1. Let A, B ∈ S be matrices chosen independently uniformly at random. Find the probability that A and B commute, i.e. AB = BA.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(proposed by Marian Panţiruc, "Gheorghe Asachi" Technical University of Iaşi, Romania)

Solution. Let n=2025n = 2025. First, we give a charaterisation of matrices in S\mathcal{S}.

Suppose that A=(aij)i,j=1n∈SA = (a_{ij})_{i,j=1}^n \in \mathcal{S}. Since rk⁡A=1\operatorname{rk} A = 1, for every 1<i,j≤n1 < i, j \le n, we have

det⁡(a11a1jai1aij)=a11aij−ai1a1j=a11aij−ai1aj1=0.\det\begin{pmatrix} a_{11} & a_{1j} \\ a_{i1} & a_{ij} \end{pmatrix} = a_{11}a_{ij} - a_{i1}a_{1j} = a_{11}a_{ij} - a_{i1}a_{j1} = 0.

If a11=1a_{11} = 1 then this means aij=ai1aj1a_{ij} = a_{i1}a_{j1}. In this case, let u=(a11a21⋮an1)=(1a21⋮an1)u = \begin{pmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{n1} \end{pmatrix} = \begin{pmatrix} 1 \\ a_{21} \\ \vdots \\ a_{n1} \end{pmatrix}; then we have A=(ai1aj1)=uu⊤A = \big(a_{i1}a_{j1}\big) = uu^\top. Otherwise, if a11=−1a_{11} = -1, we have aij=−ai1aj1a_{ij} = -a_{i1}a_{j1}. In that case, let u=(−a11−a21⋮−an1)=(1−a21⋮−an1)u = \begin{pmatrix} -a_{11} \\ -a_{21} \\ \vdots \\ -a_{n1} \end{pmatrix} = \begin{pmatrix} 1 \\ -a_{21} \\ \vdots \\ -a_{n1} \end{pmatrix}; then A=−(ai1aj1)=−uu⊤A = -\big(a_{i1}a_{j1}\big) = -uu^\top.

Hence, all matrices in S\mathcal{S} can uniquely be written as ±uu⊤\pm uu^\top with a vector u=(1u2⋮un)u = \begin{pmatrix} 1 \\ u_2 \\ \vdots \\ u_n \end{pmatrix} such that u2,…,un∈{±1}u_2, \dots, u_n \in \{\pm 1\}. (Note that rk⁡(uu⊤)=1\operatorname{rk}(uu^\top) = 1 is satisfied.) In particular, we have ∣S∣=2n|\mathcal{S}| = 2^n, because the sign and the coordinates u2,…,unu_2, \dots, u_n can be chosen independently.

Now, if A=±uuTA = \pm uu^T and B=±vvTB = \pm vv^T are elements of S\mathcal{S}, then

AB=±(uu⊤)(vv⊤)=±u(u⊤v)v⊤=±u⋅⟨u,v⟩⋅v⊤=±⟨u,v⟩⋅(uivj)i,j=1nAB = \pm(uu^\top)(vv^\top) = \pm u(u^\top v)v^\top = \pm u \cdot \langle u, v\rangle \cdot v^\top = \pm\langle u, v\rangle \cdot \big(u_i v_j\big)_{i,j=1}^n
and similarly
BA=±⟨u,v⟩⋅(viuj)i,j=1n.BA = \pm\langle u, v\rangle \cdot \big(v_i u_j\big)_{i,j=1}^n.
Since n=2025n = 2025 is odd, it follows that ⟨u,v⟩≠0\langle u, v\rangle \ne 0. The first columns of the matrices uv⊤=(uivj)i,j=1nuv^\top = \big(u_i v_j\big)_{i,j=1}^n and vu⊤=(viuj)i,j=1nvu^\top = \big(v_i u_j\big)_{i,j=1}^n are uu and vv, respectively. Hence, AB=BAAB = BA if and only if u=vu = v; in other words, if A=±BA = \pm B.

For each A∈SA \in \mathcal{S}, there are precisely two suitable matrices B∈SB \in \mathcal{S}, so the probability that A,BA, B commute is 2∣S∣=12n−1\dfrac{2}{|\mathcal{S}|} = \dfrac{1}{2^{n-1}}.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;