How can we determine easily that the following transition matrix is irreducible? Let $n\in\Bbb N$ be arbitrary, and define the matrix $A=(a_{ij})_{i,j=0}^n$ via:
$$a_{ij}=\begin{cases}0&|i-j|\neq1\\\frac{i}{n}&j=i-1\\\frac{n-i}{n}&j=i+1\end{cases}$$
Which represents the transition matrix of the Markov shift system where $n$ balls numbered $1\to n$ are distributed across two urns, and at every time step an integer value $1\le k\le n$ is chosen equiprobably, and the ball numbered $k$ is moved from the urn it's in to the other, and the state is the number of balls in the first urn.
The text I was following claimed without proof that $A$ is always irreducible, but I don't know how one shows that. Computing $\sum_{k=1}^nA^k$  in general is not easy, nor is trying to reason about the general graph represented by $A$. Indeed, I might try to show it is not able to be permuted into a block-triangular matrix, but I believe it is defacto block-triangular - for $n=4$:
$$A=\begin{bmatrix}0&1&0&0&0\\1/4&0&3/4&0&0\\0&1/4&0&3/4&0\\0&0&1/4&0&3/4\\0&0&0&1&0\end{bmatrix}$$
Is there not a block triangle formed by the four zeroes in the bottom left-hand corner? I feel like I am overlooking something trivial.
Many thanks for any clarification.
 A: You don't need to actually compute $A^k$ to show that $(A^k)_{ij}>0$.
Choose two arbitrary states $i$ and $j$. We want to show there exists $k$ such that $(A^k)_{ij}>0$, that is, we can transition from state $i$ to state $j$ in $k$ steps.
Thinking heuristically for a moment, we know the number of balls in the first urn increases or decreases by exactly one at every step. So if $i>j$ we can transition from state $i$ to state $j$ by removing balls from the first urn, and if $i<j$ we can transition from state $i$ to state $j$ by adding balls to the first urn. If $i=j$ we can add and remove or remove and add a ball to the first urn.
Formalizing the argument above, we have four cases:

*

*$i>j$: Let $k=i-j$, so $j=i-k$. Then,
$$(A^k)_{ij} \geq a_{i,i-1} a_{i-1,i-2} \cdots a_{i-k+1,i-k}=\left(\frac{i}{n}\right)\left(\frac{i-1}{n}\right)\cdots \left(\frac{i-k+1}{n}\right)$$
Note that all of the terms in this product are strictly positive, as $i-k+1=j+1 \geq 1$.

*$i<j$: I'll leave you to argue this similarly to the first case.

*$i=j=0$: In this case we can't remove a ball from the first urn, so we'll have to add one first. That is, we just need to show $a_{0,1} a_{1,0}>0$.

*$i=j=n$: In this case we can't add a ball, so first we remove. That is, we need to show $a_{n,n-1}a_{n-1,n}>0$.

Finally, note that your matrix is incorrect. It should be:
$$A=\begin{bmatrix}0&1&0&0&0\\1/4&0&3/4&0&0\\0&1/2&0&1/2&0\\0&0&3/4&0&1/4\\0&0&0&1&0\end{bmatrix}.$$
A: You can determine whether the matrix $\sum_{k=1}^n A^k$ is positive for some $n$ without using numerical arithmetic: just use Boolean arithmetic. In other words, first replace each positive entry in $A$ by a $1$, and then compute $S_n = \sum_{k=1}^n A^k$ using the Boolean arithmetic formulas
\begin{align*}
0+0=0, &\qquad 0+1=1+0=1+1=1 \\
0 \cdot 0 = 0 \cdot 1 = 1 \cdot 0 = 0, &\qquad 1 \cdot 1 = 1
\end{align*}
As you compute $S_1,S_2,S_3,\ldots$, there must be some value of $n$ such that $S_n=S_{n+1}$. When you reach that value, stop. If $S_n$ is all $1$'s then $A$ is irreducible. Otherwise, it's not.
A: The best for me is to look at irreducibility of state-space which means that any state be reached from any other state with positive probability.
Just build the graph $G=(V,E)$ associated with the matrix $A$ such that $V=\{1,\ldots,5\}$ and $(i,j)\in E$ if and only $a_{ij}\ne0$. Then, show that any state can be reached from any other states in maximum 4 steps on that graph. This means that the state-space is irreducible and that $\sum_{i=1}^4A^i$ is positive.
Interestingly, this shows that the irreducibility property is a structural property of the Markov chain and does not depend on the actual values of the conditional probabilities. It only depends on the pattern of the non-zero entries.
This is somehow connected to the answer by Lee Mosher which also consider the sign pattern through entries which are either 0 or 1, an approach well-known in the analysis of sign matrices.
