Probability estimates for reachability of linear systems defined over finite fields

Previous Article
Yet another variation on minimal linear codes
AMC Home
This Issue
Next Article
On skew polynomial codes and lattices from quotients of cyclic division algebras

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

Abstract
Related Papers

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.
[2]	P. A. Fuhrmann, On controllability and observability of systems connected in parallel,, IEEE Trans. Circ. Syst., 22 (1975).
[3]	P. A. Fuhrmann and U. Helmke, The Mathematics of Networks of Linear Systems,, Springer, (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. 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. 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, (2008). doi: 10.1017/CBO9780511754623.
[8]	S. Höst, Woven convolutional codes I: Encoder properties,, IEEE Trans. Inf. Theory, 48 (2002), 149. 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. 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), 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, ().
[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.
[14]	J. Rosenthal and E. V. York, BCH Convolutional Codes,, IEEE Trans. Inf. Theory, 45 (1999), 1833. 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. 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. 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).
[3]	P. A. Fuhrmann and U. Helmke, The Mathematics of Networks of Linear Systems,, Springer, (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. 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. 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, (2008). doi: 10.1017/CBO9780511754623.
[8]	S. Höst, Woven convolutional codes I: Encoder properties,, IEEE Trans. Inf. Theory, 48 (2002), 149. 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. 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), 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, ().
[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.
[14]	J. Rosenthal and E. V. York, BCH Convolutional Codes,, IEEE Trans. Inf. Theory, 45 (1999), 1833. 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. doi: 10.1109/TAC.2012.2204155.

[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]	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
[6]	Osama Khalil. Geodesic planes in geometrically finite manifolds. Discrete & Continuous Dynamical Systems - A, 2019, 39 (2) : 881-903. doi: 10.3934/dcds.2019037
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	Valentin Ovsienko, MichaeL Shapiro. Cluster algebras with Grassmann variables. Electronic Research Announcements, 2019, 26: 1-15. doi: 10.3934/era.2019.26.001
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	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
[19]	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
[20]	David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35

2017 Impact Factor: 0.564

American Institute of Mathematical Sciences