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]

G. E. Andrews, "The Theory of Partitions,'' Cambridge University Press, 1998.  Google Scholar

[2]

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

[3]

A. Barg and G. D. Forney, Jr., Random codes: Minimum distances and error exponents, IEEE Trans. Inform. Theory, 48 (2002), 2568-2573. doi: 10.1109/TIT.2002.800480.  Google Scholar

[4]

J. D. Beule and L. Storme (eds.), "Current Research Topics in Galois Geometry,'' 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]

B. Bose and T. R. N. Rao, Separating and completely separating systems and linear codes, IEEE Trans. Comput., 29 (1980), 665-668. doi: 10.1109/TC.1980.1675640.  Google Scholar

[7]

A. E. Brouwer and A. Schrijver, The blocking number of an affine space, J. Combin. Theory Ser. A, 24 (1978), 251-253. doi: 10.1016/0097-3165(78)90013-4.  Google Scholar

[8]

F. de Clerck and H. van Maldeghem, Some classes of rank two geometries, in "Handbook of Incidence Geometry--Buildings and Foundations'' (ed. F. Buekenhout), Elsevier Science Publ., (1995), 433-475. Google Scholar

[9]

G. Cohen and G. Zémor, Intersecting codes and independent families, IEEE Trans. Inform. Theory, 40 (1994), 1872-1881. doi: 10.1109/18.340462.  Google Scholar

[10]

G. Cohen and G. Zémor, Copyright protection for digital data, IEEE Commun. Lett., 4 (2000), 158-160. doi: 10.1109/4234.846497.  Google Scholar

[11]

I. Csiszár, Linear codes for sources and source networks: error exponents, universal coding, IEEE Trans. Inform. Theory, 28 (1982), 585-592. doi: 10.1109/TIT.1982.1056524.  Google Scholar

[12]

P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8.  Google Scholar

[13]

P. Dembowski, "Finite Geometries,'' Springer-Verlag, 1968.  Google Scholar

[14]

A. B. Evans, "Orthomorphism Graphs of Groups,'' Springer-Verlag, 1992.  Google Scholar

[15]

E.M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 1-12.  Google Scholar

[16]

R. G. Gallager, "Low-Density Parity-Check Codes,'' MIT Press, Cambridge, MA, 1963.  Google Scholar

[17]

M. Greferath and S. E. Schmidt, Finite-ring combinatorics and MacWilliams' equivalence theorem, J. Combin. Theory Ser. A, 92 (2000), 17-28. doi: 10.1006/jcta.1999.3033.  Google Scholar

[18]

M. Hall, Jr., "Combinatorial Theory,'' 2nd edition, John Wiley & Sons, 1986.  Google Scholar

[19]

W. Heise and T. Honold, Homogeneous and egalitarian weights on finite rings, in "Proceedings of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-2000),'' Bansko, Bulgaria, (2000), 183-188. Google Scholar

[20]

J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition, Oxford University Press, New York, 1998.  Google Scholar

[21]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces, J. Statist. Plann. Inference, 72 (1998), 355-380. doi: 10.1016/S0378-3758(98)00043-3.  Google Scholar

[22]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: update 2001, in "Finite Geometries,'' Kluwer Acad. Publ., Dordrecht, (2001), 201-246. doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[23]

T. Honold and A. A. Nechaev, Weighted modules and representations of codes, Probl. Inform. Transm., 35 (1999), 205-223.  Google Scholar

[24]

R. E. Jamison, Covering finite fields with cosets of subspaces, J. Combin. Theory Ser. A, 22 (1977), 253-266. doi: 10.1016/0097-3165(77)90001-2.  Google Scholar

[25]

D. J. Kleitman and J. Spencer, Families of k-independent sets, Discrete Math., 6 (1973), 255-262. doi: 10.1016/0012-365X(73)90098-8.  Google Scholar

[26]

J. Körner, On the extremal combinatorics of the Hamming space, J. Combin. Theory Ser. A, 71 (1995), 112-126. doi: 10.1016/0097-3165(95)90019-5.  Google Scholar

[27]

T.-Y. Lam, "A First Course in Noncommutative Rings,'' 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]

H. Niederreiter and K. H. Robinson, Complete mappings of finite fields, J. Aust. Math. Soc. Ser. A, 33 (1982), 197-212. doi: 10.1017/S1446788700018346.  Google Scholar

[30]

D. R. Pradhan and S. M. Peddy, Techniques to construct $(2, 1)$ separating systems from linear error-correcting codes, IEEE Trans. Comput., 25 (1976), 945-949. doi: 10.1109/TC.1976.1674720.  Google Scholar

[31]

R. M. Roth, Maximum-rank array codes and their application to crisscross error correction, IEEE Trans. Inform. Theory, 37 (1991), 328-336. doi: 10.1109/18.75248.  Google Scholar

[32]

Z.-X. Wan, "Geometry of Matrices,'' World Scientific, 1996. doi: 10.1142/9789812830234.  Google Scholar

[33]

S. Yang, Y. Chen and P. Qiu, Linear-codes-based lossless joint source-channel coding for multiple-access channels, 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]

Y. Yuan, Y. Tong and H. Zhang, Complete mapping polynomials over finite field $\mathbb F_{16}$, 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]

G. E. Andrews, "The Theory of Partitions,'' Cambridge University Press, 1998.  Google Scholar

[2]

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

[3]

A. Barg and G. D. Forney, Jr., Random codes: Minimum distances and error exponents, IEEE Trans. Inform. Theory, 48 (2002), 2568-2573. doi: 10.1109/TIT.2002.800480.  Google Scholar

[4]

J. D. Beule and L. Storme (eds.), "Current Research Topics in Galois Geometry,'' 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]

