Browse issues
no. 2
Rook theory of the Etzion-Silberstein Conjecture
Gruica, Anina1; Ravagnani, Alberto1
1 Department of Mathematics and Computer Science Eindhoven University of Technology the Netherlands
Algebraic Combinatorics, Volume 7 (2024) no. 2, pp. 555-576.

In 2009, Etzion and Silberstein proposed a conjecture on the largest dimension of a linear space of matrices over a finite field in which all nonzero matrices are supported on a Ferrers diagram and have rank bounded below by a given integer. Although several cases of the conjecture have been established in the past decade, proving or disproving it remains to date a wide open problem. In this paper, we take a new look at the Etzion-Silberstein Conjecture, investigating its connection with rook theory. Our results show that the combinatorics behind this open problem is closely linked to the theory of q-rook polynomials associated with Ferrers diagrams, as defined by Garsia and Remmel. In passing, we give a closed formula for the trailing degree of the q-rook polynomial associated with a Ferrers diagram in terms of the cardinalities of its diagonals. The combinatorial approach taken in this paper allows us to establish some new instances of the Etzion-Silberstein Conjecture using a non-constructive argument. We also solve the asymptotic version of the conjecture over large finite fields, answering a current open question.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.337
Classification: 05A16, 11T71
Keywords: rook theory, Ferrers diagram, rank-metric codes

Gruica, Anina 1; Ravagnani, Alberto 1

1 Department of Mathematics and Computer Science Eindhoven University of Technology the Netherlands
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2024__7_2_555_0,
     author = {Gruica, Anina and Ravagnani, Alberto},
     title = {Rook theory of the {Etzion-Silberstein} {Conjecture}},
     journal = {Algebraic Combinatorics},
     pages = {555--576},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {2},
     year = {2024},
     doi = {10.5802/alco.337},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.337/}
}
TY  - JOUR
AU  - Gruica, Anina
AU  - Ravagnani, Alberto
TI  - Rook theory of the Etzion-Silberstein Conjecture
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 555
EP  - 576
VL  - 7
IS  - 2
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.337/
DO  - 10.5802/alco.337
LA  - en
ID  - ALCO_2024__7_2_555_0
ER  - 
%0 Journal Article
%A Gruica, Anina
%A Ravagnani, Alberto
%T Rook theory of the Etzion-Silberstein Conjecture
%J Algebraic Combinatorics
%D 2024
%P 555-576
%V 7
%N 2
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.337/
%R 10.5802/alco.337
%G en
%F ALCO_2024__7_2_555_0
Gruica, Anina; Ravagnani, Alberto. Rook theory of the Etzion-Silberstein Conjecture. Algebraic Combinatorics, Volume 7 (2024) no. 2, pp. 555-576. doi : 10.5802/alco.337. https://alco.centre-mersenne.org/articles/10.5802/alco.337/

[1] Antrobus, Jared; Gluesing-Luerssen, Heide Maximal Ferrers diagram codes: constructions and genericity considerations, IEEE Trans. Inform. Theory, Volume 65 (2019) no. 10, pp. 6204-6223 | DOI | MR | Zbl

[2] Ballico, E. Linear subspaces of matrices associated to a Ferrers diagram and with a prescribed lower bound for their rank, Linear Algebra Appl., Volume 483 (2015), pp. 30-39 | DOI | MR | Zbl

[3] Braun, Michael; Etzion, Tuvi; Östergård, Patric R. J.; Vardy, Alexander; Wassermann, Alfred Existence of q-analogs of Steiner systems, Forum Math. Pi, Volume 4 (2016), Paper no. e7, 14 pages | DOI | MR | Zbl

[4] Carlitz, L.; Riordan, J. Two element lattice permutation numbers and their q-generalization, Duke Math. J., Volume 31 (1964), pp. 371-388 | MR | Zbl

[5] Csajbók, Bence; Marino, Giuseppe; Polverino, Olga; Zullo, Ferdinando Maximum scattered linear sets and MRD-codes, J. Algebraic Combin., Volume 46 (2017) no. 3-4, pp. 517-531 | DOI | MR

[6] de Bruijn, N. G. Asymptotic methods in analysis, Dover Publications, Inc., New York, 1981, xii+200 pages | MR

[7] de Seguins Pazzis, Clément The classification of large spaces of matrices with bounded rank, Israel J. Math., Volume 208 (2015) no. 1, pp. 219-259 | DOI | MR

[8] Delsarte, Ph. Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, Volume 25 (1978) no. 3, pp. 226-241 | DOI | MR | Zbl

[9] Draisma, Jan Small maximal spaces of non-invertible matrices, Bull. London Math. Soc., Volume 38 (2006) no. 5, pp. 764-776 | DOI | MR

[10] Dumas, Jean-Guillaume; Gow, Rod; McGuire, Gary; Sheekey, John Subspaces of matrices with special rank properties, Linear Algebra Appl., Volume 433 (2010) no. 1, pp. 191-202 | DOI | MR

[11] Eisenbud, David; Harris, Joe Vector spaces of matrices of low rank, Adv. in Math., Volume 70 (1988) no. 2, pp. 135-155 | DOI | MR

[12] Etzion, Tuvi; Gorla, Elisa; Ravagnani, Alberto; Wachter-Zeh, Antonia Optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, Volume 62 (2016) no. 4, pp. 1616-1630 | DOI | MR

