вырожденные циркулянты из +/-1

[maxal]

Задача 1. Докажите, что для простого $p>2$ количество вырожденных циркулянтов порядка $2p$ с элементами $\pm 1$ равно в точности

$$2{2p\choose p}.$$

[maxal]

Задача 2. Докажите, что для простого $p>3$ количество вырожденных циркулянтов порядка $3p$ с элементами $\pm 1$ равно в точности

$$2\cdot 3^p + \sum_{k=0}^p {p\choose k}^3.$$

Задача 3. Обобщите результат до $n$ свободных от квадратов - выведите и докажите формулу для числа вырожденных циркулянтов такого порядка.

[Руст]

maxal, ты бы лучше вначале дал определение, что такое циркулянты. Что то примоминаю, что это матрицы имеющие одинаковые элементы по диагонали. Не помню, имеющиее одинаковые элементы на неглавных (косял) диагонали считаются ли циркулянтами. Иногда ещё используют чтобы все элементы $a_{ij}$ одинаковы, если $i=j\mod n$, n - порядок (размер n*n) матрицы.

[maxal]

Циркулянт - это матрица, где каждая следующая строка является циклическим сдвигом предыдущей. Подробности здесь:
http://mathworld.wolfram.com/CirculantMatrix.html
http://mathworld.wolfram.com/CirculantDeterminant.html

[Sonic86]

По задаче 1.
Что понимается под циркулянтами? Определители матриц вида $(a_{i,j})$, где
$a_{i,j}=a_{(j-i) \mod n}$, n - порядок матрицы?
В этом случае у меня получилось $C_{2p}^p$ матриц, в которых количество 1 и -1
в первой строке равны, а также $C_{2p}^p$ матриц, в которых в первой строке
количество 1 (ну и -1) на четных местах, равно количеству 1 (ну и -1) на нечетных местах.
Т.е., если $x=(x_1, x_2, ..., x_{2p})$ - первая строка, то определитель равен 0 в 2-х случаях:
1. $\sum\limits_{j=1}^{2p} x_j =0$
2. $\sum\limits_{j=1}^{p} x_{2j-1} = \sum\limits_{j=1}^{p} x_{2j-1}$
Случаи 1 и 2 совместимы только при $x_j = const$ - в 2-х случаях. Так что у меня всего
$2C_{2p}^p - 2$ матриц.
Как доказать, что других нет, пока не понял.

[maxal]

Sonic86 писал(а):

Случаи 1 и 2 совместимы только при $x_j = \const$ - в 2-х случаях. Так что у меня всего
$2C_{2p}^p - 2$ матриц.
Как доказать, что других нет, пока не понял.

Ну для начала все-таки убедитесь, что случаи 1 и 2 на самом деле несовместимы. А вот в доказательстве, что других нет, и состоит вся соль задачи.

[Руст]

Если смотреть на ссылку, то определить разлагается в произведение. Соответственно хотя бы один из множителей равен нулю. А это возможно только в случае, когда
(1) $\sum_{i=0}^{n/d-1}x_{r+id} =a$
не зависит от $r=0,1,..,d-1$, (здесь d делитель n) в случае d=1 он равен 0.
Если равенство выполняется одновременно для двух делителей d, то оно выполняется и для lcm. Если выполняется для степени некоторого простого числа, то выполняется и для этого простого делителя. Поэтому достаточно ограничиваться с простыми делителями и для 1. Когда $x_i=\pm 1$ несложно просчитывается количество решений.
В первой задаче $d=1$ дает $C_{n}^{n/2}$ решений, $d=2$ дает $x_1+x_3+...=x_2+x_4+...$.
Количество решений (1) при $x_i=\pm 1$ получается $\sum_{k=0}^{n/d}(C_{n/d}^k)^d$.
При d=2 это опять $C_{n}^{n/2}$ и для нечётного $n/2$ решения из $d=1$ и $d=2$ (с $x_i=\pm 1$) не пересекаются. Случай делителя $p$ в первой задаче дает решения d=1 при $a=0$ или решения $d=2$ при $a\not =0$.