При каких условиях такая ленточная матрица обратима?

[Bars]

Всем привет! Помогите, пожалуйста, с задачкой по Защите Информации.

Укажите, при каких условиях (при каких $n$ и $k$) процедура:

$$ c_i = \sum_{j=1}^k p_{(i + j) \mod n} \mod 33 $$

реализует взаимно-однозначное отображение $ (p_1, p_2, \dots, p_n) \mapsto (c_1, c_2, \dots, c_n) $.

В случае $n = 6, k = 3$ отображение задаётся матрицей

$$ c = p A_{nk} = p \left ( \begin{array}{cccccc} 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 \end{array} \right ) $$

Я посчитал ранги и определители таких матриц, чтобы найти каку-то закономерность.

Определители:

$$ \begin{tabular}{c|cccccccccccc} & \multicolumn{12}{c}{k} \\ n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline 12 & -1 & 0 & 0 & 0 & -5 & 0 & -7 & 0 & 0 & 0 & -11 & 0 \\ 11 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 0 \\ 10 & -1 & 0 & -3 & 0 & 0 & 0 & -7 & 0 & -9 & 0 \\ 9 & 1 & 2 & 0 & 4 & 5 & 0 & 7 & 8 & 0 \\ 8 & -1 & 0 & -3 & 0 & -5 & 0 & -7 & 0 \\ 7 & 1 & 2 & 3 & 4 & 5 & 6 & 0 \\ 6 & -1 & 0 & 0 & 0 & -5 & 0 \\ 5 & 1 & 2 & 3 & 4 & 0 \\ 4 & -1 & 0 & -3 & 0 \\ 3 & 1 & 2 & 0 \\ 2 & -1 & 0 \\ 1 & 1 \\ \end{tabular} $$

Ранги:

$$ \begin{tabular}{c|cccccccccccc} & \multicolumn{12}{c}{k} \\ n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\ \hline 12 & 12 & 11 & 10 & 9 & 12 & 7 & 12 & 9 & 10 & 11 & 12 & 1 \\ 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 11 & 1 \\ 10 & 10 & 9 & 10 & 9 & 6 & 9 & 10 & 9 & 10 & 1 \\ 9 & 9 & 9 & 7 & 9 & 9 & 7 & 9 & 9 & 1 \\ 8 & 8 & 7 & 8 & 5 & 8 & 7 & 8 & 1 \\ 7 & 7 & 7 & 7 & 7 & 7 & 7 & 1 \\ 6 & 6 & 5 & 4 & 5 & 6 & 1 \\ 5 & 5 & 5 & 5 & 5 & 1 \\ 4 & 4 & 3 & 4 & 1 \\ 3 & 3 & 3 & 1 \\ 2 & 2 & 1 \\ 1 & 1 \\ \end{tabular} $$

Я посмотрел на эти картинки и понял, что матрица должна быть обратима если и только если $n$ и $k$ взаимно просты.

Но доказать смог только то, что если $k$ нетривиально делит $n$, то следующие строки матрицы являются ленийно зависимыми:

$$ \begin{aligned} & (\underbrace{1, 1, \dots, 1}_k, \underbrace{0, 0, \dots, 0}_{n - k}) & & (0, \underbrace{1, 1, \dots, 1}_k, \underbrace{0, 0, \dots, 0}_{n - k - 1}) \\ & (\underbrace{0, 0, \dots, 0}_{k}, \underbrace{1, 1, \dots, 1}_k, \underbrace{0, 0, \dots, 0}_{n - 2k}) & & (\underbrace{0, 0, \dots, 0}_{k + 1}, \underbrace{1, 1, \dots, 1}_k, \underbrace{0, 0, \dots, 0}_{n - 2k - 1}) \\ & \dots & & \dots \\ & (\underbrace{0, 0, \dots, 0}_{n - k}, \underbrace{1, 1, \dots, 1}_k) & & (1, \underbrace{0, 0, \dots, 0}_{n - k}, \underbrace{1, 1, \dots, 1}_{k - 1}) \\ \end{aligned} $$

(сумма строк слева равна сумме строк справа и равна $(1, 1, \dots, 1)$)

Помогите, пожалуйста, доказать, что

$$A_{n k} - \text{обратима} \Leftrightarrow (n, k) = 1$$

И ещё есть маленький вопросик. Мы работаем с матрицами над кольцом $\mathbb Z_n$. Остаются ли верными всякие утверждения, связанные с делимостью, определителями и линейной независимостью для кольца, когда кольцо не является полем?

[AV_77]

У вас какое кольцо, $\mathbb{Z}_{33}$ или нет?

Bars в сообщении #846040 писал(а):

Мы работаем с матрицами над кольцом $\mathbb Z_n$. Остаются ли верными всякие утверждения, связанные с делимостью, определителями и линейной независимостью для кольца, когда кольцо не является полем?

Какие-то сохраняются, какие-то нет. Например, матрица обратима, если ее определитель является обратимым элементом кольца.

[Bars]

Кольцо у нас, получается, $\mathbb Z_{33}$

[AV_77]

Тогда это утверждение

Bars в сообщении #846040 писал(а):

матрица должна быть обратима если и только если $n$ и $k$ взаимно просты

не совсем верно. Точнее еще оно условие на $k$ должно быть.

[Bars]

AV_77 в сообщении #846088 писал(а):

условие на $k$ должно быть.

Не знаю, какое. В приведённой таблице определителей его можно увидеть?

[AV_77]

Можно, если вспомнить, что кольцо $\mathbb{Z}_{33}$, а в нем не все элементы обратимы.

[Bars]

Ах да, 33 дложно быть взаимно просто с $k$