LecturesCMC/PythonIntro2019/Homework_DodgsonDet

Ввести квадратную целочисленную матрицу построчно и посчитать её определитель (например, методом конденсации Доджсона). Размер матрицы (1<N<14) определяется длиной её нулевой строки. Описание предлагаемого метода в подсказках. Пользоваться numpy нельзя:)

Сам метод хорошо описан в Википедии. Приведём слегка модифицированный вариант. Будем строить матрицу ${\displaystyle A\prime }$ размера ${\displaystyle n-1\times n-1}$ из матрицы ${\displaystyle A}$ размера ${\displaystyle n\times n}$ таким образом, что каждый её элемент равен определителю минора второго порядка строк ${\displaystyle 0}$ и ${\displaystyle j+1}$ и столбцов ${\displaystyle 0}$ и ${\displaystyle i+1}$ матрицы ${\displaystyle A}$, т. е.

${\displaystyle A{\prime }_{i,j}=det\left(\left[\begin{array}{cc}{A}_{0,0}& A_{0,i+1}\\ A_{j+1,0}& A_{j+1,i+1}\end{array}\right]\right)}$

Согласно алгоритму Доджсона, элементы матрицы ${\displaystyle A\prime {\prime }_{i,j}}$ надо поделить на соответствующие внутренние элементы матрицы ${\displaystyle A_{i+1,j+1}}$. В нашем случае делить надо всегда на ${\displaystyle A_{0,0}}$, так что можно посчитать определитель ${\displaystyle A\prime \prime }$, а потом уже поделить на ${\displaystyle {\left(A_{0,0}\right)}^{n-2}}$. Таким образом, на каждом шаге конденсации мы накапливаем общий делитель ${\displaystyle D={\left(A_{0,0}\right)}^{n-2}\cdot {\left(A{\prime }_{0,0}\right)}^{n-3}\cdot {(A\prime {\prime }_{0,0})}^{n-4}\cdot ...}$, а на последнем шаге (когда размерность матрицы становится ${\displaystyle 1\times 1}$) делим ${\displaystyle A{\prime }^{\dots }{\prime }_{0,0}}$ на ${\displaystyle D}$.

Кроме того, исходный алгоритм Доджсона предписывает переставлять строки, если какой-то внешний элемент оказался нулевым. В нашем варианте алгоритма достаточно поддерживать ${\displaystyle A{\prime }^{\dots }{\prime }_{0,0}\ne 0}$, то есть переставлять в матрице строки до тех пор, пока угловой элемент не окажется ненулевым (если таких нет, определитель 0). Не забываем о знаке определителя при перестановке строк (иногда его надо менять)!

8, 8, 5, 6, 3
1, 4, 4, 9, 0
9, 6, 7, 7, 3
4, 1, 0, 1, 4
6, 7, 9, 7, 3

2784

Для проверки правильности можно воспользоваться модулем numpy (предположим, матрица Array хранится в виде списка списков):

   1 import numpy
   2 print(numpy.linalg.det(numpy.array(Array)))

Да, с модулями в Ptyhon жизнь становится намного проще . Но наша цель — учёба, а не лёгкая жизнь.

CategoryHomework