What is the complexity order of Kalman rank condition?

Question

Does computing the Kalman rank condition of an integer matrix have complexity polynomial in the size of the input? if yes what is the order of complexity?

For a discrete-time linear state-space system, the state equation is

$$ x(k+1) = Ax(k) + Bu(k) $$

where $A$ is an $n\times n$ matrix and $B$ is $n\times m$ matrix, the test of controllability is that the $n\times nm$ matrix $C$ which is in the blow :

\begin{bmatrix}B&AB&A^{2}B&\cdots &A^{n-1}B\end{bmatrix}

has full row rank. it is the Kalman rank condition to test controllability. but what is the computational complexity?

Answer 1

For the calculation of $AB,\cdots,A^{n-1}B$, the complexity is $O(n.n^2m)$. For the calculation of the rank, the complexity is $O(n^2.nm)$.

Finally , the total complexity is $O(n^3m)$.