American Institute of Mathematical Sciences

Advanced
May  2012, 6(2): 203-227. doi: 10.3934/amc.2012.6.203

Good random matrices over finite fields

Shengtian Yang 1, and  Thomas Honold 2,

1. 

Zhengyuan Xiaoqu 10-2-101, Fengtan Road, Hangzhou 310011, China
2. 

Department of Information Science and Electronics Engineering, Zhejiang University, 38 Zheda Road, Hangzhou 310027, China

Received  May 2011 Revised  July 2011 Published  April 2012

The random matrix uniformly distributed over the set of all $m$-by-$n$ matrices over a finite field plays an important role in many branches of information theory. In this paper a generalization of this random matrix, called $k$-good random matrices, is studied. It is shown that a $k$-good random $m$-by-$n$ matrix with a distribution of minimum support size is uniformly distributed over a maximum-rank-distance (MRD) code of minimum rank distance min{$m,n$}$-k+1$, and vice versa. Further examples of $k$-good random matrices are derived from homogeneous weights on matrix modules. Several applications of $k$-good random matrices are given, establishing links with some well-known combinatorial problems. Finally, the related combinatorial concept of a $k$-dense set of $m$-by-$n$ matrices is studied, identifying such sets as blocking sets with respect to $(m-k)$-dimensional flats in a certain $m$-by-$n$ matrix geometry and determining their minimum size in special cases.
Keywords: intersecting code, dense set of matrices, MRD code, affine geometry of matrices, homogeneous weight, maximum-rank-distance code, blocking set., Linear code, random matrix.
Mathematics Subject Classification: 94B05, 15B52, 60B20, 15B33, 51E2.
Citation: 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
References:
[1]

Cambridge University Press, 1998.  Google Scholar

[2]

S. Ball, The polynomial method in Galois geometries,, in, (): 103.   Google Scholar

[3]

IEEE Trans. Inform. Theory, 48 (2002), 2568-2573. doi: 10.1109/TIT.2002.800480.  Google Scholar

[4]

Nova Science Publishers, 2011. Google Scholar

[5]

A. Blokhuis, P. Sziklai and T. Szőnyi, Blocking sets in projective spaces,, in, (): 61.   Google Scholar

[6]

IEEE Trans. Comput., 29 (1980), 665-668. doi: 10.1109/TC.1980.1675640.  Google Scholar

[7]

J. Combin. Theory Ser. A, 24 (1978), 251-253. doi: 10.1016/0097-3165(78)90013-4.  Google Scholar

[8]

in "Handbook of Incidence Geometry--Buildings and Foundations'' (ed. F. Buekenhout), Elsevier Science Publ., (1995), 433-475. Google Scholar

[9]

IEEE Trans. Inform. Theory, 40 (1994), 1872-1881. doi: 10.1109/18.340462.  Google Scholar

[10]

IEEE Commun. Lett., 4 (2000), 158-160. doi: 10.1109/4234.846497.  Google Scholar

[11]

IEEE Trans. Inform. Theory, 28 (1982), 585-592. doi: 10.1109/TIT.1982.1056524.  Google Scholar

[12]

J. Combin. Theory Ser. A, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8.  Google Scholar

[13]

Springer-Verlag, 1968.  Google Scholar

[14]

Springer-Verlag, 1992.  Google Scholar

[15]

Probl. Inf. Transm., 21 (1985), 1-12.  Google Scholar

[16]

MIT Press, Cambridge, MA, 1963.  Google Scholar

[17]

J. Combin. Theory Ser. A, 92 (2000), 17-28. doi: 10.1006/jcta.1999.3033.  Google Scholar

[18]

2nd edition, John Wiley & Sons, 1986.  Google Scholar

[19]

in "Proceedings of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-2000),'' Bansko, Bulgaria, (2000), 183-188. Google Scholar

[20]

2nd edition, Oxford University Press, New York, 1998.  Google Scholar

[21]

J. Statist. Plann. Inference, 72 (1998), 355-380. doi: 10.1016/S0378-3758(98)00043-3.  Google Scholar

[22]

in "Finite Geometries,'' Kluwer Acad. Publ., Dordrecht, (2001), 201-246. doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[23]

