0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.