ny_quant

N delitsya na tri?

From:

Правильно. Чуть позже расскриню решение. Если не трудно, пока что напишите своё.

From:

First the size needs to be divisible by 3.
All eigenvalues of A are roots of the polynomial x^3+x+1=0
det A is the product of eigenvalues. It is not hard to see that the only way for it to be rational is for eigenvalues to go in triples.

On the other hand it is not hard to construct a matrix of size 3 (hence any size divisible by three):
0 -1 -1
1 0 0
0 1 0
(from the recursive equation).

Spasibo, zabavnaya zadacha.

From:

Chut' pogoryachilsya. It is intuitively clear that eigenvalues go in triples, but i would have to see how to formulate the exact argument. Chto-to is teorii Galois, kazhetsya.

From:

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

From:

I think the following is true:

if P is any polynomial of three variables, P of the roots is rational if and only if it is contained in the algebra generated by the three symmetric polynomials x_1+x_2+x_3, x_1x_2+x_2x_3 + x_1 x_3 and x_1 x_2 x_3 (corresponding to the coefficients of the cubic). Since det is a product of the roots it needs to be a power of x_1 x_2 x_3

It's been a long time since i studied these things :)

From:

Я, к сожалению, вообще этого не проходил, поэтому торможу по полной :(

Когда Вы говорите "P of the roots", Вы имеете подстановку трёх собственных чисел искомой матрицы или что-то другое? Если да, то Вы уже предполагаете, что их три?

Чтоб я хоть примерно понял откуда ветер дует, как бы выглядел базис алгебры полиномов, если бы исходное уравнение включало и квадратичный член? Я это спрашиваю потому, что мне непонятно как это тройка соответствует коэффициентам уравнения.

Since det is a product of the roots it needs to be a power of x_1 x_2 x_3

Этого тоже не понял. Это обобщение на случай, когда размерность ужене ровно три а кратна трём?

From:

Sorry, chto-to ya nevnyatno izlagaju.

1. All eigenvalues of the matrix are roots of x^3+x+1=0.
Let's call them a,b,c

2. det A is a product of these eigenvalues and therefore has the form
a^k b^l c^n for some integers k,l,n. Clearly det A is a rational number (all coefficients of the matrix are rational).

3. Let us now consider a polynomial of three variables P(x,y,z).
Claim:
P(a,b,c) is rational if and only if P can be written as a sum
(with rational coefficients) of powers of the elementary symmetric polynomials xyz, xy+xz+zy, x+y+z.

4. Consider now P(x,y,z)= x^k y^l c^n . We know that P(a,b,c) is rational.
Therefore P is a sum of powers of the elementary symmetric polynomials.
By some additional simple argument, which I omit, the only polynomial
which can appear is xyz. Therefore, it is a power of xyz and roots go in triples.

Mne kazhetsya, primerno tak.

From:

The polynomial x^3+x+1 is irreducible over the rationals; in particular, all its roots are Galois-conjugate over the field Q of rational numbers. Since the degree N characteristic polynomial of the matrix has rational coefficients, all the roots of x^3+x+1 have the samr multiplicities as roots of the characteristic polynomial. This implies that N is divisible by 3.

From:

> Since the degree N characteristic polynomial of the matrix has rational coefficients, all the roots of x^3+x+1 have the samr multiplicities as roots of the characteristic polynomial.

How do you see this?

From:

Well, it's similar to the situation with complex-conjugate roots of a polynomial with real coefficients: they have the same multiplicity. Here the roots of x^3+x+1 are Galois-conjugate over the rationals and therefore if one of them has say, multiplicity M as a root of a polynomial f(x) with rational multiplicities then all other roots of x^3+x+1 have the same multiplicity as roots of f(x).

From:

Thanks! Of course, it is just needs to be invariant under conjugation.
I was making it far too complicated.

From:

a polynomial f(x) with rational multiplicities

multiplicities => coefficients

From:

нестандартной?

From:

Ну, я такую в первый раз вижу. Возможно, мне просто не повезло в жизни.

From:

Дело не в везении, а в специализации.

From:

А какая должна быть специализация, чтобы такие задачи попадались хоть время от времени?

From:

Алгебра, теория чисел, алгебраическая геометрия ...

From:

Ну, проходили же мы алгебру и теорию чисел. Или Вы имеете в виду, что это ближе к уровню аспирантуры?

From:

Считайте, что это продвинутая линейная алгебра - секретное оружие московских и питерских математиков :)

From:

Ну уж линейную алгебру мы проходили подробно. Я же говорю - не повезло.

Вообще, много с чем не повезло. Столько оказалось всего полезного, чему нас решили не учить, что прямо иногда обидно бывает.

From:

Ну уж линейную алгебру мы проходили подробно.

Над каким полем?

From:

Вещественных чисел. Это Вы верно подметили.

From:

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

From:

Эта мысль мне не вполне доступна. Завтра подумаю ещё.

From:

Ну, для примера, множество всех комплексных чисел именуется комплексной плоскостью еще и и потому, что поле C комплексных чисел является двумерным вещественным векторным пространством с базисом 1 и i .

From:

Это я понимаю, конечно. Но от этого не легче :(

From:

У поля вещественных чисел есть единственное "расширение" которое тоже поле и имеет конечную размерность над $R$, - это поле комплексных чисел $C$. А вот у поля $Q$ рациональных чисел таких расширений очень много, - одно из них естественно возникает в Вашей задаче. А именно, если $\alpha$ - корень многочлена $x^3+x+1$ то множество $K$ всех чисел вида
$a +b \alpha + c \alpha^2$ (с рациональными $a,b,c$)
образует поле (т.е., оно замкнуто относительно сложения, вычитания, умножения и деления на не нуль), которое можно рассматривать как трехмерное векторное пространство над $Q$ с базисом
$1, \alpha, \alpha^2$.

From:

Теперь даже понятно откуда берётся тройка (размерность пространства).

Не совсем пока дошло, почему именно важно деление (т.е. что поле) и откуда этот факт берется - видимо какая-то теорема, связанная с неприводимостью.

Ну хорошо, берем какую-то матрицу А из нашего подпространства размерности 3, представляем в виде линейной комбинации элементов базиса и действуем на какой-то 3-мерный вектор. Получили новый элемент нашего подпространства. Как будто, Вы именно это приводили в процессе доказательства, но я не вполне понимаю, что именно это доказывает.

Такое впечатление, что эти рассуждения только подсказывают, что решения надо искать среди размерностей кратных трём, но факт существования устанавливается только предъявлением конкретного решения.

Кстати, как Вы его нашли? Догадались?

From:

Не совсем пока дошло, почему именно важно деление (т.е. что поле)

Если у нас поле, то сразу же появляется возможность использовать весь мощный аппарат линейной алгебры, в частности, свободно оперировать понятием размерности векторного пространства.

видимо какая-то теорема, связанная с неприводимостью.

Совершенно верно. Вот (более чем) естественная аналогия. Если рассмотреть множество
${0,1, ..., n-1}$ вычетов(остатков) по модулю $n$, то на нем естественно определяются операции сложения, вычитания и умножения (по модулю $n$). Однако делить тут можно если и только если n - простое число. (Для составного n можно найти пару ненулевых вычетов, произведение которых равно n и, стало быть, равно нулю по модулю $n$).

В Вашей задаче вместо множества ${0,1, ..., n-1}$ следует рассматривать все многочлены от #x$ с рациональными коэффициентами и со степенью меньшей тройки. Получается трехмерное векторное $V$ пространство над $Q$ с базисом $1,x, x^2$, на котором можно определить умножение по модулю $x^3+x+1$: берем произведение двух многочленов и делим его с остатком на $x^3+x+1$: этот остаток (имеющий, по определению, степень меньше тройки) и объявляется результатом умножения "по модулю" $x^3+x+1$. Возможность же "деления" действительно гарантируется неприводимостью иногочлена x^3+x+1$ над полем рациональных чисел.

факт существования устанавливается только предъявлением конкретного решения.

Кстати, как Вы его нашли? Догадались?

В пространстве $V$ (определенном выще) есть естественное линейное преобразование $A$ = "умножение" на $x$, удовлетворяющее условию $A^3+A+1=0$. Я лишь расписал его матрицу относительно базиса $1,x, x^2$.

From: