2014 dxdy logo

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

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




 
 При каких условиях такая ленточная матрица обратима?
Сообщение06.04.2014, 08:37 
Всем привет! Помогите, пожалуйста, с задачкой по Защите Информации.

Укажите, при каких условиях (при каких $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$. Остаются ли верными всякие утверждения, связанные с делимостью, определителями и линейной независимостью для кольца, когда кольцо не является полем?

 
 
 
 Re: При каких условиях такая ленточная матрица обратима?
Сообщение06.04.2014, 09:29 
У вас какое кольцо, $\mathbb{Z}_{33}$ или нет?

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

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

 
 
 
 Re: При каких условиях такая ленточная матрица обратима?
Сообщение06.04.2014, 09:38 
Кольцо у нас, получается, $\mathbb Z_{33}$ :-)

 
 
 
 Re: При каких условиях такая ленточная матрица обратима?
Сообщение06.04.2014, 11:17 
Тогда это утверждение
Bars в сообщении #846040 писал(а):
матрица должна быть обратима если и только если $n$ и $k$ взаимно просты

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

 
 
 
 Re: При каких условиях такая ленточная матрица обратима?
Сообщение17.01.2015, 21:31 
AV_77 в сообщении #846088 писал(а):
условие на $k$ должно быть.

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

 
 
 
 Re: При каких условиях такая ленточная матрица обратима?
Сообщение18.01.2015, 18:42 
Можно, если вспомнить, что кольцо $\mathbb{Z}_{33}$, а в нем не все элементы обратимы.

 
 
 
 Re: При каких условиях такая ленточная матрица обратима?
Сообщение18.01.2015, 19:35 
Ах да, 33 дложно быть взаимно просто с $k$

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group