[13] Etzion, Tuvi; Silberstein, Natalia Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, Volume 55 (2009) no. 7, pp. 2909-2919 | DOI | MR | Zbl

[14] Gabidulin, È. M. Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, Volume 21 (1985) no. 1, pp. 3-16 | MR

[15] Garsia, A. M.; Remmel, J. B. Q-Counting Rook Configurations and a Formula of Frobenius, Journal of Combinatorial Theory, Series A, Volume 41 (1986), pp. 246-275 | DOI | MR

[16] Gelbord, Boaz; Meshulam, Roy Spaces of singular matrices and matroid parity, European J. Combin., Volume 23 (2002) no. 4, pp. 389-397 | DOI | MR | Zbl

[17] Gluesing-Luerssen, Heide; Ravagnani, Alberto Partitions of matrix spaces with an application to q-rook polynomials, European J. Combin., Volume 89 (2020), Paper no. 103120, 28 pages | DOI | MR | Zbl

[18] Gorla, Elisa; Jurrius, Relinde; López, Hiram H.; Ravagnani, Alberto Rank-metric codes and q-polymatroids, J. Algebraic Combin., Volume 52 (2020) no. 1, pp. 1-19 | DOI | MR

[19] Gorla, Elisa; Ravagnani, Alberto Subspace codes from Ferrers diagrams, J. Algebra Appl., Volume 16 (2017) no. 7, Paper no. 1750131, 23 pages | DOI | MR | Zbl

[20] Gruica, Anina; Ravagnani, Alberto Common complements of linear subspaces and the sparseness of MRD codes, SIAM J. Appl. Algebra Geom., Volume 6 (2022) no. 2, pp. 79-110 | DOI | MR

[21] Haglund, James q-Rook Polynomials and Matrices over Finite Fields, Adv. in Appl. Math., Volume 20 (1998) no. 4, pp. 450-487 | DOI | MR

[22] Kötter, Ralf; Kschischang, Frank R. Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, Volume 54 (2008) no. 8, pp. 3579-3591 | DOI | MR | Zbl

[23] Lewis, Joel Brewster; Morales, Alejandro H. Rook theory of the finite general linear group, Exp. Math., Volume 29 (2020) no. 3, pp. 328-346 | DOI | MR | Zbl

[24] Liu, Shuangqing; Chang, Yanxun; Feng, Tao Constructions for optimal Ferrers diagram rank-metric codes, IEEE Trans. Inform. Theory, Volume 65 (2019) no. 7, pp. 4115-4130 | DOI | MR

[25] Lovász, László Singular spaces of matrices and their application in combinatorics, Bol. Soc. Brasil. Mat. (N.S.), Volume 20 (1989) no. 1, pp. 87-99 | DOI | MR | Zbl

[26] MacWilliams, F. J.; Sloane, N. J. A. The theory of error-correcting codes. I, North-Holland Mathematical Library, 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977, p. i-xv and 1–369 | MR

[27] Meshulam, Roy On the maximal rank in a subspace of matrices, Quart. J. Math. Oxford Ser. (2), Volume 36 (1985) no. 142, pp. 225-229 | DOI | MR

[28] Neri, Alessandro; Stanojkovski, Mima A proof of the Etzion-Silberstein conjecture for monotone and MDS-constructible Ferrers diagrams, 2023 | arXiv

[29] Roth, Ron M. Maximum-rank array codes and their application to crisscross error correction, IEEE Trans. Inform. Theory, Volume 37 (1991) no. 2, pp. 328-336 | DOI | MR | Zbl

[30] Schmidt, Kai-Uwe Quadratic and symmetric bilinear forms over finite fields and their association schemes, Algebr. Comb., Volume 3 (2020) no. 1, pp. 161-189 | DOI | Numdam | MR

[31] Segre, Beniamino Curve razionali normali e k-archi negli spazi finiti, Ann. Mat. Pura Appl. (4), Volume 39 (1955), pp. 357-379 | DOI | MR

[32] Sheekey, John New semifields and new MRD codes from skew polynomial rings, J. Lond. Math. Soc. (2), Volume 101 (2020) no. 1, pp. 432-456 | DOI | MR | Zbl

[33] Silberstein, Natalia; Trautmann, Anna-Lena New lower bounds for constant dimension codes, 2013 IEEE International Symposium on Information Theory (2013), pp. 514-518 | DOI

[34] Silberstein, Natalia; Trautmann, Anna-Lena Subspace codes based on graph matchings, Ferrers diagrams, and pending blocks, IEEE Trans. Inform. Theory, Volume 61 (2015) no. 7, pp. 3937-3953 | DOI | MR | Zbl

[35] Silva, Danilo; Kschischang, Frank R.; Kötter, Ralf A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, Volume 54 (2008) no. 9, pp. 3951-3967 | DOI | MR

[36] Stanley, Richard P. Enumerative Combinatorics: Volume 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 1997, xii+325 pages | DOI | MR

[37] Stanley, Richard P. Catalan numbers, Cambridge University Press, New York, 2015, viii+215 pages | DOI | MR

[38] Trautmann, Anna-Lena; Rosenthal, Joachim New improvements on the echelon-Ferrers construction, 19th International Symposium on Mathematical Theory of Networks and Systems (2010), pp. 405-408 | arXiv

[39] Zhang, Tao; Ge, Gennian Constructions of optimal Ferrers diagram rank metric codes, Des. Codes Cryptogr., Volume 87 (2019) no. 1, pp. 107-121 | DOI | MR

Cited by Sources: