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

Probability estimates for reachability of linear systems defined over finite fields

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

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

[2]

Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233

[3]

Arseny Egorov. Morse coding for a Fuchsian group of finite covolume. Journal of Modern Dynamics, 2009, 3 (4) : 637-646. doi: 10.3934/jmd.2009.3.637

[4]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141

[5]

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

[6]

Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20.

[7]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265

[8]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[9]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[10]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[11]

Wenmin Gong, Guangcun Lu. On coupled Dirac systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (8) : 4329-4346. doi: 10.3934/dcds.2017185

[12]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[13]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[14]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[15]

Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810

[16]

Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161

[17]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329

[18]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[19]

Graziano Crasta, Philippe G. LeFloch. Existence result for a class of nonconservative and nonstrictly hyperbolic systems. Communications on Pure & Applied Analysis, 2002, 1 (4) : 513-530. doi: 10.3934/cpaa.2002.1.513

[20]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

2019 Impact Factor: 0.734

Metrics

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

Other articles
by authors

[Back to Top]