We define the matrix $W_n = (w_{i,j})$ in $\mathcal{M}_n(\mathbb{R})$ by $w_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } i = n \text{ and } j \in \{1,2\} \\ 0 & \text{in all other cases} \end{cases}$ Show that for all $i, j$ in $\llbracket 1, n \rrbracket$, with $i \neq j$, there exists in $W_n$ at least one path with origin $i$, endpoint $j$, and length less than or equal to $n-1$. You may treat successively the two cases $1 \notin \{i,j\}$ and $1 \in \{i,j\}$. Deduce that the matrix $W_n^{n^2-2n+2}$ is strictly positive and conclude.
We define the matrix $W_n = (w_{i,j})$ in $\mathcal{M}_n(\mathbb{R})$ by $w_{i,j} = \begin{cases} 1 & \text{if } 1 \leqslant i < n \text{ and } j = i+1 \\ 1 & \text{if } i = n \text{ and } j \in \{1,2\} \\ 0 & \text{in all other cases} \end{cases}$
Show that for all $i, j$ in $\llbracket 1, n \rrbracket$, with $i \neq j$, there exists in $W_n$ at least one path with origin $i$, endpoint $j$, and length less than or equal to $n-1$.
You may treat successively the two cases $1 \notin \{i,j\}$ and $1 \in \{i,j\}$.
Deduce that the matrix $W_n^{n^2-2n+2}$ is strictly positive and conclude.