Good random matrices over finite fields

Shengtian Yang; Thomas Honold

doi:10.3934/amc.2012.6.203

Article Contents

2012, Volume 6, Issue 2: 203-227. Doi: 10.3934/amc.2012.6.203

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

Good random matrices over finite fields

Shengtian Yang^1, and
Thomas Honold^2,

1.
Zhengyuan Xiaoqu 10-2-101, Fengtan Road, Hangzhou 310011
2.
Department of Information Science and Electronics Engineering, Zhejiang University, 38 Zheda Road, Hangzhou 310027

Received: April 30, 2011

Revised: June 30, 2011

Published: April 2012

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 94B05, 15B52, 60B20, 15B33, 51E21.

Citation:

Related Papers

Cited by

References

[1]	G. E. Andrews, "The Theory of Partitions,'' Cambridge University Press, 1998.
[2]	S. Ball, The polynomial method in Galois geometries, in "Beule and Storme [4],'' Chapter 5, 103-128.
[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 "Beule and Storme [4],'' Chapter 3, 61-84.
[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 "Beule and Storme [4],'' Chapter 8, 185-212.
[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, arXiv:0909.3131
[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.