Задачка по Дискре-Линалу

Genmaximus

Дано:
1)Вектор из 0 и 1, в нем нечетное число 1.
2)Все вектора, полученные из исходного циклическими сдвигами
3)Все вектора различны.
Доказать:
Полученное множество векторов линейно независимо над полем Z_2.
Может кто-нибудь помочь?

iri3955

ой, здесь была лажа

Irenas

здесь тоже.

griz_a

Ну вообще-то ты навесил перестановку на все наши вектора, в том числе на векторы сдвига из начального.
Почему s_n(цикл(s_n^{-1} (1..1,0...=цикл(1...1,0...) - непонятно

Irenas

Да, неаккуратненько получилось.
Спасиб. Подумаю.

JuLsJuLs

такой определитель называется циркулянт, его можно явно посчитать (быстрее в гугле найдешь, чем я напишу)
потом надо подумать, почему это явное выражение не равно нулю

iri3955

1100000 +
100000110101 +
001101011000 +
011000001101 =
000000000000

margo11

как нашел? ручками или прогой?

iri3955

руками... Ежели внимательно посмотреть, то сумма первых двух - периодический вектор, с периодом, не равным 2 (ну, то есть, на равным 1/2 длины вектора дальше понятно.
Вообще, есть проще
111000
000111
011100
100011

Genmaximus

Спасиб.
Да, утверждение было неверным.
В общем случае задача такая - есть вектор и все его циклические сдвиги.
Нужно описать множество, получающееся линейными комбинациями из них.
Пока мне даже не очень понятно, на каком языке и с помощью какого аппарата можно его описать.

goga7152

В общем случае задача такая - есть вектор и все его циклические сдвиги.
Нужно описать множество, получающееся линейными комбинациями из них.
Пока мне даже не очень понятно, на каком языке и с помощью какого аппарата можно его описать.
Приходит в голову язык линейных представлений конечных групп (в данном случае циклических).

manggol

язык линейных представлений конечных групп
че то я сомневаюсь, что это кто-то делал для характеристики 2. Обычно над C или R берутся представления.

goga7152

че то я сомневаюсь, что это кто-то делал для характеристики 2
http://en.wikipedia.org/wiki/Modular_representation_theory

manggol

а интересно однако. Кстати там в тексте ближе к концу есть пара мест, потенциально полезных для вопроса топикстартера.

Hana7725

В общем случае задача такая - есть вектор и все его циклические сдвиги.
Нужно описать множество, получающееся линейными комбинациями из них.
Совсем не очевидно, что можно надеяться на сколько-нибудь явный ответ на такой общий вопрос. Рассмотрим более частный - когда все циклические сдвиги линейно независимы? Похоже, ситуация будет существенно зависеть от размерности n. Вероятно, имеет смысл рассматривать разбиение пространства на подмножества векторов, содержащих одинаковое количество единиц: циклические перестановки разбивают их на классы эквивалентности.
Гипотезы:
1) если у вектора четное число единиц, то сдвиги л.з.
2) для любого нечетного k<n найдется вектор с k единицами, чьи сдвиги л.н.
3) если n=2^m, то для любого нечетного k все векторы с k единицами дают л.н. сдвиги.
4) если n=3(2m+1 то все сдвиги векторов с k единицами будут л.н. только если k=1.
5) если n=6m, то все сдвиги векторов с k единицами будут л.н. только если k=1 или k=n-1.
Из гипотез 1) и 3) (если они верны) вытекает ответ на исходный вопрос в случае, когда n является степенью двойки. В других случаях ответ даже на вопрос когда *все* векторы с k единицами дают л.н. сдвиги будет более сложным.
Пока мне даже не очень понятно, на каком языке и с помощью какого аппарата можно его описать.

Рассмотрим кольцо [math]$A=\mathbb{Z}_2[x]/(x^n+1)$[/math], другими словами, будем рассматривать многочлены степени не выше n-1, а чтобы их
можно было умножать, положим [math]$x^n=1$[/math]. Сопоставим вектору [math]$a=(a_1,\ldots,a_n)\in \mathbb{Z}_2^n$[/math] многочлен [math]$p_a(x)=a_1+a_2 x+\ldots+a_{n}x^{n-1}$[/math]. Умножение [math]$p_a(x)$[/math] на [math]$x^k$[/math]соответствует циклическому сдвигу вектора [math]$a$[/math], умножение на многочлен - линейной комбинации сдвигов. Подпространству в [math]$\mathbb{Z}_2^n$[/math], порожденному циклическими сдвигами вектора [math]$a$[/math] будет соответствовать главный идеал [math]$Ap_a$[/math], порожденный многочленом [math]$p_a$[/math].
Оставить комментарий
Имя или ник:
Комментарий: