Skip to main content
2 of 2
added 471 characters in body

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$. (Here, $\mathbf{A}$ is the adjacency matrix.)

In particular, if the characteristic polynomial is irreducible over $\mathbb{Q}$, then the controllability matrix is invertible for all nonzero $\mathbf{b}$.

Also note that for regular graphs, one of the factors will be $(x-\rho)$ where $\rho$ is the common degree of the graph, and this $\rho$ will be the largest eigenvalue of $\mathbf{A}$. Hence the above result would state that the rank of any controllability matrix as defined previously is $1+\sum_{i=2}^r c_id_i$ where $c_i=0$ or $1$ for all $2\leq i\leq r$. In particular for the case when $\mathbf{b}$ is the vector of all ones, it is well-known that $c_2=c_3=\cdots=c_r=0$ and the rank of the controllability matrix will be $1$.