Probability estimates for reachability of linear systems defined over finite fields

Uwe Helmke; Jens  Jordan; Julia  Lieb

doi:10.3934/amc.2016.10.63

Article Contents

2016, Volume 10, Issue 1: 63-78. Doi: 10.3934/amc.2016.10.63

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

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

Received: November 30, 2014

Revised: June 30, 2015

Published: January 2016

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 93B05, 93C05, 11T06; Secondary: 93B25, 93C55.

Citation:

Related Papers

Cited by

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.