How to prove that a banded matrix is irreducible? I want to proof that for a certain $n\in\mathbb{N}$ a banded matrix, $A\in\mathbb{R^{n\times n}}$, with elements $\frac{1}{h^{2}}$ on the $+1$ and $-1$ diagonals and $1+2/h^{2}$ on the main diagonal is irreducibe. Therefore i have to proof that there does not exist a permutation matrix $P$, such that $PAP^{T}$ is block upper triangular. I do not know how to begin this proof and cannot find any clear conditions for banded matrices, which imply irreducibility.

**Hint:** Applying the permutation similarity $A \mapsto PAP^T$ amounts to moving the $i,j$ entry of $A$ to the $\pi(i),\pi(j)$ position for some permutation $\pi:\\{1,\dots,n\\} \to \\{1,\dots,n\\}$. Note that the $(i,j)$ entry is above the diagonal if and only if $j\geq i$.

Suppose that $\pi$ is a permutation such that the corresponding $PAP^T$ is upper triangular. Since $a_{i,i+1}$ is non-zero for $i=1,\dots,n-1$, we must have $\pi(i+1) \geq \pi(i)$ for $i = 1,\dots,n$. On the other hand, since $a_{i-1,i}$ is non-zero for $i = 2,\dots,n$, we must have $\pi(i-1) \leq \pi(i)$ for $i = 2,\dots,n$.

Argue that these conditions cannot hold simultaneously.