A301370 Maximum determinant of an n X n (0,1)-matrix that has exactly 2*n ones.

0, 2, 2, 3, 4, 4, 6, 8, 9, 12, 16, 18, 24, 32, 36, 48, 64

Offset: 2

Author

Hugo Pfoertner, Mar 20 2018

Keywords

• nonn
• hard
• more

Comments

A proved upper bound is abs(a(n)) <= 6^(n/6), provided by Bruhn and Rautenbach. A conjectured sharper bound is abs(a(n)) <= 2^(n/3), provided by the same authors. For n=3*k, the bound is achieved by diagonally concatenating blocks ((1 1 0)(0 1 1)(1 0 1)).

The sharper bound is proved by Araujo, Balogh, and Wang in their article. See link. - Hugo Pfoertner, Nov 04 2020

Examples

			a(8) = 6 because no (0,1)-matrix with 2*8 ones with a greater determinant exists than
  ( 1 0 0 0 0 0 0 0 )
  ( 0 1 0 1 0 0 0 0 )
  ( 0 0 1 0 1 1 0 0 )
  ( 0 0 0 1 0 0 1 0 )
  ( 0 0 0 0 1 0 0 1 )
  ( 0 0 0 0 0 1 0 1 )
  ( 0 1 0 0 0 0 1 0 )
  ( 0 0 1 0 0 0 0 1 )
		

Links

• Igor Araujo, József Balogh, and Yuzhou Wang, Maximum determinant and permanent of sparse 0-1 matrices, arXiv:2011.01892 [math.CO], 3 Nov 2020.
• Henning Bruhn and Dieter Rautenbach, Maximal determinants of combinatorial matrices, arXiv:1711.09935 [math.CO], 2017.
• Mathoverflow, Are bounds known for the maximum determinant of a (0,1)-matrix of specified size and with a specifed number of 1s?, 2014-2018.
• Yaroslav Shitov, On the determinant of a sparse 0-1 matrix, Linear Algebra and its Applications, Volume 554, 1 October 2018, Pages 49-50.
• Markus Sigg, Gasper's determinant theorem, revisited, arXiv:1804.02897 [math.CO], 2018.

Crossrefs

Cf. A003432, A017979, A085000.