ny_quant

N delitsya na tri?

From:

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

From:

The answer: N is an every positive integer that is divisible by 3. The proof is based on the irreducibility of the cubic polynomial x^3+x+1 over the rationals that could be easily checked (the only divisors of the constant term are 1 and -1 and they are not the roots). Namely, let us consider the set K of all matrices of the form a+b A+c A^2 with a,b,c rational numbers. Since A^3=-(1+A), the set K is closed under multiplication. Now the irreducibility implies that actually one may divide in K (of course, by non-zero elements). In other words, K is a field (like the fields of rational, reals or complex numbers.) What's interesting is that K carries a natural "structure of 3-dim'l vector space over the field of rational numbers Q, "i.e.", one may add up elements of K and multiply them by rational numbers. Now the action of the matrix A on the coordinate vector space Q^n provides Q^n with a natural structure of K-vector space, whose K-dimension is N/3 and therefore 3 divides N.

For N=3 one may take as A the matrix B

0 0 -1
1 0 -1
0 1 0

If N=3M then one should take the block-diagonal M x M matrix, whose
"diagonal" entries are B.

From:

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

From:

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

From:

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

From:

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

From:

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

From:

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

From:

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

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

From:

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

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

From:

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

From:

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

From:

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

From:

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

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:

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

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:

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

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:

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

Когда Вы говорите "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:

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:

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:

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

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

Ну хорошо, берем какую-то матрицу А из нашего подпространства размерности 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:

> 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: