Good random matrices over finite fields

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

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). 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. 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. 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. 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, (1995), 433. Google Scholar
[9]	G. Cohen and G. Zémor, Intersecting codes and independent families,, IEEE Trans. Inform. Theory, 40 (1994), 1872. 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. 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. 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. 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. Google Scholar
[16]	R. G. Gallager, "Low-Density Parity-Check Codes,'', MIT Press, (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. doi: 10.1006/jcta.1999.3033. Google Scholar
[18]	M. Hall, Jr., "Combinatorial Theory,'', 2^nd edition, (1986). Google Scholar
[19]	W. Heise and T. Honold, Homogeneous and egalitarian weights on finite rings,, in, (2000), 183. Google Scholar
[20]	J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'', 2^nd edition, (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. 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, (2001), 201. 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. Google Scholar
[24]	R. E. Jamison, Covering finite fields with cosets of subspaces,, J. Combin. Theory Ser. A, 22 (1977), 253. 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. 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. 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. 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. 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. 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. 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, (2007), 147. 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. 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. 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. 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, (1995), 433. Google Scholar
[9]	G. Cohen and G. Zémor, Intersecting codes and independent families,, IEEE Trans. Inform. Theory, 40 (1994), 1872. 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. 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. 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. 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. Google Scholar
[16]	R. G. Gallager, "Low-Density Parity-Check Codes,'', MIT Press, (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. doi: 10.1006/jcta.1999.3033. Google Scholar
[18]	M. Hall, Jr., "Combinatorial Theory,'', 2^nd edition, (1986). Google Scholar
[19]	W. Heise and T. Honold, Homogeneous and egalitarian weights on finite rings,, in, (2000), 183. Google Scholar
[20]	J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'', 2^nd edition, (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. 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, (2001), 201. 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. Google Scholar
[24]	R. E. Jamison, Covering finite fields with cosets of subspaces,, J. Combin. Theory Ser. A, 22 (1977), 253. 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. 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. 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. 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. 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. 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. 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, (2007), 147. 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]	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
[3]	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
[4]	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
[5]	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
[6]	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
[7]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	John Sheekey. A new family of linear maximum rank distance codes. Advances in Mathematics of Communications, 2016, 10 (3) : 475-488. doi: 10.3934/amc.2016019
[15]	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
[16]	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
[17]	Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z₄. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017
[18]	Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029
[19]	Artem Dudko. Computability of the Julia set. Nonrecurrent critical orbits. Discrete & Continuous Dynamical Systems - A, 2014, 34 (7) : 2751-2778. doi: 10.3934/dcds.2014.34.2751
[20]	Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences