Преобразование матрицы к треугольному виду

Здравствуйте, возникла нестандартная задача: преобразовать матрицу (разреженную) к треугольному виду (все ненулевые элементы поместить на и под диагональ), только переставляя строки и столбцы, математические операции недопустимы, следовательно обратный ход метода Гаусса тоже. Важное условие - диагональ должна быть ненулевая после преобразования, также существует некое окаймление, то есть минимум 1 столбец справа после нулей может быть ненулевым. Матрицу привел в виду: строки по возрастанию кол-ва эл-тов сверху вниз, столбцы по убыванию слева направо, то есть большинство эл-тов уже находится под диагональю. Поделитесь мыслями как можно реализовать. Дополнительные условия: эл-ты на диагонали должны быть максимальные по модулю, матрица записана в списочном виде, то есть нули не хранятся.

Добавлено через 4 часа 55 минут
Хотя бы просто к треугольному виду, но перестановками строк и столбцов.

1

Мне кажется, что без математических операций ничего не получится.
Однако можно (вероятно) заполнить диагональ максимальными по
модулю элементами.
Вот алгоритм:
1) в матрице n*n находится максимальный по модулю элемент
(параллельно и его индексы)
2) с помощью перестановок строк и столбцов (порядок не важен)
этот элемент помещается в самый верх (начало) диагонали
3) игнорируя первую строку и первый столбец рассмотрим
матрицу размера (n-1)*(n-1) и находим в ней наибольший по модулю
элемент.
4) с помощью перестановок столбцов и строк помещаем его на
диагонали второй строки и второго столбца
5) далее имеем матрицу уже размера (n-2)*(n-2)
6) и в ней находим максимальный по модулю элемент, который
перемещаем на очередное место диагонали
7) и т.д.
8) последний n-ый элемент перемещать никуда не надо.
он будет занимать своё место в конце диагонали и быть
максимальным по модулю, ибо он единственный (иных нет)!!
Примечание:
Заполнить полматрицы нулями
будет возможно только в том случае,
если будут разрешены операции со строками (умножение, вычитание ...)

0

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

1

Мне очень хочется уточнить ваше последнее предложение.
Я сформулирую его в виде простого вопроса:
Дана квадратная матрица, у которой есть 4 максимальных
элементов. Положим, что все элементы равны 10 и они
располагаются в четырёх углах матрицы. Как бы мы не
переставляли столбцы и строки все угловые элементы
не уйдут на диагональ. Они будут ходить по периметру.
Как поступить в этом случае? (если я вас правильно понял)??
Или не понял вовсе??

0

Если они стоят в углах, ставить на диагональ уже не нужно, как-то трудновато выявить максимальный элемент среди равных...

1

Я попробовал хотя бы частично проанализировать вашу задачу.
Без этого мы просто зайдем в тупик.
1) если дана матрица размером n*n , то в качестве необходимого условия
для преобразования ее к треугольному виду должно быть наличие в этой
матрице необходимого числа нулей, как минимум: n(n-1)/2 нулей.
2) для матрицы 2*2 одного нуля вполне достаточно, а вот два нуля
могут сделать задачу неразрешимой (или решённой)!!
3) в общем случае для разрешимости задачи необходимо, чтобы детерминант
(определитель) матрицы был отличен от нуля, в противном случае задача
неразрешима
4) вывод: решение этой задачи зависит от вида матрицы
5) вывод2: если эта задача имеет решение, то можно попробовать
написать программу, которая методом перебора найдёт решение
либо докажет, что такого решения нет.
Вот пожалуй и все, что я хотел сказать
P.S.
Программа самое верное, особенно для небольших матриц.

0

Сообщение от xod Дана квадратная матрица, у которой есть 4 максимальных элементов. Положим, что все элементы равны 10 и они располагаются в четырёх углах матрицы.

Либо я условие не понимю, либо почему не так?

1

Понимаете в чем дело, вашу задачу с преобразованием матрицы
легко связать с разрешимостью системы n линейных уравнений
с n неизвестными. А последнее в свою очередь тесно связано с
определителем матрицы. В линейной алгебре доказывается, что
если определитель матрицы равен 0, то превратить ее в треугольный
вид с ненулевой диагональю неудастся. А если определитель не
равен 0. То вам может повезти. (я уверен вы знаете метод Гауса)
Правда в вашей задаче должно быть достаточное количество нулей.
Это не гарантия успеха, но это необходимое условие. Вы можете
сами это проверить расчетами. Например возьмём матрицу
порядка 5. Количество вариантов для перестановки строк =5! (факториал)
столько же и для столбцов. Итого 5!*5! вариантов. Но для построения
Вашей матрицы, а это (25 - 5)/2 =10 нулей, для которых потребуется
10! вариантов. 10! > 5!*5! - вот и сделайте вывод.
Вывод:
в общем случае ваша задача неразрешима
Конечно интересно изучить эту задачу, да вот нет времени ... Увы!
Удачи вам!

0

Сообщение от xod В линейной алгебре доказывается, что если определитель матрицы равен 0, то превратить ее в треугольный вид с ненулевой диагональю неудастся.

Что-то тут не тою Вот матрица, определитель 0, главная диагональ ненулевая:
Вероятно, имелось в виду что невозможно привести к треугольной матрице, у которой все элемнты на главной диагонали отличны от 0? Тогда да, но ведь это не требуется.

Добавлено через 2 минуты

Сообщение от xod в общем случае ваша задача неразрешима

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

1

значит я решил неразрешимую задачу...

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

0

Сообщение от ExFau$t иначе нет смысла ставить задачу о ненулевой диагонали

Что такое ненулевая диагональ? Когда все элементы отличны от нуля или когда хотя бы один элемент отличен от 0?

1