Максимальное значение определителя

[bot]

Руст писал(а):

Предлагаю найти максимальное значение определителя k -го порядка(оно красиво вычисляется) из 1 или -1.

Три простых замечания - по делу или нет, пока не знаю. Скорее нет, и надо рыть что-то ещё.

1) Определитель n-го, составленный из $\pm 1$ делится на $2^{m - 1}$. Это очевидно, так как гауссовыми исключениями он сводится к определителю порядка n-1, составленному из 0,2,-2. Кстати, это ещё один вариант устранения комбинаторики из случая с определителем 3-го порядка.
2) Очевидно без разницы считать максимум или минимум, тогда можно сводить комбинаторику к простым случаям переставляя строки (столбцы) без ограничений и меняя их знаки.устранять комбинаторику - можно искать максимум модуля.
3) Если разложить по одной строке, то получаем, что максимум является максимальной суммой всех модулей миноров n-1-го порядка матрицы $(n-1) \times n$

Определитель порядка 4 по п.3 не может быть больше 16, следовательно его максимум либо 8 либо 16. Нереализуемость 16 можно установить теперь перебором, но меня больше привлекла теорема Лапласа. Разлагаем определитель по первым двум строчкам и видим, что 16 можно получить только если в этих двух строчках есть 4 ненулевых минора. Это действительно возможно, однако нетрудно сообразить, что в оставшихся двух строчках невозможно тогда отличие от нуля всех дополнений к этим минорам.

Аналогичным образом, раскладывая по одной строке определитель 5-го порядка, получаем, что он не может быть более 40. Отсюда варианты: 16 и 32. Раскладывая по двум строкам и пытаясь установить, что 32 нереализуемо, обнаружил, что, напротив, реализуемо.

Таким образом, начиная с определителя первого порядка имеем максимумы: 1, 2, 4, 8, 32, ...
Для 6-го порядка не считал и не буду - явно бесперспективный путь для общего случая.
Всё же просто так, от балды, в силу нарастания комбинаторики рискну предположить, что следующим будет вряд ли 128 - скорее 160, а 192 это уже явный перебор.

[evgeny]

Ваши рассуждения можно сформулировать так:
Договорившись искать максимум модуля определителя матрицы $n \times n$ из $\pm1$,
домножим строчки и столбцы на $\pm1$ так, чтобы все элементы в первой строке и первом столбце были $1$.
Вычтем первую строку из всех остальных.
Разложив по перому столбцу, получим множитель $(-2)^{n-1}$ и матрицу из $n-1\times n-1$ из $0,1$.
Таким образом задача сводится к поиску максимального по объему тетраедра в еденичном кубе (изначально одна из вершин тетраедра была фиксированна, теперь же все вершины равноправны)

[rashid]

В книге Садовничего В.А. "Задачи садачи студенческих математических олимпиад" задачка ваша висит по полной красе с его решением и там даже указано что по абсолютной величине определитель k от единиц различных знаков не превосходит от (k-1)*(k-1)!.
для доказательства этого факта надо действовать по индукции выбрав для начального определителя третий порядок...

[evgeny]

А можно узнать полную формулировку задачи из книжки и какой дается ответ (там есть только оценка или найден максимум)?
Дело в том, что для $k=4$ ответ $8$ (хотя это не противоречит оценке $3\cdot 3!=18$).

[bot]

evgeny писал(а):

Домножим строчки и столбцы на $\pm1$ так, чтобы все элементы в первой строке и первом столбце были $1$.

Ну да, я ведь и говорил, что комбинаторику можно сильно уменьшить игнорируя знаки. Для уменьшения порядка определителя этого и не нужно, а при разборе я так и считал - в первом столбце и в первой строке стоят единицы.

Цитата:

Таким образом задача сводится к поиску максимального по объему тетраедра в единичном кубе

Ой ли? Речь ведь не об оценке, а о вычислении. Как там нули и единицы будут располагаться - любым ли способом? Ясно, что не любым - заведомо не будет ситуации без нулей.

rashid писал(а):

В книге Садовничего В.А. "Задачи садачи студенческих математических олимпиад" задачка ваша висит по полной красе с его решением и там даже указано что по абсолютной величине определитель k от единиц различных знаков не превосходит от (k-1)*(k-1)!.

Не заглянул, хотя эта книга у меня есть. Если там только оценка, то она очень грубая даже для $k=6$.
Сравните 160 (хе-хе, как будто это уже факт), ну, ладно, пусть даже 192 и 5\cdot 5!=600. Что 600 на 32 не делится, можно было бы и не говорить.

[rashid]

конечно оценка очень и очень грубая но для малых значений k она дает весомый результат...
там точного решения нету к сожелению

[evgeny]

Цитата:

Ой ли? Речь ведь не об оценке, а о вычислении. Как там нули и единицы будут располагаться - любым ли способом? Ясно, что не любым - заведомо не будет ситуации без нулей.

В том то все и дело, что матрица из 0 и 1 может быть любая - никаких ограничений нет (разность строки из $\pm1$ и строки из $1$ может быть любая строка из $0, -2$).

Если хочется точных формул, то матрице $(b_{i,j})_{n-1}, \ b_{i,j}\in \{0,1\}$
сопоставляется матрица $(a_{i,j})_n, \ a_{i,j}\in \{-1,1\}$ по простым формулам:

