Advanced Search
Article Contents
Article Contents

Good random matrices over finite fields

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: 94B05, 15B52, 60B20, 15B33, 51E21.


    \begin{equation} \\ \end{equation}
  • [1]

    G. E. Andrews, "The Theory of Partitions,'' Cambridge University Press, 1998.


    S. BallThe polynomial method in Galois geometries, in "Beule and Storme [4],'' Chapter 5, 103-128.


    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.


    J. D. Beule and L. Storme (eds.), "Current Research Topics in Galois Geometry,'' Nova Science Publishers, 2011.


    A. Blokhuis, P. Sziklai and T. SzőnyiBlocking sets in projective spaces, in "Beule and Storme [4],'' Chapter 3, 61-84.


    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.


    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.


    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.


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


    G. Cohen and G. Zémor, Copyright protection for digital data, IEEE Commun. Lett., 4 (2000), 158-160.doi: 10.1109/4234.846497.


    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.


    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.


    P. Dembowski, "Finite Geometries,'' Springer-Verlag, 1968.


    A. B. Evans, "Orthomorphism Graphs of Groups,'' Springer-Verlag, 1992.


    E.M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 1-12.


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


    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.


    M. Hall, Jr., "Combinatorial Theory,'' 2nd edition, John Wiley & Sons, 1986.


    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.


    J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition, Oxford University Press, New York, 1998.


    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.


    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.


    T. Honold and A. A. Nechaev, Weighted modules and representations of codes, Probl. Inform. Transm., 35 (1999), 205-223.


    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.


    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.


    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.


    T.-Y. Lam, "A First Course in Noncommutative Rings,'' Springer-Verlag, 1991.doi: 10.1007/978-1-4684-0406-7.


    I. Landjev and L. StormeGalois geometries and coding theory, in "Beule and Storme [4],'' Chapter 8, 185-212.


    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.


    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.


    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.


    Z.-X. Wan, "Geometry of Matrices,'' World Scientific, 1996.doi: 10.1142/9789812830234.


    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.


    S. Yang, T. Honold, Y. Chen, Z. Zhang and P. QiuConstructing linear codes with good spectra, preprint, arXiv:0909.3131


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(119) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint