Question 96
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 $\{x_{i}\}_{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_{ij}$ 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$.
- $x_{i} \in S$ for all $i$,
- $a_{x_{k} x_{k+1}}=1$ for all $k$, where $a_{ij}$ 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$.