2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 антиортогональные системы векторов
Сообщение27.04.2008, 14:18 


04/10/05
272
ВМиК МГУ
Рассмотрим $n$-мерное векторное пространство над полем вычетов по простому модулю $p$. Векторы $(x_1,\ldots,x_n)$ и $(y_1,\ldots,y_n)$ будем называть ортогональными, если $x_1y_1+\ldots+x_ny_n=0$.

Две системы векторов $(u_1,\ldots,u_k)$ и $(v_1,\ldots,v_k)$ называются антиортогональными, если при всех $i$ векторы $u_i$ и $v_i$ ортогональны, и при всех $i\neq j$ векторы $u_i$ и $v_j$ не ортогональны. Найти максимальное $k$, при котором такие системы существуют.

Для начала можно хотя бы оценить порядок роста этой функции на уровне полином/экспонента. Разбор частных случаев тоже приветствуется.

 Профиль  
                  
 
 
Сообщение28.04.2008, 10:09 
Модератор
Аватара пользователя


11/01/06
5660
Уже на плоскости ($n=2$) существует бесконечное семейство антиортогональных векторов:
$u_i = (i,1),\ v_i= (1,-i),\ i=1,2,3,\dots$

Понятно, что $(u_i,v_i)=i-i=0$ и $(u_i,v_j)=i-j\ne 0$ при всех $i\ne j$.

 Профиль  
                  
 
 
Сообщение28.04.2008, 10:37 


04/10/05
272
ВМиК МГУ
В $\mathbb{R}^n$, $n\geq 2$ - да, а в пространстве над конечным полем, естественно, бесконечных семейств не бывает.

 Профиль  
                  
 
 
Сообщение28.04.2008, 23:45 


04/10/05
272
ВМиК МГУ
Самое интересное, что даже при $p=2$ уже получается неожиданный ответ.

 Профиль  
                  
 
 
Сообщение14.12.2008, 14:05 


04/10/05
272
ВМиК МГУ
Запостить решение что ли...
Докажем, что $\left(\substack{n-1 \\ p-1}\right)\leq k\leq\left(\substack{p+n-2 \\ p-1}\right)+1$.

$k\leq\left(\substack{p+n-2 \\ p-1}\right)+1$. Пусть $(u_1,\ldots,u_k)$, $(v_1,\ldots,v_k)$ - антиортогональные системы векторов размерности $n$ над $\mathbb{Z}_p$. Рассмотрим матрицу $R=\{r_{ij}\}$, где $r_{ij}=(u_i,v_j)^{p-1}$, $1,\leq i,j\leq k$ ($(x,y)$ - это рассматриваемое нами скалярное произведение векторов). По малой теореме Ферма, $r_{ij}=1$, если векторы $u_i$ и $v_j$ не ортогональны, $0$, если ортогональны. Из этого следует, что ранг матрицы $R$ не меньше $k-1$.
Рассмотрим выражение
$(a_1x_1+\ldots+a_nx_n)^{p-1}$.
Его можно представить в виде
$\sum_{i=1}^{l}c_i(a_1,\ldots,a_n)p_i(x_1,\ldots,x_n)$,
где $p_1,\ldots,p_l$ - различные одночлены степени не больше $p-1$. Количество одночленов $l=\left(\substack{p+n-2 \\ p-1}\right)$. Из этого представления следует, что существуют такие $l$ векторов размерности $k$, что каждая строка матрицы $R$ представляется в виде их линейной комбинации. Таким образом, $\mathrm{rang}(R)\leq l$. Из этого вытекает доказываемое неравенство.

$\left(\substack{n-1 \\ p-1}\right)\leq k$. Возьмём множество всех векторов, у которых первая компонента и ещё $p-1$ компонент равны 1, остальные - 0. Всё.

Более точной оценки мне не известно.

Добавлено спустя 29 минут 36 секунд:

При $p=2$ ответом является наименьшее нечётное число, большее или равное $n$.

Пример при чётном $n$: первое семейство состоит из вектора $(1,1,\ldots,1)$ и всех единичных векторов, второе из всех векторов, в которых не более одной нулевой компоненты. При нечётном $n$ можно приписать ко всем построенным векторам размерности $n-1$ справа ноль.

Доказательство, что больше нельзя - аналогичное через ранг матрицы (только нужно ранг вычислить точно, а не оценить как $k-1$).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group