2012, 6(2): 203-227. doi: 10.3934/amc.2012.6.203

Good random matrices over finite fields

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.
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. 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. 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. doi: 10.1016/0097-3165(78)90013-4.

[8]

F. de Clerck and H. van Maldeghem, Some classes of rank two geometries,, in, (1995), 433.

[9]

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

[10]

G. Cohen and G. Zémor, Copyright protection for digital data,, IEEE Commun. Lett., 4 (2000), 158. 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. 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. 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.

[16]

R. G. Gallager, "Low-Density Parity-Check Codes,'', MIT Press, (1963).

[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.

[18]

M. Hall, Jr., "Combinatorial Theory,'', 2nd edition, (1986).

[19]

W. Heise and T. Honold, Homogeneous and egalitarian weights on finite rings,, in, (2000), 183.

[20]

J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'', 2nd edition, (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. 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, (2001), 201. 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.

[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.

[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.

[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.

[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. 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. 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. 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. 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, (2007), 147. 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. 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. 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. doi: 10.1016/0097-3165(78)90013-4.

[8]

F. de Clerck and H. van Maldeghem, Some classes of rank two geometries,, in, (1995), 433.

[9]

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

[10]

G. Cohen and G. Zémor, Copyright protection for digital data,, IEEE Commun. Lett., 4 (2000), 158. 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. 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. 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.

[16]

R. G. Gallager, "Low-Density Parity-Check Codes,'', MIT Press, (1963).

[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.

[18]

M. Hall, Jr., "Combinatorial Theory,'', 2nd edition, (1986).

[19]

W. Heise and T. Honold, Homogeneous and egalitarian weights on finite rings,, in, (2000), 183.

[20]

J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'', 2nd edition, (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. 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, (2001), 201. 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.

[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.

[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.

[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.

[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. 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. 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. 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. 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, (2007), 147. 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]

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$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

[6]

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

[7]

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

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

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]

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 Z4. 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

2017 Impact Factor: 0.564

Metrics

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

Other articles
by authors

[Back to Top]