IMC 2016 · Day 1 · P2

For every $i = 1, \dots, n$, since $A_i \cdot A_i \ne 0$, there is a column $v_i \in \mathbb{R}^n$ in $A_i$ such that $A_i v_i \ne 0$. We will show that the vectors $v_1, \dots, v_k$ are linearly independent; this immediately proves $k \le n$.

Suppose that a linear combination of $v_1, \dots, v_k$ vanishes: $$c_1 v_1 + \dots + c_k v_k = 0, \qquad c_1, \dots, c_k \in \mathbb{R}.$$ For $i \ne j$ we have $A_i A_j = 0$; in particular, $A_i v_j = 0$. Now, for each $i = 1, \dots, n$, from $$0 = A_i (c_1 v_1 + \dots + c_k v_k) = \sum_{j=1}^{k} c_j (A_i v_j) = c_i (A_i v_i)$$ we can see that $c_i = 0$. Hence, $c_1 = \dots = c_k = 0$.

The case $k = n$ is possible: if $A_i$ has a single 1 in the main diagonal at the $i$th position and its other entries are zero then $A_i^2 = A_i$ and $A_i A_j = 0$ for $i \ne j$.

Remark. The solution above can be re-formulated using block matrices in the following way. Consider $$\begin{pmatrix} A_1 \\ A_2 \\ \vdots \\ A_k \end{pmatrix} \begin{pmatrix} A_1 & A_2 & \dots & A_k \end{pmatrix} = \begin{pmatrix} A_1^2 & 0 & \dots & 0 \\ 0 & A_2^2 & \ddots & \vdots \\ \vdots & \ddots & \ddots & 0 \\ 0 & 0 & \dots & A_k^2 \end{pmatrix}.$$ It is easy to see that the rank of the left-hand side is at most $n$; the rank of the right-hand side is at least $k$.

Let $U_i$ and $K_i$ be the image and the kernel of the matrix $A_i$ (considered as a linear operator on $\mathbb{R}^n$), respectively. For every pair $i, j$ of indices, we have $U_j \subset K_i$ if and only if $i \ne j$.

Let $X_0 = \mathbb{R}^n$ and let $X_i = K_1 \cap K_2 \cap \dots \cap K_i$ for $i = 1, \dots, k$, so $X_0 \supset X_1 \supset \dots \supset X_k$. Notice also that $U_i \subset X_{i-1}$ because $U_i \subset K_j$ for every $j < i$, and $U_i \not\subset X_i$ because $U_i \not\subset K_i$. Hence, $X_i \ne X_{i-1}$; $X_i$ is a proper subspace of $X_{i-1}$.

Now, from $$n = \dim X_0 > \dim X_1 > \dots > \dim X_k \ge 0$$ we get $k \ge n$.