$$ a_{i,j} = \left\{ \begin{array}{cl} 1& i=1\ \text{или}\ j=1 \\ 1-2b_{i-1,j-1} & i,j>1\\ \end{array} \right. $$

Соответственно матрица без нулей соответствует исходной матрице с $1$ в первом столбце и первой строке и $-1$ на остальных местах.

Поэтому надо искать тетраедр максимального объема в еденичном кубе (меньшей размерности) - эта задача эквивалентна исходной, но кажется более геометричной

[bot]

Всё-таки прокосячил в реализуемости.
Итог: для четвёртого порядка верхняя оценка 16 реализуется:
++++
++--
+-+-
+--+
Верхнюю оценку для пятого порядка пересчитал раскладывая по двум строкам: максимально возможно 6 ненулевых миноров в этих строках, отсюда получаем 6x2x4=48. Она тоже достигается:
+++++
+++--
++--+
+--+-
+-+-+
Верхнюю оценку 192 для 6 порядка пришлось тоже пересчитать - по прежнему методу она получается 288, хоть по одной строке раскладывай, хоть по двум. Она всё-таки оказалась верной:
В трёх строках определителя максимально может быть 12 ненулевых миноров 3-го порядка, отсюда
12x4x4=192. В двух строках ненулевые миноры строятся по существу из двух векторов, а в трёх строках - из четырёх. Помогло то, что с точностью до перестановок и смены знака имеется лишь два ненулевых определителя 3-го порядка с двумя общими столбцами.
Заколебался теперь - то ли и здесь верхняя оценка реализуется, то ли всё-таки получится 160 или даже 128?

2 evgeny. Да, действительно. Хотя с ходу не вижу как этим воспользоваться.
Меня вот тоже тянет перейти к матрице Грама, умножив определитель на транспонированный, только не знаю, куда это воткнуть?

[bot]

Попробовал получить верхние оценки, в формате 0/1. Разобрал для 4-го и 5-го и что-то не вдохновился. Нет, всё получается, но как-то уж очень, я бы сказал, разнообразно в сравнении с форматом +/-.

[Руст]

Предлагаю найти определитель для матрицы из элементов +-1 который выражается по формуле: $det=2^{N(n)}, N(n)=2n+1-l(n+1)-2[\log_2(n+1)].$, где l(m) число ненулевых цифр в двоичной записи числа m. По моему, это максимальное значение определителя.

[bot]

Не понял. Может быть косяк в формуле? У Вас det - это степень двойки, а это не так для 5-го порядка - я уже писал.
Напишу подробнее:
Раскрываем по первым двум столбцам. В этих столбцах имеем максимально 6 миноров второго порядка, равных 2 или -2. Это очевидно, так как ненулевой минор (с точностью до знака) может быть набран только из строк типа ++ и +-, итого 6 миноров получится, если мы возьмём три строки одного типа и две строки другого. Если для каждого из этих миноров можно подобрать дополнительный минор третьего порядка с крайним +-4, то мы сможем реализовать верхнюю оценку $6\cdot 2 \cdot 4 = 48$. Эту реализацию я указал выше.

Для 6-го порядка, если раскладывать по одному или по двум столбцам, то получается верхняя оценка $6\cdot 48 = 9\cdot 2 \cdot 16 = 288$, однако если раскладывать по трём, то получается уже 192 (требует проверки, возможно недоперебрал в комбинаторике), 160 вроде реализовал (тоже надо проверить - в арифметике запросто могу накосячить, особенно если числа маленькие).

[Руст]

Да, похоже, это не максимальное значение детерминанта. У меня были некоторые соображения в пользу увеличения определителя при увеличении размерности. Такой определитель действительно существуети растёт примерно как $4^n/n^2$, однако это не максимальное значение.

[bot]

Похоже, тяжёлая задача. Друг против друга работают два фактора:
1) Верхняя оценка. Оптимально её получать по Лапласу, раскладывая по половине строк.
2) Реализуемость верхней оценки. Имхо, она должна падать - становится тесно и труднее подбирать к каждому ненулевому минору дополнительный ненулевой с соответствующим знаком.
Если для 6-го будет 160 (или 192), то отбрасывая заведомо присутствующий множитель $2^{n-1}$ и начиная с n=3, получим последовательность:
1,2,3,5(или 6)...
Пожалуй, 6 слишком прытко было бы, но уже точно не 4. Вот реализация 160 (или -160, не следил за знаком при вычислении):
++++++
+++---
++-+--
+-++-+
+---++
+-+++-

[Руст]

Тут заходил разговор о верхней оценке. Оценка приведённая rashid ом фактический не отличается от тривиальной. Легко получается и такая: $det<(\sqrt n )^n=exp(\frac 12 n\ln n)$ (объём параллелипеда образованного n векторами длины rjhtym из n). Это почти корень квадратный от тривиальной). Я полагал, что рост только экспоненциальный. Сейчас думаю, что отличается от этой верхней на экспоненциальный, т.е примерно квадратный корень от n!.

[sonnawert]

bot писал(а):

Всё-таки прокосячил в реализуемости.
Итог: для четвёртого порядка верхняя оценка 16 реализуется:
++++
++--
+-+-
+--+

здесь можно было обойтись и таким образом
+++-
-+++
+-++
++-+
она тоже дает тот же рзултат...

Цитата:

Верхнюю оценку для пятого порядка пересчитал раскладывая по двум строкам: максимально возможно 6 ненулевых миноров в этих строках, отсюда получаем 6x2x4=48. Она тоже достигается:
+++++
+++--
++--+
+--+-
+-+-+

ее тоже можно выразит через диагональных элементов
-++++
+-+++
++-++
+++-+
++++-
седьмой у меня получилось 320
восьмой 768
вот таким образом
+++++++-
++++++-+
+++++-++
++++-+++
+++-++++
++-+++++
+-++++++
-+++++++....