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]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Joseph H. Silverman. Local-global aspects of (hyper)elliptic curves over (in)finite fields. Advances in Mathematics of Communications, 2010, 4 (2) : 101-114. doi: 10.3934/amc.2010.4.101
[17]

Zilong Wang, Guang Gong. Correlation of binary sequence families derived from the multiplicative characters of finite fields. Advances in Mathematics of Communications, 2013, 7 (4) : 475-484. doi: 10.3934/amc.2013.7.475
[18]

Liren Lin, Hongwei Liu, Bocong Chen. Existence conditions for self-orthogonal negacyclic codes over finite fields. Advances in Mathematics of Communications, 2015, 9 (1) : 1-7. doi: 10.3934/amc.2015.9.1
[19]

Konstantinos Drakakis, Rod Gow, Scott Rickard. Parity properties of Costas arrays defined via finite fields. Advances in Mathematics of Communications, 2007, 1 (3) : 321-330. doi: 10.3934/amc.2007.1.321
[20]

Vincent Naudot, Jiazhong Yang. Finite smooth normal forms and integrability of local families of vector fields. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 667-682. doi: 10.3934/dcdss.2010.3.667

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences