American Institute of Mathematical Sciences

Advanced
February  2016, 10(1): 63-78. doi: 10.3934/amc.2016.10.63

Probability estimates for reachability of linear systems defined over finite fields

Uwe Helmke 1, , Jens Jordan 2, and  Julia Lieb 2,

1. 

Institut für Mathematik; Lehrstuhl für Mathematik II, Universität Würzburg, Am Hubland, 97074 Würzburg,
2. 

Institute of Mathematics, University of Würzburg, 97074 Würzburg, Germany, Germany

Received  December 2014 Revised  July 2015 Published  March 2016

This paper deals with the probability that random linear systems defined over a finite field are reachable. Explicit formulas are derived for the probabilities that a linear input-state system is reachable, that the reachability matrix has a prescribed rank, as well as for the number of cyclic vectors of a cyclic matrix. We also estimate the probability that the parallel connection of finitely many single-input systems is reachable. These results may be viewed as a first step to calculate the probability that a network of linear systems is reachable.
Keywords: Linear systems, reachability, finite fields, parallel connection., Grassmann manifolds.
Mathematics Subject Classification: Primary: 93B05, 93C05, 11T06; Secondary: 93B25, 93C5.
Citation: Uwe Helmke, Jens Jordan, Julia Lieb. Probability estimates for reachability of linear systems defined over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 63-78. doi: 10.3934/amc.2016.10.63
References:
[1]

J.-J. Climent, V. Herranz and C. Perea, A first approximation of concatenated convolutional codes from linear systems theory viewpoint,, Linear Alg. Appl., 425 (2007), 673.  doi: 10.1016/j.laa.2007.03.017.  Google Scholar

[2]

P. A. Fuhrmann, On controllability and observability of systems connected in parallel,, IEEE Trans. Circ. Syst., 22 (1975).   Google Scholar

[3]

P. A. Fuhrmann and U. Helmke, The Mathematics of Networks of Linear Systems,, Springer, (2015).  doi: 10.1007/978-3-319-16646-9.  Google Scholar

[4]

M. Garcia-Armas, S. R. Ghorpade and S. Ram, Relatively prime polynomials and nonsingular Hankel matrices over finite fields,, J. Combin. Theory Ser. A, 118 (2011), 819.  doi: 10.1016/j.jcta.2010.11.005.  Google Scholar

[5]

U. Helmke, Topology of the moduli space for reachable linear dynamical systems: The complex case,, Math. Syst. Theory, 19 (1986), 155.  doi: 10.1007/BF01704912.  Google Scholar

[6]

U. Helmke, The cohomology of moduli spaces for linear dynamical systems,, Regensburger Math. Schriften, 24 (1993).   Google Scholar

[7]

T. Ho and D. S. Lun, Network Coding: An Introduction,, Cambridge Univ. Press, (2008).  doi: 10.1017/CBO9780511754623.  Google Scholar

[8]

S. Höst, Woven convolutional codes I: Encoder properties,, IEEE Trans. Inf. Theory, 48 (2002), 149.  doi: 10.1109/18.971745.  Google Scholar

[9]

A. S. Jarrah, R. Laubenbacher, B. Stigler and M. Stillman, Reverse-engineering of polynomial dynamical systems,, Adv. Appl. Math., 39 (2007), 477.  doi: 10.1016/j.aam.2006.08.004.  Google Scholar

[10]

M. Kociecky and K. M. Przyluski, On the number of controllable linear systems over a finite field,, Linear Alg. Appl., 122-124 (1989), 122.  doi: 10.1016/0024-3795(89)90649-6.  Google Scholar

[11]

J. Milnor and J. Stasheff, Characteristic Classes,, Princeton Univ. Press, (1974).   Google Scholar

[12]

J. A. De Reyna and R. Heyman, Counting tuples restricted by coprimality conditions,, preprint, ().   Google Scholar

[13]

J. Rosenthal, J. M. Schumacher and E. V. York, On behaviours and convolutional codes,, IEEE Trans. Inf. Theory, 42 (1996), 1881.  doi: 10.1109/18.556682.  Google Scholar

[14]

J. Rosenthal and E. V. York, BCH Convolutional Codes,, IEEE Trans. Inf. Theory, 45 (1999), 1833.  doi: 10.1109/18.782104.  Google Scholar

[15]

S. Sundaram and C. Hadjicostis, Structural controllability and observability of linear systems over finite fields with applications to mult-agent systems,, IEEE Trans. Autom. Control, 58 (2013), 60.  doi: 10.1109/TAC.2012.2204155.  Google Scholar

show all references

References:
[1]

J.-J. Climent, V. Herranz and C. Perea, A first approximation of concatenated convolutional codes from linear systems theory viewpoint,, Linear Alg. Appl., 425 (2007), 673.  doi: 10.1016/j.laa.2007.03.017.  Google Scholar

[2]

P. A. Fuhrmann, On controllability and observability of systems connected in parallel,, IEEE Trans. Circ. Syst., 22 (1975).   Google Scholar

[3]

P. A. Fuhrmann and U. Helmke, The Mathematics of Networks of Linear Systems,, Springer, (2015).  doi: 10.1007/978-3-319-16646-9.  Google Scholar

