Maths Olympiad Prep

Library / /383 of 520

Algebra Difficulty 7.2 National olympiad, round 2 Find the answer

The linear operator AA on a finite-dimensional vector space VV is called an involution if
A2=IA^{2}=I, where II is the identity operator. Let dimV=n\dim V=n.
i) Prove that for every involution AA on VV, there exists a basis of VV consisting of eigenvectors
of AA.
ii) Find the maximal number of distinct pairwise commuting involutions on VV.

A number or a short expression. Spacing and $ signs are ignored.

Solution

### Part (i)
1. Definition and Setup:
- Let A A be an involution on V V , meaning A2=I A^2 = I , where I I is the identity operator.
- We need to show that there exists a basis of V V consisting of eigenvectors of A A .

2. **Eigenvalues of A A **:
- Since A2=I A^2 = I , the eigenvalues λ \lambda of A A must satisfy λ2=1 \lambda^2 = 1 .
- Therefore, the possible eigenvalues of A A are λ=1 \lambda = 1 and λ=1 \lambda = -1 .

3. **Decomposition of V V **:
- Let V1 V_1 be the eigenspace corresponding to the eigenvalue 1 1 , i.e., V1={vVAv=v} V_1 = \{ v \in V \mid Av = v \} .
- Let V1 V_{-1} be the eigenspace corresponding to the eigenvalue 1 -1 , i.e., V1={wVAw=w} V_{-1} = \{ w \in V \mid Aw = -w \} .

4. Direct Sum of Eigenspaces:
- Any vector xV x \in V can be written as x=x+Ax2+xAx2 x = \frac{x + Ax}{2} + \frac{x - Ax}{2} .
- Define v=x+Ax2 v = \frac{x + Ax}{2} and w=xAx2 w = \frac{x - Ax}{2} .
- Notice that Av=A(x+Ax2)=Ax+A2x2=Ax+x2=v Av = A\left(\frac{x + Ax}{2}\right) = \frac{Ax + A^2x}{2} = \frac{Ax + x}{2} = v , so vV1 v \in V_1 .
- Similarly, Aw=A(xAx2)=AxA2x2=Axx2=w Aw = A\left(\frac{x - Ax}{2}\right) = \frac{Ax - A^2x}{2} = \frac{Ax - x}{2} = -w , so wV1 w \in V_{-1} .
- Therefore, x=v+w x = v + w with vV1 v \in V_1 and wV1 w \in V_{-1} .

5. Basis of Eigenvectors:
- Since V1 V_1 and V1 V_{-1} are eigenspaces corresponding to distinct eigenvalues, they are linearly independent.
- The direct sum V=V1V1 V = V_1 \oplus V_{-1} spans V V .
- Hence, there exists a basis of V V consisting of eigenvectors of A A .

### Part (ii)
1. Commuting Involutions:
- We need to find the maximal number of distinct pairwise commuting involutions on V V .

2. Simultaneous Diagonalization:
- Recall that any set of pairwise commuting, diagonalizable matrices is simultaneously diagonalizable.
- Since involutions are diagonalizable with eigenvalues ±1 \pm 1 , we can assume that all the matrices are diagonal in some common basis.

3. Diagonal Entries:
- In the common basis, each involution Ai A_i can be represented as a diagonal matrix with entries ±1 \pm 1 .
- Each diagonal entry can independently be 1 1 or 1 -1 .

4. Number of Distinct Involutions:
- For an n n -dimensional vector space V V , there are n n diagonal entries.
- Each entry can be independently 1 1 or 1 -1 , leading to 2n 2^n possible distinct diagonal matrices.
- Therefore, the maximal number of distinct pairwise commuting involutions on V V is 2n 2^n .

The final answer is 2n \boxed{ 2^n } .

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

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.