Ранг матрицы

[Enoid]

Здравствуйте! Столкнулся со следующей задачей. Рассмотрим множество $M$ матриц размера $n\times n$ следующего строения: $A \in M \Rightarrow (\exists! k) (\forall i) a_{i,i+k} = 1$ ,остальные элементы равны $0$. Теперь рассмотрим сумму $m$ различных элементов множества $M$, получившуюся матрицу обозначим за $C$. Вопрос: чему может быть равен ранг матрицы $C$? Какова нижняя граница? Наибольший интерес представляет случай, когда в матрице $C$ нет одинаковых столбцов. Заранее спасибо!

[ddn]

Enoid писал(а):

Здравствуйте! Столкнулся со следующей задачей. Рассмотрим множество $M$ матриц размера $n\times n$ следующего строения: $A \in M \Rightarrow (\exists! k) (\forall i) a_{i,i+k} = 1$ ,остальные элементы равны $0$. Теперь рассмотрим сумму $m$ различных элементов множества $M$, получившуюся матрицу обозначим за $C$. Вопрос: чему может быть равен ранг матрицы $C$? Какова нижняя граница? Наибольший интерес представляет случай, когда в матрице $C$ нет одинаковых столбцов. Заранее спасибо!

$C^{(1)}=\left\(\begin{array}{c}a\end{array}\right$

$C^{(2)}=\left(\begin{array}{cc}a&b\\b&a\end{array}\right)$

$C^{(3)}=\left(\begin{array}{ccc}a&b&c\\c&a&b\\b&c&a\end{array}\right)$

$C^{(4)}=\left(\begin{array}{cccc}a&b&c&d\\d&a&b&c\\c&d&a&b\\b&c&d&a\end{array}\right)$

Где $a$, $b$, $c$, $d$ - целые неотрицательные числа, и для матрицы $C^{(n)}$ среди первых $n$ из них ровно $m>0$ ненулевых.

Условия невырожденности ($rank=n$):

$det(C^{(1)})=a\not=0$

$det(C^{(2)})=(a+b)(a-b)\not=0$
если $a\not=b$

$det(C^{(3)})=(a+b+c)(a^2+b^2+c^2-ab-ac-bc)=$
$=\frac{1}{2}(a+b+c)((a-b)^2+(b-c)^2+(c-a)^2)\not=0$
если $a\not=b\vee b\not=c\vee c\not=a$

$det(C^{(4)})=(a+b+c+d)(a-b+c-d)(a^2-2ca+c^2+b^2-2bd+d^2)=$
$=(a+b+c+d)((a+c)-(b+d))((a-c)^2+(b-d)^2)\not=0$
если $(a\not=c\vee b\not=d)\wedge(a+c\not=b+d)$

Может удастся найти обощения для любых $n$.

[maxal]

ddn писал(а):

Enoid писал(а):

Здравствуйте! Столкнулся со следующей задачей. Рассмотрим множество $M$ матриц размера $n\times n$ следующего строения: $A \in M \Rightarrow (\exists! k) (\forall i) a_{i,i+k} = 1$ ,остальные элементы равны $0$. Теперь рассмотрим сумму $m$ различных элементов множества $M$, получившуюся матрицу обозначим за $C$. Вопрос: чему может быть равен ранг матрицы $C$? Какова нижняя граница? Наибольший интерес представляет случай, когда в матрице $C$ нет одинаковых столбцов. Заранее спасибо!

$C^{(1)}=\left\(\begin{array}{c}a\end{array}\right$

$C^{(2)}=\left(\begin{array}{cc}a&b\\b&a\end{array}\right)$

Начиная с $C^{(2)}$ и далее - неверно.
Описанные матрицы всего лишь характеризуются условием, что их элементы - неотрицательные целые числа, а сумма элементов в каждой строке равна $m$.

[Александр Т.]

Enoid писал(а):

Рассмотрим множество $M$ матриц размера $n\times n$ следующего строения: $A \in M \Rightarrow (\exists! k) (\forall i) a_{i,i+k} = 1$, остальные элементы равны $0$.

Извиняюсь за неграмотность, но что означает восклицательный знак в $(\exists! k)$? Может быть все-таки $A \in M \Rightarrow (\exists k) (\forall i) a_{i,i+k} = 1$, остальные элементы равны $0$? Тогда как быть, когда $k+i>n$ - брать сравнимое по модулю $n$? То есть, правильно ли я понимаю, что речь идет о матрицах перестановок, описывающих циклический сдвиг в одну сторону?

[maxal]

Восклицательный знак означает "единственное". А вообще справедливое замечание насчет проблемы с $k+i>n$. Я по невнимательности прочитал как $\forall i \exists !k: a_{i,i+k} = 1$ - в этом случае проблемы нет.

[Александр Т.]

maxal писал(а):

Восклицательный знак означает "единственное".

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

maxal писал(а):

А вообще справедливое замечание насчет проблемы с $k+i>n$. Я по невнимательности прочитал как $\forall i \exists !k: a_{i,i+k} = 1$ - в этом случае проблемы нет.

Но тогда, вроде бы, смысл меняется: $k$ может принимать различные значения для различных значений $i$, т.е. матрица не обязательно является матрицей перестановки. Или я снова демонстрирую непонимание общепринятых обозначений?

[maxal]

Александр Т. писал(а):

maxal писал(а):

А вообще справедливое замечание насчет проблемы с $k+i>n$. Я по невнимательности прочитал как $\forall i \exists !k: a_{i,i+k} = 1$ - в этом случае проблемы нет.

Но тогда, вроде бы, смысл меняется: $k$ может принимать различные значения для различных значений $i$, т.е. матрица не обязательно является матрицей перестановки.

Не является, но так в исходном сообщении про перестановочные матрицы ничего не говориться. Если же это действительно перестановочные матрицы имелись в виду, то $C$ будет дважды стохастической матрицей.

[Александр Т.]

maxal писал(а):

Александр Т. писал(а):

maxal писал(а):

А вообще справедливое замечание насчет проблемы с $k+i>n$. Я по невнимательности прочитал как $\forall i \exists !k: a_{i,i+k} = 1$ - в этом случае проблемы нет.

Но тогда, вроде бы, смысл меняется: $k$ может принимать различные значения для различных значений $i$, т.е. матрица не обязательно является матрицей перестановки.

Не является, но так в исходном сообщении про перестановочные матрицы ничего не говориться. Если же это действительно перестановочные матрицы имелись в виду, то $C$ будет дважды стохастической матрицей.

А мне с самого начала показалось, что в исходном сообщении говорилось о матричных представлениях циклических сдвигов, т.е. формулировка задачи должна была выглядеть следующим образом.

Цитата:

Рассмотрим множество $M$ матриц размера $n\times n$ следующего строения: $A \in M \Rightarrow (\exists! k) (\forall i) a_{i,(i+k) \pmod n} = 1$, остальные элементы равны $0$. Теперь рассмотрим сумму $m$ различных элементов множества $M$, получившуюся матрицу обозначим за $C$. Вопрос: чему может быть равен ранг матрицы $C$? Какова нижняя граница?

Причем я понимал это так, что в одной матрице $k$ должно принимать единственное значение для всех $i$.

Тогда, кстати, решение, вроде бы, следующее. Множество $M$ состоит из $n$ различных матриц. И ранг любой их суммы кроме суммы их всех (т.е. когда $m<n$) равен $n$. А ранг суммы их всех (т.е. когда $m=n$) равен единице, что и является нижней границей. (По крайней мере, для $n=2$ и $n=3$ это так.)

[Enoid]

Спасибо за замечания, действительно, имелись в виду матрицы перестановок, описывающие циклический сдвиг в одну сторону. Да, $C$ будет дважды стохастической.
Таким образом, как верно заметил Александр Т., сумму $k+i$ надо брать по $\mod n$.
По поводу вашего рассуждения - почему ранг любой их суммы при $m<n$ равен $n$?

[ewert]

Собственно, вопрос вот к чему сводится. Пусть $\{l_j\}_{j=1}^m$, $m<n$ -- некоторый фиксированный набор различных целых чисел, лежащих в диапазоне от $0$ до $(n-1)$. Надо проверить $n$ равенств:

$$\sum_{j=1}^me^{2\pi i{k\over n}l_j}=0,$$

$k=0,1,\dots,n-1.$

Сколько таких равенств выполняются -- ровно таким и будет коранг матрицы $C$.

-------------------------------------------------
(там плохо видно, расшифровка:

$$\sum_{j=1}^m\exp\left(2\pi i{k\over n}l_j\right)=0$$

)

[Александр Т.]

Enoid писал(а):

По поводу вашего рассуждения - почему ранг любой их суммы при $m<n$ равен $n$?

Это была гипотеза, которая оказалась неверной уже при $n=4$. Например, ранг матрицы

$$\begin{Vmatrix} 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ \end{Vmatrix}$$

равен 2. Почему-то мне показалось, что столбцы любой суммы при $m<n$ линейно независимы.

[ewert]

Ещё один контрпример, который показывает, что ранг непосредственно не связан с количеством различных столбцов: ранг матрицы

$$\begin{pmatrix} 1&1&0&0 \\ 0&1&1&0 \\ 0&0&1&1 \\ 1&0&0&1 \end{pmatrix}$$

равен 3.

[Enoid]

Эти выражения с экспонентами странно выглядят). Уважаемый ewert, вы не могли бы написать, как они выводятся?

[ewert]

А-а, это-то... Довольно просто. Пусть $D$ -- матрица циклического сдвига на единичку (т.е. отличается от единичной сдвигом главной диагонали на одну позицию и, соотв., появлением единички в противоположном углу). Эта матрица унитарна, и все её собственные числа суть $\lambda_k=e^{i{2\pi k\over n}$, $k=0,1,\dots,n-1$ (просто потому, что вполне очевидны соответствующие собственные вектора, представляющие собой отрезки геометрических прогрессий: $\vec u_k=\{e^{i{2\pi k\over n}l\}_{l=1}^n$).

Далее, произвольный циклический сдвиг -- это степень единичного циклического сдвига. Соответственно, матрица $C$ есть некий многочлен от $D$, более конкретно: $C=P(D)\equiv\sum_{l=1}^mD^{l_j}$. Тогда собственные векторы матрицы $C$ те же, что и у $D$, а собственные числа получаются подстановкой чисел $\lambda_k$ в многочлен $P(\lambda)$.

Ну и наконец: собственные векторы $D$ образуют базис (хотя бы потому, что эта матрица унитарна и, следовательно, диагонализуема -- не говоря уж о простоте её собственных чисел). Поэтому размерность нулевого собственного подпространства матрицы $C$ (а это и есть её коранг) в точности совпадает с количеством тех чисел $\lambda_k$, которые являются корнями многочлена $P(\lambda)$.
Ровно это условие выше и выписано.