If the characteristic polynomial factors (over $\mathbb{Q}$) into polynomials of degrees $d_1,d_2,\ldots,d_r$, where $d_1$ is the degree of the polynomial that the largest eigenvalue is a root of, then the controllability matrix $\begin{pmatrix}\mathbf{b} & \mathbf{Ab} & \mathbf{A}^2\mathbf{b} & \ldots & \mathbf{A}^{n-1}\mathbf{b}\end{pmatrix}$ with respect to any nonzero $0$-$1$ indicator vector $\mathbf{b}$ has rank $d_1+\sum_{i=2}^r c_id_i$, where $c_i=0$ or $1$ for all $2\leq i\leq r$.
In particular, if the characteristic polynomial is irreducible over $\mathbb{Q}$, then the controllability matrix is invertible for all nonzero $\mathbf{b}$.