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-699. doi: 10.1016/j.laa.2007.03.017.

[2]

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

[3]

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

[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-828. doi: 10.1016/j.jcta.2010.11.005.

[5]

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

[6]

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

[7]

T. Ho and D. S. Lun, Network Coding: An Introduction, Cambridge Univ. Press, New York, 2008. doi: 10.1017/CBO9780511754623.

[8]

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

[9]

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

[10]

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

[11]

J. Milnor and J. Stasheff, Characteristic Classes, Princeton Univ. Press, 1974.

[12]

J. A. De Reyna and R. Heyman, Counting tuples restricted by coprimality conditions, preprint, arXiv:1403.2769v1

[13]

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

[14]

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

[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-73. doi: 10.1109/TAC.2012.2204155.

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-699. doi: 10.1016/j.laa.2007.03.017.

[2]

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

[3]

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

[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-828. doi: 10.1016/j.jcta.2010.11.005.

[5]

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

[6]

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

[7]

T. Ho and D. S. Lun, Network Coding: An Introduction, Cambridge Univ. Press, New York, 2008. doi: 10.1017/CBO9780511754623.

[8]

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

[9]

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

[10]

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

[11]

J. Milnor and J. Stasheff, Characteristic Classes, Princeton Univ. Press, 1974.

[12]

J. A. De Reyna and R. Heyman, Counting tuples restricted by coprimality conditions, preprint, arXiv:1403.2769v1

[13]

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

[14]

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

[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-73. doi: 10.1109/TAC.2012.2204155.

[1]

Rolando Mosquera, Aziz Hamdouni, Abdallah El Hamidi, Cyrille Allery. POD basis interpolation via Inverse Distance Weighting on Grassmann manifolds. Discrete and Continuous Dynamical Systems - S, 2019, 12 (6) : 1743-1759. doi: 10.3934/dcdss.2019115
[2]

Igor E. Shparlinski. On some dynamical systems in finite fields and residue rings. Discrete and Continuous Dynamical Systems, 2007, 17 (4) : 901-917. doi: 10.3934/dcds.2007.17.901
[3]

Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[4]

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
[5]

Mikhail Gusev. On reachability analysis for nonlinear control systems with state constraints. Conference Publications, 2015, 2015 (special) : 579-587. doi: 10.3934/proc.2015.0579
[6]

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

Lih-Chung Wang, Tzer-jen Wei, Jian-Ming Shih, Yuh-Hua Hu, Chih-Cheng Hsieh. An algorithm for solving over-determined multivariate quadratic systems over finite fields. Advances in Mathematics of Communications, 2022  doi: 10.3934/amc.2022001
[8]

Felix X.-F. Ye, Hong Qian. Stochastic dynamics Ⅱ: Finite random dynamical systems, linear representation, and entropy production. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4341-4366. doi: 10.3934/dcdsb.2019122
[9]

Florian Luca, Igor E. Shparlinski. On finite fields for pairing based cryptography. Advances in Mathematics of Communications, 2007, 1 (3) : 281-286. doi: 10.3934/amc.2007.1.281
[10]

Valentin Ovsienko, MichaeL Shapiro. Cluster algebras with Grassmann variables. Electronic Research Announcements, 2019, 26: 1-15. doi: 10.3934/era.2019.26.001
[11]

Osama Khalil. Geodesic planes in geometrically finite manifolds. Discrete and Continuous Dynamical Systems, 2019, 39 (2) : 881-903. doi: 10.3934/dcds.2019037
[12]

Stefania Fanali, Massimo Giulietti, Irene Platoni. On maximal curves over finite fields of small order. Advances in Mathematics of Communications, 2012, 6 (1) : 107-120. doi: 10.3934/amc.2012.6.107
[13]

Jean-François Biasse, Michael J. Jacobson, Jr.. Smoothness testing of polynomials over finite fields. Advances in Mathematics of Communications, 2014, 8 (4) : 459-477. doi: 10.3934/amc.2014.8.459
[14]

Shengtian Yang, Thomas Honold. Good random matrices over finite fields. Advances in Mathematics of Communications, 2012, 6 (2) : 203-227. doi: 10.3934/amc.2012.6.203
[15]

Francis N. Castro, Carlos Corrada-Bravo, Natalia Pacheco-Tallaj, Ivelisse Rubio. Explicit formulas for monomial involutions over finite fields. Advances in Mathematics of Communications, 2017, 11 (2) : 301-306. doi: 10.3934/amc.2017022
[16]

Robert Granger, Thorsten Kleinjung, Jens Zumbrägel. Indiscreet logarithms in finite fields of small characteristic. Advances in Mathematics of Communications, 2018, 12 (2) : 263-286. doi: 10.3934/amc.2018017
[17]

Ghobad Barmalzan, Ali Akbar Hosseinzadeh, Narayanaswamy Balakrishnan. Stochastic comparisons of series-parallel and parallel-series systems with dependence between components and also of subsystems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021101
[18]

Ale Jan Homburg. Heteroclinic bifurcations of $\Omega$-stable vector fields on 3-manifolds. Discrete and Continuous Dynamical Systems, 1998, 4 (3) : 559-580. doi: 10.3934/dcds.1998.4.559
[19]

Paolo Maria Mariano. Line defect evolution in finite-dimensional manifolds. Discrete and Continuous Dynamical Systems - B, 2012, 17 (2) : 575-596. doi: 10.3934/dcdsb.2012.17.575
[20]

Osama Khalil. Geodesic planes in geometrically finite manifolds-corrigendum. Discrete and Continuous Dynamical Systems, 2022, 42 (5) : 2101-2102. doi: 10.3934/dcds.2021185

2021 Impact Factor: 1.015

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy