International Mathematics Competition
for University Students
2016

IMC2016: Day 1, Problem 2

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

Proposed by Fedor Petrov, St. Petersburg State University

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

Suppose that a linear combination of $v_1,\ldots,v_k$ vanishes: $$c_1 v_1 + \ldots + c_k v_k = 0, \quad c_1,\ldots,c_k\in\mathbb{R}.$$ For $i\ne j$ we have $A_iA_j=0$; in particular, $A_iv_j=0$. Now, for each $i=1,\ldots,n$, from $$0 = A_i(c_1 v_1 + \ldots + c_k v_k) = \sum_{j=1}^k c_j(A_i v_j) = c_i (A_iv_i)$$ we can see that $c_i=0$. Hence, $c_1=\ldots=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_iA_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 & \ldots & A_k \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ \vdots \\ A_k \end{pmatrix} = \begin{pmatrix} A_1^2 & 0 & \ldots & 0 \\ 0 & A_2^2 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \ldots & 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$.

Solution 2. 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\ldots\supset X_k$. Notice also that $U_i\subset X_{i-1}$ because $U_i\subset K_j$ for every $j\lt 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 > \ldots > \dim X_k\ge 0$$ we get $k\ge n$.