Probl. Inform. Transm., 35 (1999), 205-223.  Google Scholar

[24]

J. Combin. Theory Ser. A, 22 (1977), 253-266. doi: 10.1016/0097-3165(77)90001-2.  Google Scholar

[25]

Discrete Math., 6 (1973), 255-262. doi: 10.1016/0012-365X(73)90098-8.  Google Scholar

[26]

J. Combin. Theory Ser. A, 71 (1995), 112-126. doi: 10.1016/0097-3165(95)90019-5.  Google Scholar

[27]

Springer-Verlag, 1991. doi: 10.1007/978-1-4684-0406-7.  Google Scholar

[28]

I. Landjev and L. Storme, Galois geometries and coding theory,, in, (): 185.   Google Scholar

[29]

J. Aust. Math. Soc. Ser. A, 33 (1982), 197-212. doi: 10.1017/S1446788700018346.  Google Scholar

[30]

IEEE Trans. Comput., 25 (1976), 945-949. doi: 10.1109/TC.1976.1674720.  Google Scholar

[31]

IEEE Trans. Inform. Theory, 37 (1991), 328-336. doi: 10.1109/18.75248.  Google Scholar

[32]

World Scientific, 1996. doi: 10.1142/9789812830234.  Google Scholar

[33]

IEEE Trans. Inform. Theory, 55 (2009), 1468-1486. doi: 10.1109/TIT.2009.2013009.  Google Scholar

[34]

S. Yang, T. Honold, Y. Chen, Z. Zhang and P. Qiu, Constructing linear codes with good spectra,, preprint, ().   Google Scholar

[35]

in "Arithmetic of Finite Fields,'' Springer-Verlag, Berlin, (2007), 147-158. doi: 10.1007/978-3-540-73074-3_12.  Google Scholar

show all references

References:
[1]

Cambridge University Press, 1998.  Google Scholar

[2]

S. Ball, The polynomial method in Galois geometries,, in, (): 103.   Google Scholar

[3]

IEEE Trans. Inform. Theory, 48 (2002), 2568-2573. doi: 10.1109/TIT.2002.800480.  Google Scholar

[4]

Nova Science Publishers, 2011. Google Scholar

[5]

A. Blokhuis, P. Sziklai and T. Szőnyi, Blocking sets in projective spaces,, in, (): 61.   Google Scholar

[6]

IEEE Trans. Comput., 29 (1980), 665-668. doi: 10.1109/TC.1980.1675640.  Google Scholar

[7]

J. Combin. Theory Ser. A, 24 (1978), 251-253. doi: 10.1016/0097-3165(78)90013-4.  Google Scholar

[8]

in "Handbook of Incidence Geometry--Buildings and Foundations'' (ed. F. Buekenhout), Elsevier Science Publ., (1995), 433-475. Google Scholar

[9]

IEEE Trans. Inform. Theory, 40 (1994), 1872-1881. doi: 10.1109/18.340462.  Google Scholar

[10]

IEEE Commun. Lett., 4 (2000), 158-160. doi: 10.1109/4234.846497.  Google Scholar

[11]

IEEE Trans. Inform. Theory, 28 (1982), 585-592. doi: 10.1109/TIT.1982.1056524.  Google Scholar

[12]

J. Combin. Theory Ser. A, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8.  Google Scholar

[13]

Springer-Verlag, 1968.  Google Scholar

[14]

Springer-Verlag, 1992.  Google Scholar

[15]

Probl. Inf. Transm., 21 (1985), 1-12.  Google Scholar

[16]

MIT Press, Cambridge, MA, 1963.  Google Scholar

[17]

J. Combin. Theory Ser. A, 92 (2000), 17-28. doi: 10.1006/jcta.1999.3033.  Google Scholar

[18]

2nd edition, John Wiley & Sons, 1986.  Google Scholar

[19]

in "Proceedings of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-2000),'' Bansko, Bulgaria, (2000), 183-188. Google Scholar

[20]

2nd edition, Oxford University Press, New York, 1998.  Google Scholar

[21]

J. Statist. Plann. Inference, 72 (1998), 355-380. doi: 10.1016/S0378-3758(98)00043-3.  Google Scholar

[22]

