IMC 2007 · Day 2 · P11

The anwser is $n_k = 2^k$. In that case, the matrices can be constructed as follows: Let $V$ be the $n$-dimensional real vector space with basis elements $[S]$, where $S$ runs through all $n = 2^k$ subsets of $\{1, 2, \dots, k\}$. Define $A_i$ as an endomorphism of $V$ by $$A_i [S] = \begin{cases} 0 & \text{if } i \in S \\ [S \cup \{i\}] & \text{if } i \notin S \end{cases}$$ for all $i = 1, 2, \dots, k$ and $S \subset \{1, 2, \dots, k\}$. Then $A_i^2 = 0$ and $A_i A_j = A_j A_i$. Furthermore, $$A_1 A_2 \dots A_k [\emptyset] = [\{1, 2, \dots, k\}],$$ and hence $A_1 A_2 \dots A_k \ne 0$.

Now let $A_1, A_2, \dots, A_k$ be $n \times n$ matrices satisfying the conditions of the problem; we prove that $n \ge 2^k$. Let $v$ be a real vector satisfying $A_1 A_2 \dots A_k v \ne 0$. Denote by $\mathcal{P}$ the set of all subsets of $\{1, 2, \dots, k\}$. Choose a complete ordering $\prec$ on $\mathcal{P}$ with the property $$X \prec Y \Rightarrow |X| \le |Y| \quad \text{for all } X, Y \in \mathcal{P}.$$ For every element $X = \{x_1, x_2, \dots, x_r\} \in \mathcal{P}$, define $A_X = A_{x_1} A_{x_2} \dots A_{x_r}$ and $v_X = A_X v$. Finally, write $\bar{X} = \{1, 2, \dots, k\} \setminus X$ for the complement of $X$.

Now take $X, Y \in \mathcal{P}$ with $X \prec Y$. Then $A_{\bar{X}}$ annihilates $v_Y$, because $X \prec Y$ implies the existence of some $y \in Y \setminus X = Y \cap \bar{X}$, and $$A_{\bar{X}} v_Y = A_{\bar{X} \setminus \{y\}} A_y A_y v_{Y \setminus \{y\}} = 0,$$ since $A_y^2 = 0$. So, $A_{\bar{X}}$ annihilates the span of all the $v_Y$ with $X \prec Y$. This implies that $v_X$ does not lie in this span, because $A_{\bar{X}} v_X = v_{\{1, 2, \dots, k\}} \ne 0$. Therefore, the vectors $v_X$ (with $X \in \mathcal{P}$) are linearly independent; hence $n \ge |\mathcal{P}| = 2^k$.