B. Bose and T. R. N. Rao, Separating and completely separating systems and linear codes, IEEE Trans. Comput., 29 (1980), 665-668. doi: 10.1109/TC.1980.1675640.  Google Scholar

[7]

A. E. Brouwer and A. Schrijver, The blocking number of an affine space, J. Combin. Theory Ser. A, 24 (1978), 251-253. doi: 10.1016/0097-3165(78)90013-4.  Google Scholar

[8]

F. de Clerck and H. van Maldeghem, Some classes of rank two geometries, in "Handbook of Incidence Geometry--Buildings and Foundations'' (ed. F. Buekenhout), Elsevier Science Publ., (1995), 433-475. Google Scholar

[9]

G. Cohen and G. Zémor, Intersecting codes and independent families, IEEE Trans. Inform. Theory, 40 (1994), 1872-1881. doi: 10.1109/18.340462.  Google Scholar

[10]

G. Cohen and G. Zémor, Copyright protection for digital data, IEEE Commun. Lett., 4 (2000), 158-160. doi: 10.1109/4234.846497.  Google Scholar

[11]

I. Csiszár, Linear codes for sources and source networks: error exponents, universal coding, IEEE Trans. Inform. Theory, 28 (1982), 585-592. doi: 10.1109/TIT.1982.1056524.  Google Scholar

[12]

P. Delsarte, Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, 25 (1978), 226-241. doi: 10.1016/0097-3165(78)90015-8.  Google Scholar

[13]

P. Dembowski, "Finite Geometries,'' Springer-Verlag, 1968.  Google Scholar

[14]

A. B. Evans, "Orthomorphism Graphs of Groups,'' Springer-Verlag, 1992.  Google Scholar

[15]

E.M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 1-12.  Google Scholar

[16]

R. G. Gallager, "Low-Density Parity-Check Codes,'' MIT Press, Cambridge, MA, 1963.  Google Scholar

[17]

M. Greferath and S. E. Schmidt, Finite-ring combinatorics and MacWilliams' equivalence theorem, J. Combin. Theory Ser. A, 92 (2000), 17-28. doi: 10.1006/jcta.1999.3033.  Google Scholar

[18]

M. Hall, Jr., "Combinatorial Theory,'' 2nd edition, John Wiley & Sons, 1986.  Google Scholar

[19]

W. Heise and T. Honold, Homogeneous and egalitarian weights on finite rings, in "Proceedings of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory (ACCT-2000),'' Bansko, Bulgaria, (2000), 183-188. Google Scholar

[20]

J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition, Oxford University Press, New York, 1998.  Google Scholar

[21]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces, J. Statist. Plann. Inference, 72 (1998), 355-380. doi: 10.1016/S0378-3758(98)00043-3.  Google Scholar

[22]

J. W. P. Hirschfeld and L. Storme, The packing problem in statistics, coding theory and finite projective spaces: update 2001, in "Finite Geometries,'' Kluwer Acad. Publ., Dordrecht, (2001), 201-246. doi: 10.1007/978-1-4613-0283-4_13.  Google Scholar

[23]

T. Honold and A. A. Nechaev, Weighted modules and representations of codes, Probl. Inform. Transm., 35 (1999), 205-223.  Google Scholar

[24]

R. E. Jamison, Covering finite fields with cosets of subspaces, J. Combin. Theory Ser. A, 22 (1977), 253-266. doi: 10.1016/0097-3165(77)90001-2.  Google Scholar

[25]

D. J. Kleitman and J. Spencer, Families of k-independent sets, Discrete Math., 6 (1973), 255-262. doi: 10.1016/0012-365X(73)90098-8.  Google Scholar

[26]

J. Körner, On the extremal combinatorics of the Hamming space, J. Combin. Theory Ser. A, 71 (1995), 112-126. doi: 10.1016/0097-3165(95)90019-5.  Google Scholar

[27]

T.-Y. Lam, "A First Course in Noncommutative Rings,'' 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]

H. Niederreiter and K. H. Robinson, Complete mappings of finite fields, J. Aust. Math. Soc. Ser. A, 33 (1982), 197-212. doi: 10.1017/S1446788700018346.  Google Scholar

[30]

D. R. Pradhan and S. M. Peddy, Techniques to construct $(2, 1)$ separating systems from linear error-correcting codes, IEEE Trans. Comput., 25 (1976), 945-949. doi: 10.1109/TC.1976.1674720.  Google Scholar

[31]

R. M. Roth, Maximum-rank array codes and their application to crisscross error correction, IEEE Trans. Inform. Theory, 37 (1991), 328-336. doi: 10.1109/18.75248.  Google Scholar

[32]

Z.-X. Wan, "Geometry of Matrices,'' World Scientific, 1996. doi: 10.1142/9789812830234.  Google Scholar

[33]

S. Yang, Y. Chen and P. Qiu, Linear-codes-based lossless joint source-channel coding for multiple-access channels, 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]

Y. Yuan, Y. Tong and H. Zhang, Complete mapping polynomials over finite field $\mathbb F_{16}$, in "Arithmetic of Finite Fields,'' Springer-Verlag, Berlin, (2007), 147-158. doi: 10.1007/978-3-540-73074-3_12.  Google Scholar

[1]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003
[2]

María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018
[3]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042
[4]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1
[5]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45
[6]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275
[7]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399
[8]

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

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[10]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032
[11]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013
[12]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046
[13]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[14]

Jorge P. Arpasi. On the non-Abelian group code capacity of memoryless channels. Advances in Mathematics of Communications, 2020, 14 (3) : 423-436. doi: 10.3934/amc.2020058
[15]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83
[16]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261
[17]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149
[18]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281
[19]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027
[20]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences