Недавно появилось желание вернуться к старой проблеме. А именно найти определитель матрицы но не рекурсивно, а грубо говоря с помощью цикла. Пока идея у меня такова, только как ее реализовать, хотя вроде бы все кажется и очевидно, я не знаю:

Имеем матрицу (к примеру 5х5):
+++++
+++++
+++++
+++++
+++++


необходимо сначала перебрать все миноры (обозначены ноликами) размерностью 3х3, чтобы вычислить определитель первого минора рангом 3+1 то есть:
+++++ +++++ +++++ +++++
+++++ ++ooo ++ooo ++ooo
++ooo +++++ ++ooo ++ooo
++ooo ++ooo +++++ ++ooo
++ooo ++ooo ++ooo +++++

потом для второго минора рангом 3+1

+++++ ++ooo ++ooo ++ooo
+++++ +++++ +++++ +++++
++ooo +++++ ++ooo ++ooo
++ooo ++ooo +++++ ++ooo
++ooo ++ooo ++ooo +++++

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

и соответственно

1
0
1
1
1

На первый взгляд все просто, но если ранг исходной матрицы сделать >5, то вычисление новых значений вектора "затенения" у меня вызывает проблемы.

Может кто со свежей головой подкинет пару толковых идей, о том как вычислять вектор?

Это сообщение отредактировал(а) Royan - 14.5.2004, 14:23

Очень хочется спросить - а зачем? не нравится рекурсия - приводи матрицу к диагональному виду...

обычно используется процедура Гаусса

обычно, чтобы избавиться от рекурсии, я имитирую стек вызовов собственным стеком,
т.е. берешь свою рукурсивную функцию и вместо вложенных вызовов складываешь текущую
подматрицу (или структури описывающую эту подматрицу ссылаясь на исходную) в стек,
ну и конечно нужно предусматреть спуск по стеку вызовов, вот и все. Хотя наверное можно обойтись без этого, через циклы, но все равно в принципе получится то же самое алгоритм
вычисления через определители рекурсивный.

Просто идея в голове родилась и захотелось воплотить ее в жизнь, просто таким алгоритмом можно будет раскрутить матрицу практически любой размерности

можно конечно пользоваться и рекурсивным, но его сложность порядка n!, а сложность Гаусса порядка n^3

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

PS Умные учебники по алгебре у меня, к сожалению, вывелись
PPS Пробовал найти инфу на сайтах приведенных в топике "Прежде чем изобретать велосипед" но тоже ни фига не нашел, хотя может плохо искал...

на форуме был не один вопрос по этой теме
кратко можно описать так:
определитель матрицы не изменится, если к строке прибавить другую строку, умноженную на какое-нибудь число
берут первую строку и прибавляют ее к остальным с такими множителями, чтобы в первом столбце получались нули
вот и получается первый столбец с одним единственным ненулевым коэффициентом на первом месте
на это тратится порядка n*n операций
во втором столбике оставляется ненулевой коэффициент на втором месте, и т.д. для всех n столбцов, получается порядка n*n*n операций...

Есть очень простой алгоритм, который просто нужным образом ставит перестановки.
Припишем к исходной матрице n*n снизу еще 1 такую же матрицу. получится матрица n*2n
Теперь давайте. Давайте пойдем по первому столбцу вниз перемножая Элементы стоящие на диагоналях получившейся матрицы(начиная с главной) до последнего элемента исходной матрицы. Получившиеся произведения сложим. Теперь возьмем последний столбец и пойдем вниз но уже влево также перемножая элементы и складвывая произведения. Вычтем из первой суммы вторую получим определитель. Почему-то начиная с матриц 3*3 этот алгоритм работает.Сложность 2*sqrt(2)*n*n

Цитата

Почему-то начиная с матриц 3*3 этот алгоритм работает.Сложность 2*sqrt(2)*n*n

такое ощущение, что на матрицах 3*3 его корректная работа и заканчивается...
порисовал немного для матрицы 4*4
не нашел такой перестановки: (1,1) (2,3) (3,2) (4,4)

Х.з. я когда развлекался с ним просто создавал матрицы произвольного разменра(с разными слуайными числвами) и считал их с помощью гаусса и этой хрени, получалось что сходятся. Мой друган пытался это доказать, что-то у него получилось, но м.б. он просто ХОТЕЛ, чтобы у него чего-то получилось....вообщем у меня он пока работал, а так...

Цитата

Давайте пойдем по первому столбцу вниз перемножая Элементы стоящие на диагоналях получившейся матрицы(начиная с главной) до последнего элемента исходной матрицы

Я наверно тупой но я не понял эту фразу, то есть например имеем:

a++++ |
+a+++ |
++a++ | - матрица А
+++a+ |
++++a |

b++++ |
+b+++ |
++b++ |- ее дубликат, назовем её А'
+++b+ |
++++b |

То есть получили a*b + a*b + a*b + a*b + a*b

а далее как идти вниз?

не совсем
a_1 a_2 a_3 a_4
a_5 a_6 a_7 a_8
a_9 a_10 a_11 a_12
a_13 a_14 a_14 a_16
b_1 b_2 b_3 b_4
b_5 b_6 b_7 b_8
b_9 b_10 b_11 b_12

p_1=a_1*a_6*a_11*a_16
p_2=a_5*a_10*a_14*b_4
p_3=a_9*a_14*b_3*b_8

а тот факт, что ты забил только три строки матрицы b_N это так и задумано или все-таки надо все четыре?

Нет, надо, конечно все 4
и еще 4 с другого бока