Блог пользователя Sangar

Maximum value of the determinant formed from the matrix of 0 and n
Автор Sangar, история, 8 лет назад, По-английски

Given a number k , a number n We have to form a K*K square matrix using just the numbers 0 and n such that it has maximum possible determinant We have to write a program that returns such determinant for given values of k and n

for example if k = 3 and n = 13

13 13 0

0 13 13

13 0 13

ie for k = 3 and any non negative value of n required matrix is

n n 0

0 n n

n 0 n

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

constraints for n and k?

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

This is a very classic problem known as Hadamard's maximal determinant problem. Long story short, this is an open question even for k = 21 (k ≤ 20 is known, and lots of larger cases are known as well--this is linked to the Hadamard Conjecture, as well).

The fact that you are putting n into the matrix can be ignored since dividing a row by n also divides the determinant by n, so if you determine the maximal determinant of (0,1)-matrices, we can reverse the above operations and the result of this problem will be nk times larger than the answer for (0,1)-matrices.

→ Ответить