Home > Algebra, Uncategorized > IMC 2016 – Day 1 – Problem 2

## IMC 2016 – Day 1 – Problem 2

Problem 2. Let ${k}$ and ${n}$ be positive integers. A sequence ${(A_1,...,A_k)}$ of ${n\times n}$ matrices is preferred by Ivan the Confessor if ${A_i^2 \neq 0}$ for ${1\leq i \leq k}$, but ${A_iA_j = 0}$ for ${1\leq i,j \leq k}$ with ${i \neq j}$. Show that if ${k \leq n}$ in al preferred sequences and give an example of a preferred sequence with ${k=n}$ for each ${n}$.

Sketch of proof: The fact that ${A_iA_j = 0}$ for ${i \neq j}$ should imply somehow that the images of ${A_i}$, i.e. the spaces ${S_i = \{ y = A_ix, x \in \Bbb{R}^n \}}$ do not have much in common. Indeed, let’s suppose that ${y \in S_i \cap S_j}$, then ${y = A_i x_i = A_j x_j}$. If this happens, then ${A_i^2 x_i = A_j^2 x_j = 0}$. Now we know that ${A_i^2 \neq 0}$ for every ${i}$ which implies the existence of ${x_i}$ such that ${A_i^2 x_i \neq 0}$ for every ${i}$.

In this way, the elements ${y_i = A_ix_i}$ are such that ${y_i \in S_i}$ and ${y_i \notin S_j}$ for ${i \neq j}$. Since ${S_i}$ are linear subspaces of ${\Bbb{R}^n}$ this implies, in particular that the family ${\{y_1,...,y_k\}}$ is linearly independent in ${\Bbb{R}^n}$. This implies that ${k \leq n}$.

An example when ${k=n}$ is the family of matrices which have ${1}$ on the ${i}$-th diagonal position and ${0}$ elsewhere.