Банк задач по математике

Задача 5.4.1

(1)(2)(3)

Найдите перманент матрицы

?

(1)

$\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ ;

(2)

$4 \times 4$ , у которой $k = 0,1,2,3,4$ диагональных элементов — нули, а все остальные (в том числе недиагональные) элементы — единицы;

(3)

$n \times n$ , у которой на диагонали нули, а вне диагонали — единицы.

Примечание.

?

Перманент квадратной матрицы $A = (a_{ij})$ размера $n \times n$ определяется формулой

\operatorname {Per}(A) := \sum _{\sigma \in \Sigma _{n}} \prod _{i=1}^{n} a_{i,\sigma (i)},

где $\Sigma_{n}$ есть множество всех перестановок $n$ -элементного множества.

Задача 5.4.2

Найдите перманент матрицы $m \times n$ , состоящей из одних единиц.

?

Примечание.

?

Подматрицей данной матрицы называется матрица, полученная из данной вычеркиванием некоторого количества строк и столбцов. Перманент прямоугольной матрицы $A$ определяется как сумма перманентов всех квадратных подматриц максимального размера. Или, формулой, при $m < n$

\operatorname {Per}(A) := \sum _{\sigma } \prod _{i=1}^{m} a_{i,\sigma (i)},

где сумма берётся по всем $m$ -элементным размещениям без повторений чисел от 1 до $n$ . При $m > n$ положим $\operatorname {Per}(A) := \operatorname {Per}(A^{T})$ .

Задача 5.4.3

(1)(2)

?

(1)

Перманент не меняется при перестановке строк.

(2)

Формула разложения по строке. Если $m \leqslant n$ , то для любого $i$

\operatorname {Per}(A) = \sum _{j=1}^{n} a_{ij}\operatorname {Per}(A_{ij}),

где $A_{ij}$ — матрица, получаемая из исходной вычеркиванием $i$ -й строки и $j$ -го столбца.

Задача 5.4.4

(1)(2)

?

(1)

Перманент матрицы $n \times n$ из нулей и единиц равен нулю тогда и только тогда, когда есть нулевая подматрица $s \times t$ , где $s+t = n+1$ .

(2)

Для любых $m \leqslant n$ перманент прямоугольной матрицы $m \times n$ из нулей и единиц равен количеству с.р.п. (п. 5.3) для системы из $m$ подмножеств множества $\left\{ 1,\ldots ,n\right\}$ , определяемых строками этой матрицы.