Good random matrices over finite fields

Shengtian Yang; Thomas Honold

doi:10.3934/amc.2012.6.203

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). 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]	Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020169
[2]	Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076
[3]	Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020168
[4]	Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020164
[5]	Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073
[6]	Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[7]	Federico Rodriguez Hertz, Zhiren Wang. On $ \epsilon $-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365
[8]	Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020 doi: 10.3934/mcrf.2020048
[9]	Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020444
[10]	Antoine Benoit. Weak well-posedness of hyperbolic boundary value problems in a strip: when instabilities do not reflect the geometry. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5475-5486. doi: 10.3934/cpaa.2020248
[11]	Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121
[12]	Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080
[13]	S. Sadeghi, H. Jafari, S. Nemati. Solving fractional Advection-diffusion equation using Genocchi operational matrix based on Atangana-Baleanu derivative. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020435
[14]	Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020375

2019 Impact Factor: 0.734

American Institute of Mathematical Sciences

Good random matrices over finite fields

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Good random matrices over finite fields

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors