2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Простой определитель
Сообщение15.11.2013, 03:14 
Есть матрица 3x3. Каждый элемент матрицы может принимать значения $\pm 1$. Чему равен $\max{\Delta}$ (наибольший детерминант такой матрицы)? Задача легкая и решена у того же Проскурякова, мне интересно есть ли у данной задачи формальное решение? Вообще есть ли формальные методы как решать такие задачи? Если нет, то есть ли методы, которые позволяют определить, что формальных методов решения нет? Вопрос, наверное, глупый, но я что-то не могу понять.

 
 
 
 Re: Простой определитель
Сообщение15.11.2013, 03:18 
Аватара пользователя
Вот вам ну очень формальный метод. Вычисляем 512 возможных определителей и находим наибольший. Или чего вы хотели?

 
 
 
 Re: Простой определитель
Сообщение15.11.2013, 03:40 
Так то-ж перебор.
Ну я понимаю, что сам не до конца понимаю, чего хочу, ну давайте я так попробую изложить вопрос:
Вот вы говорите, что надо перебрать 512 вариантов; это дело, конечно, хорошее. Но никто же так решать не станет. Мы с вами знаем (доагдываемся), что, к примеру, определитель не будет равен 6, знаем также, что, если все элементы будут либо $+1$, либо $-1$, то мы явно максимум не получим. Вот можно как-то эти наши соображения формализовать, чтобы потом применять на более общие случаи?
Пока оптимальное решение выглядит так: доказать, что определитель не может быть равен 6. Потом доказать, что определитель не равен 5, потом легко находиться хоть один, который равен 4, вот и ответ. Но может есть какие-то другие, более "находчивые" соображения?

 
 
 
 Re: Простой определитель
Сообщение15.11.2013, 05:21 
Можно сделать Gaussian elimination по первой колонке. Это сильно уменьшит набор возможных значений определителя. Довольно легко показать, что два крайних значения недостижимы.

 
 
 
 Re: Простой определитель
Сообщение15.11.2013, 05:35 
Аватара пользователя
GAttuso в сообщении #788812 писал(а):
Пока оптимальное решение выглядит так: доказать, что определитель не может быть равен 6. Потом доказать, что определитель не равен 5, потом легко находиться хоть один, который равен 4, вот и ответ.


По мне так это и есть оптимальное решение, учитывая, что для доказательства невозможности 6 и 5 достаточно соображений четности.

 
 
 
 Re: Простой определитель
Сообщение15.11.2013, 07:53 
Аватара пользователя
Мне понравилась идея venco. Если сложением/вычитанием сделать нули в первом столбце, сразу видно, что определитель делится на 4. Ну, а больше 6 он быть не может.

 
 
 
 Re: Простой определитель
Сообщение15.11.2013, 08:37 
Аватара пользователя
Было

 
 
 
 Re: Простой определитель
Сообщение15.11.2013, 13:31 
Всем спасибо за мысли (и ссылки).
По ссылке как раз обсуждается случаи матрицы nxn. Попробую сперва сам пободаться обобщив какие-нибудь из предложенных методов, а потом гляну, что предлогали местные гуру. :D

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group