Good random matrices over finite fields

Previous Article
Classification of self-dual codes of length 36
AMC Home
This Issue
Next Article
Double-circulant and bordered-double-circulant constructions for self-dual codes over $R_2$

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

Abstract
Related Papers

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.
[2]	S. Ball, The polynomial method in Galois geometries,, in, (): 103.
[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.
[4]	J. D. Beule and L. Storme (eds.), "Current Research Topics in Galois Geometry,'' Nova Science Publishers, 2011.
[5]	A. Blokhuis, P. Sziklai and T. Szőnyi, Blocking sets in projective spaces,, in, (): 61.
[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.
[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.
[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.
[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.
[10]	G. Cohen and G. Zémor, Copyright protection for digital data, IEEE Commun. Lett., 4 (2000), 158-160. doi: 10.1109/4234.846497.
[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.
[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.
[13]	P. Dembowski, "Finite Geometries,'' Springer-Verlag, 1968.
[14]	A. B. Evans, "Orthomorphism Graphs of Groups,'' Springer-Verlag, 1992.
[15]	E.M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 1-12.
[16]	R. G. Gallager, "Low-Density Parity-Check Codes,'' MIT Press, Cambridge, MA, 1963.
[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.
[18]	M. Hall, Jr., "Combinatorial Theory,'' 2^nd edition, John Wiley & Sons, 1986.
[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.
[20]	J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2^nd edition, Oxford University Press, New York, 1998.
[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.
[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.
[23]	T. Honold and A. A. Nechaev, Weighted modules and representations of codes, Probl. Inform. Transm., 35 (1999), 205-223.
[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.
[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.
[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.
[27]	T.-Y. Lam, "A First Course in Noncommutative Rings,'' Springer-Verlag, 1991. doi: 10.1007/978-1-4684-0406-7.
[28]	I. Landjev and L. Storme, Galois geometries and coding theory,, in, (): 185.
[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.
[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.
[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.
[32]	Z.-X. Wan, "Geometry of Matrices,'' World Scientific, 1996. doi: 10.1142/9789812830234.
[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.
[34]	S. Yang, T. Honold, Y. Chen, Z. Zhang and P. Qiu, Constructing linear codes with good spectra,, preprint, ().
[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.

show all references

References:

[1]	G. E. Andrews, "The Theory of Partitions,'' Cambridge University Press, 1998.
[2]	S. Ball, The polynomial method in Galois geometries,, in, (): 103.
[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.
[4]	J. D. Beule and L. Storme (eds.), "Current Research Topics in Galois Geometry,'' Nova Science Publishers, 2011.
[5]	A. Blokhuis, P. Sziklai and T. Szőnyi, Blocking sets in projective spaces,, in, (): 61.
[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.
[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.
[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.
[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.
[10]	G. Cohen and G. Zémor, Copyright protection for digital data, IEEE Commun. Lett., 4 (2000), 158-160. doi: 10.1109/4234.846497.
[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.
[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.
[13]	P. Dembowski, "Finite Geometries,'' Springer-Verlag, 1968.
[14]	A. B. Evans, "Orthomorphism Graphs of Groups,'' Springer-Verlag, 1992.
[15]	E.M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 1-12.
[16]	R. G. Gallager, "Low-Density Parity-Check Codes,'' MIT Press, Cambridge, MA, 1963.
[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.
[18]	M. Hall, Jr., "Combinatorial Theory,'' 2^nd edition, John Wiley & Sons, 1986.
[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.
[20]	J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2^nd edition, Oxford University Press, New York, 1998.
[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.
[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.
[23]	T. Honold and A. A. Nechaev, Weighted modules and representations of codes, Probl. Inform. Transm., 35 (1999), 205-223.
[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.
[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.
[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.
[27]	T.-Y. Lam, "A First Course in Noncommutative Rings,'' Springer-Verlag, 1991. doi: 10.1007/978-1-4684-0406-7.
[28]	I. Landjev and L. Storme, Galois geometries and coding theory,, in, (): 185.
[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.
[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.
[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.
[32]	Z.-X. Wan, "Geometry of Matrices,'' World Scientific, 1996. doi: 10.1142/9789812830234.
[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.
[34]	S. Yang, T. Honold, Y. Chen, Z. Zhang and P. Qiu, Constructing linear codes with good spectra,, preprint, ().
[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.

[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$₄-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]	Andrea Seidl, Stefan Wrzaczek. Opening the source code: The threat of forking. Journal of Dynamics and Games, 2022 doi: 10.3934/jdg.2022010
[8]	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
[9]	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
[10]	Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete and Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889
[11]	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
[12]	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
[13]	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
[14]	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 and Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407
[15]	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
[16]	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
[17]	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
[18]	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
[19]	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
[20]	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

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Shengtian Yang Thomas Honold
on Google Scholar
Shengtian Yang Thomas Honold

[Back to Top]