2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 вырожденные циркулянты из +/-1
Сообщение02.10.2008, 05:08 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение03.10.2008, 06:36 
Модератор
Аватара пользователя


11/01/06
5710
Задача 2. Докажите, что для простого $p>3$ количество вырожденных циркулянтов порядка $3p$ с элементами $\pm 1$ равно в точности $$2\cdot 3^p + \sum_{k=0}^p {p\choose k}^3.$$

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

 Профиль  
                  
 
 
Сообщение05.10.2008, 08:22 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение05.10.2008, 08:26 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение05.10.2008, 14:11 
Заслуженный участник


08/04/08
8562
По задаче 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$ матриц.
Как доказать, что других нет, пока не понял.

 Профиль  
                  
 
 
Сообщение05.10.2008, 20:01 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение07.10.2008, 09:50 
Заслуженный участник


09/02/06
4401
Москва
Если смотреть на ссылку, то определить разлагается в произведение. Соответственно хотя бы один из множителей равен нулю. А это возможно только в случае, когда
(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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group