Вектора

[Terraniux]

1.Каково наибольшее число попарно ортогональных векторов, смотрящих из центра $n$-мерного куба в его вершины?
2. В пространстве даны $n$ векторов, модуль каждого из которых равен 1, а сумма всех равна нуль-вектору. Докажите, что можно занумеровать вектоора так, что для любого $ k=1, 2, \ldots, n$ модуль суммы первых $k$ векторов не превосходит 3.
Докажите также, что условие на длину векторов "равна 1" можно заменить условием "не больше 1".

[mihiv]

1. Поместим центр куба в начале координат, тогда ортогональные векторы можно искать в множество из $2^n$ векторов с координатами $\pm 1$. Пусть у пары таких векторов ровно $k$ координат отличается знаком и, соответственно, $n-k$ координат совпадает. Скалярное произведение этих векторов равно $n-2k$. Если векторы ортогональны, то $n-2k=0$. То есть ортогональные векторы существуют только для четных $n$.
Пусть $n$ четное. Т.к. ортогональные векторы линейно независимы, то число попарно ортогональных векторов $\leqslant n$, с другой стороны всегда можно найти пару ортогональных векторов.
Отметим, что для $n=2,4$ число попарно ортогональных векторов равно $n$. Общей закономерности найти не удалось.

[ИСН]

внезапно
https://en.wikipedia.org/wiki/Hadamard_matrix
кое-что известно, но вообще открытая проблема.

[Terraniux]

А ведь это, по мнению Белова, задача-монстр!

[ИСН]

Ну а что, не монстр, что ли?

[mihiv]

Предлагаю модификацию задачи 2 :
На плоскости даны $n$ векторов, модуль каждого из которых равен 1, а сумма всех равна нуль-вектору. Докажите, что можно занумеровать вектора так, что для любого $ k=1, 2, \ldots, n$ модуль суммы первых $k$ векторов не превосходит $\sqrt 2$.

[Terraniux]

mihiv в сообщении #959218 писал(а):

Предлагаю модификацию задачи 2 :
На плоскости даны $n$ векторов, модуль каждого из которых равен 1, а сумма всех равна нуль-вектору. Докажите, что можно занумеровать вектора так, что для любого $ k=1, 2, \ldots, n$ модуль суммы первых $k$ векторов не превосходит $\sqrt 2$.

Интересно. Есть ли у Вас решение?

[mihiv]

Да, для плоскости решение есть.

[mihiv]

В задаче 1 для $n=4l+2$ можно доказать, что максимальное число взаимно ортогональных векторов равно 2.
Действительно, если два вектора ортогональны, то, как показано ранее, $n-2k=0$, где $k$- число координат векторов, отличающихся знаком. Следовательно, $k=\frac n2\qquad (1)$ .
Предположим, можно найти три взаимно ортогональных вектора $\vec a_1, \vec a_2, \vec a_3.$ Тогда должно выполняться равенство: $(\vec a_1+\vec a_2, \vec a_3)=0 \qquad (2).$ Но в силу условия (1) вектор $\vec a_1+\vec a_2=2\vec a,$ где $\frac n2$ координат вектора $\vec a$ равны 0, а оставшиеся $\frac n2$ координат равны $\pm 1$. Так как $\frac n2$ нечетно, то скалярное произведение (2) не равно 0. Противоречие.

[iifat]

mihiv в сообщении #959535 писал(а):

для плоскости решение есть

Пошёл думать. Спасибо за задачу.
На прямой доказывается достаточно просто (даны $n$ чисел, по модулю не превосходящих $1$, в сумме ноль; доказать, что можно выстроить так, чтоб частичные суммы по модулю не превосходили $1$). Если получится обобщить... Тогда частичные суммы будут по модулю не более $\sqrt r$ (корень из размерности пространства).

[mihiv]

В задаче 1 для $n=2^l$ максимальное число взаимно ортогональных векторов $N$ равно $N=2^l$. Доказывается индукцией по $l$.
Будем записывать координаты векторов в пространстве размерности $n=2^l$ в виде строк матрицы $A_l$ размера $2^l\times 2^l$. Для $l=1$ утверждение очевидно справедливо. В качестве матрицы $A_1$ можно выбрать, например:

$$A_1=\left (\begin {array}{ccc}1& 1\\1&-1\end {array}\right )$$

По матрице $A_{l-1}$ по рекуррентной формуле строим матрицу:

$$A_l=\left (\begin {array}{ccc}A_{l-1}&A_{l-1}\\A_{l-1}&-A_{l-1}\end {array}\right )$$

В общем случае, когда $n=2^lm, m>1, m-$ нечетное, вероятно, также $N=2^l$, но доказать это пока не получилось.

[ИСН]

Ваша конструкция для степеней двойки - это Walsh matrix. Про общий случай я тоже уже говорил.

[mihiv]

ИСН, спасибо за разъяснение! Таким образом, общий случай упирается в недоказанную гипотезу Адамара.