[4]

M. Garcia-Armas, S. R. Ghorpade and S. Ram, Relatively prime polynomials and nonsingular Hankel matrices over finite fields,, J. Combin. Theory Ser. A, 118 (2011), 819.  doi: 10.1016/j.jcta.2010.11.005.  Google Scholar

[5]

U. Helmke, Topology of the moduli space for reachable linear dynamical systems: The complex case,, Math. Syst. Theory, 19 (1986), 155.  doi: 10.1007/BF01704912.  Google Scholar

[6]

U. Helmke, The cohomology of moduli spaces for linear dynamical systems,, Regensburger Math. Schriften, 24 (1993).   Google Scholar

[7]

T. Ho and D. S. Lun, Network Coding: An Introduction,, Cambridge Univ. Press, (2008).  doi: 10.1017/CBO9780511754623.  Google Scholar

[8]

S. Höst, Woven convolutional codes I: Encoder properties,, IEEE Trans. Inf. Theory, 48 (2002), 149.  doi: 10.1109/18.971745.  Google Scholar

[9]

A. S. Jarrah, R. Laubenbacher, B. Stigler and M. Stillman, Reverse-engineering of polynomial dynamical systems,, Adv. Appl. Math., 39 (2007), 477.  doi: 10.1016/j.aam.2006.08.004.  Google Scholar

[10]

M. Kociecky and K. M. Przyluski, On the number of controllable linear systems over a finite field,, Linear Alg. Appl., 122-124 (1989), 122.  doi: 10.1016/0024-3795(89)90649-6.  Google Scholar

[11]

J. Milnor and J. Stasheff, Characteristic Classes,, Princeton Univ. Press, (1974).   Google Scholar

[12]

J. A. De Reyna and R. Heyman, Counting tuples restricted by coprimality conditions,, preprint, ().   Google Scholar

[13]

J. Rosenthal, J. M. Schumacher and E. V. York, On behaviours and convolutional codes,, IEEE Trans. Inf. Theory, 42 (1996), 1881.  doi: 10.1109/18.556682.  Google Scholar

[14]

J. Rosenthal and E. V. York, BCH Convolutional Codes,, IEEE Trans. Inf. Theory, 45 (1999), 1833.  doi: 10.1109/18.782104.  Google Scholar

[15]

S. Sundaram and C. Hadjicostis, Structural controllability and observability of linear systems over finite fields with applications to mult-agent systems,, IEEE Trans. Autom. Control, 58 (2013), 60.  doi: 10.1109/TAC.2012.2204155.  Google Scholar

[1]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[2]

Simone Fiori. Error-based control systems on Riemannian state manifolds: Properties of the principal pushforward map associated to parallel transport. Mathematical Control & Related Fields, 2021, 11 (1) : 143-167. doi: 10.3934/mcrf.2020031
[3]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004
[4]

Roderick S. C. Wong, H. Y. Zhang. On the connection formulas of the third Painlevé transcendent. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 541-560. doi: 10.3934/dcds.2009.23.541
[5]

Duy Phan, Lassi Paunonen. Finite-dimensional controllers for robust regulation of boundary control systems. Mathematical Control & Related Fields, 2021, 11 (1) : 95-117. doi: 10.3934/mcrf.2020029
[6]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[7]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[8]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020174
[9]

Jonathan J. Wylie, Robert M. Miura, Huaxiong Huang. Systems of coupled diffusion equations with degenerate nonlinear source terms: Linear stability and traveling waves. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 561-569. doi: 10.3934/dcds.2009.23.561
[10]

Andy Hammerlindl, Jana Rodriguez Hertz, Raúl Ures. Ergodicity and partial hyperbolicity on Seifert manifolds. Journal of Modern Dynamics, 2020, 0: 331-348. doi: 10.3934/jmd.2020012
[11]

Jianfeng Huang, Haihua Liang. Limit cycles of planar system defined by the sum of two quasi-homogeneous vector fields. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 861-873. doi: 10.3934/dcdsb.2020145
[12]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020031
[13]

Harrison Bray. Ergodicity of Bowen–Margulis measure for the Benoist 3-manifolds. Journal of Modern Dynamics, 2020, 16: 305-329. doi: 10.3934/jmd.2020011
[14]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[15]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453
[16]

Philippe G. Lefloch, Cristinel Mardare, Sorin Mardare. Isometric immersions into the Minkowski spacetime for Lorentzian manifolds with limited regularity. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 341-365. doi: 10.3934/dcds.2009.23.341
[17]

Paul A. Glendinning, David J. W. Simpson. A constructive approach to robust chaos using invariant manifolds and expanding cones. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020409
[18]

Bixiang Wang. Mean-square random invariant manifolds for stochastic differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1449-1468. doi: 10.3934/dcds.2020324
[19]

Lin Shi, Dingshi Li, Kening Lu. Limiting behavior of unstable manifolds for spdes in varying phase spaces. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021020
[20]

Giuseppe Capobianco, Tom Winandy, Simon R. Eugster. The principle of virtual work and Hamilton's principle on Galilean manifolds. Journal of Geometric Mechanics, 2021  doi: 10.3934/jgm.2021002

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (75)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences