SCIENCE CHINA Information Sciences, Volume 62 , Issue 1 : 012205(2019) https://doi.org/10.1007/s11432-017-9311-x

On strong structural controllability and observability of linear time-varying systems: a constructive method

More info
  • ReceivedJul 30, 2017
  • AcceptedNov 6, 2017
  • PublishedNov 12, 2018



This work was supported by National Natural Science Foundation of China (Grant Nos. 61233004, 61590924, 61521063).


[1] Kalman R E, Ho Y C, Narenda K S. Controllability of linear dynamical systems. Contrib Diff Eqs, 1963, 1: 189--213. Google Scholar

[2] Rosenbrock H H. State-Space and Multivariable Theory. New York: Wiley, 1970. Google Scholar

[3] Hautus M L J. Controllability and observability conditions of linear autonomous systems. Nederl Akad Wet Proc Ser A, 1969, 72: 443--448. Google Scholar

[4] Ching-Tai Lin . Structural controllability. IEEE Trans Automat Contr, 1974, 19: 201-208 CrossRef Google Scholar

[5] Shields R, Pearson J. Structural controllability of multiinput linear systems. IEEE Trans Automat Contr, 1976, 21: 203-212 CrossRef Google Scholar

[6] Mayeda H. On structural controllability theorem. IEEE Trans Automat Contr, 1981, 26: 795-798 CrossRef Google Scholar

[7] Wang L, Jiang F C, Xie G M. Controllability of multi-agent systems based on agreement protocols. Sci China Ser F-Inf Sci, 2009, 52: 2074-2088 CrossRef Google Scholar

[8] Guan Y, Wang L. Structural controllability of multi-agent systems with absolute protocol under fixed and switching topologies. Sci China Inf Sci, 2017, 60: 092203 CrossRef Google Scholar

[9] Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks. Nature, 2011, 473: 167-173 CrossRef PubMed ADS Google Scholar

[10] Mu J, Li S, Wu J. On the structural controllability of distributed systems with local structure changes. Sci China Inf Sci, 2018, 61: 052201 CrossRef Google Scholar

[11] Mayeda H, Yamada T. Strong Structural Controllability. SIAM J Control Optim, 1979, 17: 123-138 CrossRef Google Scholar

[12] Hartung C, Reissig G, Svaricek F. Characterization of strong structural controllability of uncertain linear time-varying discrete-time systems. In: Proceedings of the 51st IEEE Conference on Decision and Control, Maui, 2012. 2189--2194. Google Scholar

[13] Hartung C, Reissig G, Svaricek F. Sufficient conditions for strong structural controllability of uncertain linear time-varying systems. In: Proceedings of American Control Conference, Washington, 2013. 5895--5900. Google Scholar

[14] Hartung C, Reissig G, Svaricek F. Necessary conditions for structural and strong structural controllability of linear time-varying systems. In: Proceedings of European Control Conference, Zurich, 2013. 1335--1340. Google Scholar

[15] Reissig G, Hartung C, Svaricek F. Strong Structural Controllability and Observability of Linear Time-Varying Systems. IEEE Trans Automat Contr, 2014, 59: 3087-3092 CrossRef Google Scholar

[16] Rugh W J. Linear System Theory. 2nd ed. Englewood Cliffs: Prentice Hall, 1996. Google Scholar

[17] Kalman R E. On the general theory of control systems. IEEE Trans Automat Contr, 1959, 4: 481--492. Google Scholar

[18] Sontag E D. Mathematical Control Theory. 2nd ed. New York: Springer, 1991. Google Scholar

[19] Liu X, Lin H, Chen B M. Graph-theoretic characterisations of structural controllability for multi-agent system with switching topology. Int J Control, 2013, 86: 222-231 CrossRef Google Scholar

  • Figure 1

    Run time of Algorithm 1to verify strong structurally controllable property which depends on $\nu$ and $n$ for randomly chosen structural matrices $(\bar~A,~\bar~B)~\in~\{~0,~*~\}^{n~\times~(n+m)}$ such that each LTV system $(\bar~A,~\bar~B)$ is strong structurally controllable. $\nu$ denotes the number of non-zero entries in $(\bar~A,~\bar~B)$. The underlying implementation of Algorithm 1was executed in C programming language on a Intel Core i3-2120 (3.3 GHz). (a) $n~=~1000,~m~=~250$; (b) $m~=~500,~\nu~=~50000$.


    Algorithm 1 SSC checking for structural LTV system









    for $x~\in~U~\cup~V$


    end for


    while $~\tilde~U~\neq~\emptyset$ do

    $x~=~$ Null,

    for each $~w~\in~W$

    if $~|~\tilde~N(w)~|~=~1$ with $\tilde~N(w)~=~u_{i_t}$ then




    end if

    end for

    if $x~=~\emptyset$ then

    Return “False",


    end if


    for each $z\in~\tilde~N(y)$


    end for




    Delete $~\tilde~N(y)$,

    end while

    if $\tilde~U~=~\emptyset$ then

    Return “True",

    end if