in "Finite Geometries,'' Kluwer Acad. Publ., Dordrecht, (2001), 201-246. doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[23]

Probl. Inform. Transm., 35 (1999), 205-223.  Google Scholar

[24]

J. Combin. Theory Ser. A, 22 (1977), 253-266. doi: 10.1016/0097-3165(77)90001-2.  Google Scholar

[25]

Discrete Math., 6 (1973), 255-262. doi: 10.1016/0012-365X(73)90098-8.  Google Scholar

[26]

J. Combin. Theory Ser. A, 71 (1995), 112-126. doi: 10.1016/0097-3165(95)90019-5.  Google Scholar

[27]

Springer-Verlag, 1991. doi: 10.1007/978-1-4684-0406-7.  Google Scholar

[28]

I. Landjev and L. Storme, Galois geometries and coding theory,, in, (): 185.   Google Scholar

[29]

J. Aust. Math. Soc. Ser. A, 33 (1982), 197-212. doi: 10.1017/S1446788700018346.  Google Scholar

[30]

IEEE Trans. Comput., 25 (1976), 945-949. doi: 10.1109/TC.1976.1674720.  Google Scholar

[31]

IEEE Trans. Inform. Theory, 37 (1991), 328-336. doi: 10.1109/18.75248.  Google Scholar

[32]

World Scientific, 1996. doi: 10.1142/9789812830234.  Google Scholar

[33]

IEEE Trans. Inform. Theory, 55 (2009), 1468-1486. doi: 10.1109/TIT.2009.2013009.  Google Scholar

[34]

S. Yang, T. Honold, Y. Chen, Z. Zhang and P. Qiu, Constructing linear codes with good spectra,, preprint, ().   Google Scholar

[35]

in "Arithmetic of Finite Fields,'' Springer-Verlag, Berlin, (2007), 147-158. doi: 10.1007/978-3-540-73074-3_12.  Google Scholar

[1]

Sascha Kurz. The $[46, 9, 20]_2$ code is unique. Advances in Mathematics of Communications, 2021, 15 (3) : 415-422. doi: 10.3934/amc.2020074
[2]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[3]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[4]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243
[5]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, 2021, 15 (3) : 387-413. doi: 10.3934/ipi.2020073
[6]

Joe Gildea, Adrian Korban, Abidin Kaya, Bahattin Yildiz. Constructing self-dual codes from group rings and reverse circulant matrices. Advances in Mathematics of Communications, 2021, 15 (3) : 471-485. doi: 10.3934/amc.2020077
[7]

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

Yuzhou Tian, Yulin Zhao. Global phase portraits and bifurcation diagrams for reversible equivariant Hamiltonian systems of linear plus quartic homogeneous polynomials. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 2941-2956. doi: 10.3934/dcdsb.2020214
[9]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055
[10]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133
[11]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[12]

Gelasio Salaza, Edgardo Ugalde, Jesús Urías. Master--slave synchronization of affine cellular automaton pairs. Discrete & Continuous Dynamical Systems, 2005, 13 (2) : 491-502. doi: 10.3934/dcds.2005.13.491
[13]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[14]

Mayte Pérez-Llanos, Juan Pablo Pinasco, Nicolas Saintier. Opinion fitness and convergence to consensus in homogeneous and heterogeneous populations. Networks & Heterogeneous Media, 2021, 16 (2) : 257-281. doi: 10.3934/nhm.2021006
[15]

Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003
[16]

Scott Schmieding, Rodrigo Treviño. Random substitution tilings and deviation phenomena. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3869-3902. doi: 10.3934/dcds.2021020
[17]

Muberra Allahverdi, Harun Aydilek, Asiye Aydilek, Ali Allahverdi. A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1973-1991. doi: 10.3934/jimo.2020054
[18]

Mario Bukal. Well-posedness and convergence of a numerical scheme for the corrected Derrida-Lebowitz-Speer-Spohn equation using the Hellinger distance. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3389-3414. doi: 10.3934/dcds.2021001
[19]

Nouressadat Touafek, Durhasan Turgut Tollu, Youssouf Akrour. On a general homogeneous three-dimensional system of difference equations. Electronic Research Archive, , () : -. doi: 10.3934/era.2021017
[20]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (73)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences