Оператор над конечным полем, сохраняющий обычную сумму

[muh1008]

Пусть $\mathbb{B}=\{0,1\}$. Рассмотрим линейное отображение $A:\mathbb{B}^{n}\to\mathbb{B}^{n}$, задаваемое матрицей $A=(a_{ij})$ с элементами из поля $\mathbb{B}=\{0,1\}$. То есть $y=Ax$ означает, что

$$ y_{i}=\bigoplus_{j=1}^{n}a_{ij}x_{j}, \quad i=\overline{1,n}. $$

Символ $\bigoplus$ означает сумму по модулю 2.

Пусть $m$ - некоторое фиксированное натуральное число, $1 < m < n$.

Рассмотрим множество

$$ L=\Big\{x=(x_{1},\ldots,x_{n})\in\mathbb{B}^{n}:\,\sum_{j=1}^{n}x_{j}=m\Big\}. $$

Здесь сумма понимается как обычная сумма, НЕ по модулю 2.

Вопрос. При каких условиях на матрицу $A$ для любого $x\in L$ выполнено $y=Ax\in L$ ?

Другими словами, при каких условиях на матрицу $A$ из условия $\sum\limits_{j=1}^{n}x_{j}=m$ следует, что $\sum\limits_{i=1}^{n}y_{i}=m$ ?

Если бы тот же вопрос стоял для линейного отображения $A:\mathbb{R}^{n}\to\mathbb{R}^{n}$, когда

$$ y_{i}=\sum_{j=1}^{n}a_{ij}x_{j}, \quad i=\overline{1,n}, $$

с обычной суммой, то как я вижу он решался бы просто:

$$ \sum_{i=1}^{n}y_{i}=\sum_{i=1}^{n}\sum_{j=1}^{n}a_{ij}x_{j}=\sum_{j=1}^{n}\sum_{i=1}^{n}a_{ij}x_{j}= \sum_{j=1}^{n}\Big(x_{j}\sum_{i=1}^{n}a_{ij}\Big)=m=\sum_{j=1}^{n}x_{j}, $$

и таковым условием было бы условие

$$ \sum_{i=1}^{n}a_{ij}=1, \quad j=\overline{1,n}. $$

Но проблема в том, что в случае отображения $A:\mathbb{B}^{n}\to\mathbb{B}^{n}$

$$ \sum_{i=1}^{n}y_{i}=\sum_{i=1}^{n}\bigoplus_{j=1}^{n}a_{ij}x_{j}\neq \bigoplus_{j=1}^{n}\sum_{i=1}^{n}a_{ij}x_{j}. $$

Что делать в этом случае? Заранее благодарю за помощь.

[adfg]

матрица перестановки

[muh1008]

Это понятно, что матрицы перестановки удовлетворяют условию. Но только ли они одни удовлетворяют ему?

[g______d]

muh1008 в сообщении #1406381 писал(а):

Но только ли они одни удовлетворяют ему?

Вроде да: достаточно применить к стандартным базисным векторам, а потом, если случайно на двух базисных векторах будет одинаковый результат, применить к сумме этих базисных векторов и получить противоречие.

[Munin]

А разве ответ от $m$ не зависит?

[alcoholist]

Для $L$ лучше использовать определение

$$L(m)=\left\{(x_1,\cdots,x_n)\in\mathbf{Z}_2^n:\#\{i:x_i=1\}=m\right\}$$

-- Пн июл 22, 2019 11:05:34 --

Очевидно, что

$$\mathbf{Z}_2^n=\bigcup\limits_{0\le m\le n}L(m)$$

-- разложение на орбиты естественного действия группы перестановок.

[mihaild]

От $m$ естественно зависит. Если $m = 0$, то подходят все операторы, если $m = n$ - то операторы, у которых вектор $(1, 1, \ldots, 1)$ является неподвижной точкой, если $0 < m < n$, то вроде бы только перестановки.

[g______d]

А, я почему-то подумал, что требуется одновременно для всех $m$.

[Munin]

Как я понимаю, при такой формулировке

muh1008 в сообщении #1406368 писал(а):

Вопрос. При каких условиях на матрицу $A$ для любого $x\in L$ выполнено $y=Ax\in L$ ?

подразумевается, что $A(L_m)\subseteq L_m,$ но не требуется, чтобы $A(L_m)=L_m.$ Так что насчёт "только перестановки" у меня чешутся сомнения.

Заодно, я вначале сослепу прочитал вопрос совершенно иначе: при каких условиях $|A(L_m)|=|L_m|?$ (совпадают мощности множеств)
Может быть, уважаемые собеседники и на это найдут что прокомментировать?

[g______d]

Для нечётного $m$ есть такой пример. Пусть $v\in L_m$ фиксирован, и $f(u)$ — сумма всех координат вектора $u$ (по модулю 2). Тогда $Au=f(u)v$ удовлетворяет условиям.

[vpb]

Общая философия говорит, что если в задаче есть натуральный параметр, значит надо ее решать (как правило) сначала для небольших значений этого параметра.

Если $m=0$, то ответ тривиален (любое линейное отображение подходит). Если $m=1$, то, очевидно, $A$ должно (и может) иметь вид $Ae_i=e_{\alpha(i)}$, где $\alpha$ --- любое отображение множества $I_n=\{1,2,\ldots,n\}$ в себя,
а $e_i$ обозначает базисный вектор-столбец.

Теперь уместно рассмотреть $m=2$. Заметим, что $L_2$ --- это не что иное, как множество неупорядоченных пар $\{i,j\}$. На этом множестве можно рассмотреть граф: $a\sim b$, если $a$ и $b$, как пары, имеют один общий
элемент. Это отношение может быть охарактеризовано в терминах сложения по модулю 2: $a\sim b$, если $a\oplus b\in L_2$. Если $A$ --- отображение с нужными свойствами, и $a\sim b$, то $a\oplus b=c$, для некоторого $c\in L_2$, откуда $Aa\oplus Ab=Ac$, откуда $Aa\sim Ab$. Значит, $A$ индуцирует отображение множества вершин графа в себя, которое переводит каждое ребро в ребро. Поэтому оно переводит клику в клику. Это можно использовать.

Если $n\geq5$, то, как легко видеть, клики максимального размера в $L_2$ имеют вид $C_i=\{\ \{i,j\}\mid j\ne i\}$, где $i\in I_n$. Поэтому $A$ индуцирует некоторое отображение множества $I_n$ в себя. Ну и можно подумать о том, не получается ли $A$ как раз из этого отображения.

А при $n=4$ будут, явно, и другие отображения. Например, пусть $f:{\mathbb B}^4\longrightarrow{\mathbb B}$ --- любая линейная функция, и пусть $u=(1,1,1,1)^T=e_1+e_2+e_3+e_4$. Тогда отображение по правилу $v\mapsto v+f(v)u$ сохраняет $L_2$, как легко видеть. Некоторые из таких отображений индуцированы элементами из $S_4$, а другие нет. Кажется, полная группа обратимых $A$ имеет порядок $48$. Подробности предлагается разобрать самостоятельно.

Что до $m>2$, то тут, наверное, надо действовать примерно так же. Для пар элементов из $L_m$ есть $\leq m+1$ возможных типов взаимного расположения, с точностью до действия группы $S_n$. Надо пары каждого (или хотя бы одного, скажем когда пересечение максимально) типа как-то охарактеризовать в "линейных" терминах, и потом это использовать.

В общем, как-то так.