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

Hint: Every $A_i$ has a column $v_i$ with $A_iv_i\ne0$. Prove that these vectors are linearly independent.

  Solution