CD
Ну или делению, видимо, если в другую сторону
Size: a a a
2020 June 10
МК
Там тот самый кортеж приходит коэффициентами, а сдвиг соответствует умножению на x с последующим возвращением к вычетам mod многочлен
честно говоря, сложновато понять это. Попробую завтра на свежую голову)
МК
Ещё раз спасибо, вы мне очень сильно помогли!
CD
честно говоря, сложновато понять это. Попробую завтра на свежую голову)
ну вот может так будет понятнее - этот самый X многочлена соответствует оператору смещения последовательности на 1
CD
P(X) = 0 соответствует рекуррентному соотношению
CD
соответственно, X^n mod P(X) будет соответствовать выражению n-ного элемента последовательности через начальные
CD
потому что X^n - blablabla = 0 (считая P(X) = 0)
CD
честно говоря, сложновато понять это. Попробую завтра на свежую голову)
это вообще достаточно универсальная математическая идея, например, самую обычную квадратную матрицу над C (выражающую линейный оператор!) можно рассматривать как корень обнуляющего её многочлена (совершенно случайно это окажется характеристический многочлен :) ) и дальше факторизовать этот многочлен, получив жорданову нормальную форму
mq
это вообще достаточно универсальная математическая идея, например, самую обычную квадратную матрицу над C (выражающую линейный оператор!) можно рассматривать как корень обнуляющего её многочлена (совершенно случайно это окажется характеристический многочлен :) ) и дальше факторизовать этот многочлен, получив жорданову нормальную форму
кстати, а вообще у полинома может быть много матриц-корней?
mq
ну типа я не знаю, я хочу посмотреть на множество { s \in M_4(C) | s^3 + 14 s^2 - 12 s + 228 = \mathcal{O} }
CD
кстати, а вообще у полинома может быть много матриц-корней?
хм... кажется очевидно, что он определит только набор собственных значений
mq
хм... кажется очевидно, что он определит только набор собственных значений
а, ну да, любая подобная будет корнем тоже
mq
окей а если профакторизовать по подобию
CD
а, ну да, любая подобная будет корнем тоже
и не подобная
CD
(x-1)^2 может быть двумя, а может быть одним и присоединенным
V🇺
кстати, а вообще у полинома может быть много матриц-корней?
CD
окей а если профакторизовать по подобию
(x-1)(x-1) может нулить подпространство размера 2 сразу, а может размера 1 нулить и размера 1 отображать в то, что потом занулит
CD
это, видимо, соответствует существованию двух неизоморфных абелевых групп размера p^2, но я не настоящий алгебраист
ВВ
Я теперь получил систему уравнений и решаю её, получаю х1 = .. , х2 = .. , вот в первой системе х1 = 1 и х2 = 1 , остальные = 0. Только при составлении функции получается + 1 какой-то, не могли бы вы подсказать откуда он там берётся?
Можно записать матрицу (m+1)×(m+1), которая одно состояние регистра и выходной ячейки переводит в другое. В матрице будет смещённая на одну позицию главная диагональ (это сдвиг) и строчка из коэффициентов (это вычисление нового элемента). Это если у нас состояние — вектор-столбец. Характеристический многочлен для такой матрицы будет иметь вид x1 x^m + x2 x^(m-1) + ... + xm x + 1, где xi — это коэффициенты. Коэффициенты находим из системы, там только x1 и x2 (соответствующие x^5 и x^4) ненулевые, а единичка она уже в многочлена была. Вот и получается x^5 + x^4 + 1.
CD
Можно записать матрицу (m+1)×(m+1), которая одно состояние регистра и выходной ячейки переводит в другое. В матрице будет смещённая на одну позицию главная диагональ (это сдвиг) и строчка из коэффициентов (это вычисление нового элемента). Это если у нас состояние — вектор-столбец. Характеристический многочлен для такой матрицы будет иметь вид x1 x^m + x2 x^(m-1) + ... + xm x + 1, где xi — это коэффициенты. Коэффициенты находим из системы, там только x1 и x2 (соответствующие x^5 и x^4) ненулевые, а единичка она уже в многочлена была. Вот и получается x^5 + x^4 + 1.
Мне не нравится переход через матричные представления, потому что они крякают как следствия одной причины, а не матричные крякают как базовое