определители {0,1}-матриц и {-1,1}-матриц

[maxal]

Задачка от green5, кто так и не удосужился привести свое сообщение в надлежащий вид.

Пусть $N(n,k)$ равно количеству $n\times n$ $\{0,1\}$-матриц с определителем $k$.
Пусть $M(n,k)$ равно количеству $n\times n$ $\{-1,1\}$-матриц с определителем $k$.

Докажите, что для каждого целого $n\geq 2$ и целого $k$ выполняется тождество:

$$2^{2n+1} N(n,k) = M(n+1,2^n k).$$

[Профессор Снэйп]

Назовём матрицу размера $(n+1) \times (n+1)$ особой, если у неё все элементы первой строки равны $1$, а все элементы первого столбца, не лежащие в первой строке, равны $-1$.

Пусть $A = (a_{i,j})_{1 \leqslant i,j \leqslant n}$ --- $\{ 0,1 \}$-матрица размера $n \times n$ с определителем $k$. Тогда $2A = (2a_{i,j})_{1 \leqslant i,j \leqslant n}$ --- $\{ 0,2 \}$-матрица размера $n \times n$ с определителем $k$. Пусть теперь $B = (b_{i,j})_{1 \leqslant i,j \leqslant n+1}$ --- такая матрица размера $(n+1) \times (n+1)$, что

$$ b_{i,j} = \begin{cases} 2a_{i-1,j-1}, & i,j > 1; \\ 1, & i = 1; \\ 0, & i > 1, j = 1 \end{cases} $$

для всех $i$, $j$ от $1$ до $n+1$. Пусть, наконец, матрица $C$ получается из матрицы $B$ вычитанием первой строки из всех остальных строк.

Ясно, что $C$ --- особая $\{ -1, 1 \}$-матрица размера $(n+1) \times (n+1)$ и что $\mathrm{det}(C) = \mathrm{det}(B) = \mathrm{det}(2A) = 2^n k$. Легко проверить, что отображение $A \mapsto 2A \mapsto B \mapsto C$ является биекцией множества $\{ 0, 1 \}$-матриц размера $n \times n$ на множество особых $\{ -1,1 \}$-матриц размера $(n+1) \times (n+1)$. Таким образом, количество особых $\{ -1,1 \}$-матриц размера $(n+1) \times (n+1)$ с определителем $2^n k$ равно $N(n,k)$.

А вот дальше начинается какая-то мура... Написал много букафф и всё стёр, поскольку вывод не сходится с точностью до множителя $2$. На мой взгляд, правильное равенство такое:

$$ 2^{2n} N(n,k) = M(n+1, 2^n k) $$

при всех $n \geqslant 1$. При $n=1$ оно очевидно, при $n = 2$ посчитать конкретные количества вручную уже трудно, надо прогу писать... Кому не лень, посчитайте, пожалуйста! По моему, green5 где-то ошибся в расчётах для $n=3$, а maxal ему совершенно напрасно поверил

Если ошибка действительно обнаружится, изложу свои выкладки. Если же нет, то буду искать ошибку у себя...

[maxal]

Профессор Снэйп
Я проверял численно вплоть до $n=4$.

-- Wed Sep 22, 2010 11:36:13 --

Вот значения $N(n,k)$:
$n=2$: 3, 10, 3 ($-1\leq k\leq 1$)
$n=3$: 3, 84, 338, 84, 3 ($-2\leq k\leq 2$)
$n=4$: 60, 1200, 10020, 42976, 10020, 1200, 60 ($-3\leq k\leq 3$)
$n=5$: 3600, 43560, 144720, 1213920, 4851360, 21040112, 4851360, 1213920, 144720, 43560, 3600 ($-5\leq k\leq 5$)
Центальные элементы $N(n,0)$ образуют последовательность A046747, а соседние с ними $N(n,1)$ - последовательность A086264.

А вот значения $M(n,k)$:
$n=2$: 4, 0, 8, 0, 4 ($-2\leq k\leq 2$)
$n=3$: 96, 0, 0, 0, 320, 0, 0, 0, 96 ($-4\leq k\leq 4$)
$n=4$: 384, 0, 0, 0, 0, 0, 0, 0, 10752, 0, 0, 0, 0, 0, 0, 0, 43264, 0, 0, 0, 0, 0, 0, 0, 10752, 0, 0, 0, 0, 0, 0, 0, 384 ($-16\leq k\leq 16$)
$n=5$: 30720, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 614400, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5130240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22003712, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5130240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 614400, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 30720 ($-48\leq k\leq 48$)

Здесь центральные элементы $M(n,0)$ образуют последовательность A057982.

Например, для $n=3$ и $k=0$ тождество $2^{2n+1} N(n,k) = M(n+1,2^n k)$ приобретает вид:

$$2^7\cdot 338 = 43264.$$

[Профессор Снэйп]

maxal в сообщении #355184 писал(а):

Я проверял численно вплоть до .

Да, прошу прощения. Я понял, где я ошибся

Как только пустят за компьютер, напишу решение...

[Профессор Снэйп]

Короче, как-то так...

Пусть $N(n, \pm k)$ обозначает количество $\{ 0, 1 \}$-матриц размера $n \times n$, определитель которых равен $k$ или $-k$. Аналогично $M(n+1, \pm 2^n k)$. Пусть $M_{\pm 2^n k}$ обозначает множество матриц, количество элементов которого обозначает величина $M(n+1, \pm 2^n k)$.

Выше мы показали, что количество особых матриц из $M_{\pm 2^n k}$ совпадает с $N(n, \pm k)$.

Пусть $\mathcal{D}$ --- множество диагональных матриц размера $(n+1) \times (n+1)$, у которых все диагональные элементы равны $\pm 1$. Ясно, что если $B \in M_{\pm 2^n k}$ и $U, V \in \mathcal{D}$, то $UBV \in M_{\pm 2^n k}$.

Определение. Матрицы $A, B \in M_{\pm 2^n k}$ эквивалентны, если существуют $U, V \in \mathcal{D}$, такие что $A = UBV$.

Лемма 1. Введённое отношение действительно является эквивалентностью на $M_{\pm 2^n k}$.

Доказательство. Проверяем рефлексивность, симметричность, транзитивность... $\qed$

Лемма 2. Каждый класс эквивалентности содержит ровно $2^{2n+1}$ элементов.

Доказательство. Ясно, что $\mathcal{D}$ состоит из $2^{n+1}$ элементов. Пусть $B \in M_{\pm 2^n k}$. Класс эквивалентности, содержащий $B$, является множеством элементов последовательности $\{ UBV \}_{U, V \in \mathcal{D}}$, содержащей $2^{2n+2}$ членов. Нам достаточно показать, что каждый представитель класса повторяется в последовательности ровно $2$ раза.

Пусть $UBV, U'BV'$ --- равные элементы последовательности. Расписывая произведение матриц покомпонентно, видим, что $u_{i,i} b_{i,j} v_{j,j} = u'_{i,i} b_{i,j} v'_{j,j}$ при всех $i$, $j$ от $1$ до $n+1$. Так как матрица $B$ не содержит нолей, то $u_{i,i} v_{j,j} = u'_{i,i} v'_{j,j}$ при всех $i$, $j$. Отсюда либо $U = U'$ и $V = V'$, либо $U = - U'$ и $V = - V'$. $\qed$

Лемма 3. Каждый класс эквивалентности содержит ровно одну особую матрицу.

Доказательство. Существование. Пусть $B \in M_{\pm 2^n k}$. Положив $v_{j,j} = b_{1,j}$, $u_{1,1} = 1$ и $u_{i,i} = - b_{i,1} b_{1,1}$ для всех $j \in \{ 1, \ldots, n+1 \}$ и $i \in \{ 2, \ldots, n+1 \}$, получим особую матрицу $UVB$.

Единственность. Пусть $A, B \in M_{\pm 2^n k}$ --- особые матрицы и $A = UBV$ для некоторых $U, V \in \mathcal{D}$. Тогда $u_{1,1} v_{j,j} = 1$ и $u_{i,i} v_{1,1} = 1$ для всех $i,j \in \{ 1, \ldots, n+1 \}$. Отсюда либо $U = V = E$, либо $U = V = -E$. В любом случае $A = B$. $\qed$.

Следствие. $2^{2n+1} N(n,\pm k) = M(n+1, \pm 2^n k)$.

Теперь если $k = 0$, то всё уже доказано. Если же $k \neq 0$, то нужно заметить, что $M(n+1, 2^n k) = M(n+1, \pm 2^n k)/2$ и $N(n,k) = N(n, \pm k)/2$ (Последнее равенство не выполняется при $n = 1$ ). Это просто. Переставляем, к примеру, местами первую и вторую строку матрицы, определитель меняет знак. Так как этот определитель ненулевой, то строки не могут совпадать.

[green5]

Хмм, клево но непонятно
Я както по $ det \left( \begin{array} {cc} A B \\ C D \end{array} \right) = det(A)*det(D-B* \frac{1}{A} * C) $

[Профессор Снэйп]

green5 в сообщении #356808 писал(а):

Я както по $ det \left( \begin{array} {cc} A B \\ C D \end{array} \right) = det(A)*det(D-B* \frac{1}{A} * C) $

Що це за хрень и как её применять к этой задаче?

[green5]

Ну не знаю, а ВЫ знаете
Как не так maxal определил задачу

[Профессор Снэйп]

green5 в сообщении #362521 писал(а):

Ну не знаю, а ВЫ знаете
Как не так maxal определил задачу

Да вроде maxal всё грамотно сформулировал.