HMIC 2017 Problem 2

Let $S=\{1,2 \ldots, n\}$ for some positive integer $n$, and let $A$ be an $n$-by- $n$ matrix having as entries only ones and zeros. Define an infinite sequence $\left\{x_{i}\right\}_{i \geq 0}$ to be strange if:

• $x_{i} \in S$ for all $i$,
• $a_{x_{k} x_{k+1}}=1$ for all $k$, where $a_{i j}$ denotes the element in the $i^{\text {th }}$ row and $j^{\text {th }}$ column of $A$.

Prove that the set of strange sequences is empty if and only if $A$ is nilpotent, i.e. $A^{m}=0$ for some integer $m$.