Here is an example I encountered in my research: 

Let $A=(a_{n, m})$ be an $N\times M$ matrix such that for all $n$ there exists $k=k(n)$ such that $a_{n,m}=0$ if $m\neq k, k+1$, that is in every row we have at most two non-zero numbers and they go one after the other, and assume that we want to know if $A$ is injective, that is whether there exists a non-zero vector v such that $Av=0$. Then it is not terribly difficult to convince yourself that this can be done by only looking at which elements of the matrix $A$ are non-zero and which pairs of rows of $A$ are linearly independent and do some fairly simple combinatorics depending on this.

However, if we say that $a_{n, m}=0$ if $m\neq k, k+1, k+2$, that is if we allow for 3 consecutive non-zero elements, then the problem becomes at least as hard as the one of determining whether the Jacobi matrix is non-singular which is a subject of dozens of books and hundredths of papers, and in particular is a very difficult problem to approach analytically.