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 :
has full row rank. it is the Kalman rank condition to test controllability. but what is the computational complexity?