2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Ранг матрицы с большими целыми элементами
Сообщение18.07.2017, 20:28 


02/10/15
41
Здравствуйте!

Имеется матрица размера (примерно) 12000x6000. При этом большинство элементов матрицы — очень большие целые числа. Например такие:
Код:
131339694543293569856427180570087681403525427113356165120000000000000000000000000000000000000000000000000

Вопрос в следующем — возможно ли за какое-то обозримое время привести такую матрицу к ступенчатому виду или, по крайней мере, точно узнать её ранг? Если да, то какие программы или библиотеки лучше использовать для работы с такими матрицами? Или же это неподъёмная задача?

Заранее спасибо за любые мнения и советы.

 Профиль  
                  
 
 Re: Ранг матрицы с большими целыми элементами
Сообщение18.07.2017, 21:01 
Заслуженный участник
Аватара пользователя


06/10/08
6314
Можно взять достаточное количество простых чисел (например, приведенное Вами число меньше произведения первых 60 простых) и по модулю каждого посчитать ранг. Ранг над целыми числами будет максимумом. Задача получается тяжелая, но вроде бы подъемная.

Если у Вас все числа так же, как и это, заканчиваются нулями, их надо, конечно, сократить.

 Профиль  
                  
 
 Re: Ранг матрицы с большими целыми элементами
Сообщение18.07.2017, 22:19 


02/10/15
41
Xaositect в сообщении #1234410 писал(а):
Можно взять достаточное количество простых чисел (например, приведенное Вами число меньше произведения первых 60 простых) и по модулю каждого посчитать ранг. Ранг над целыми числами будет максимумом. Задача получается тяжелая, но вроде бы подъемная.

Если у Вас все числа так же, как и это, заканчиваются нулями, их надо, конечно, сократить.


Xaositect, большое Вам спасибо за подсказку!
Только я не уверен, что правильно понял последовательность действий (знания в алгебре, к сожалению, более чем скромные). Если можете, посмотрите пожалуйста, что неправильно в решении примера, который я попытался рассмотреть, основываясь на Вашем сообщении.

Возьмём, например, матрицу
$M_0 = \left(
  \begin{array}{cccc}
    -93 & -32 & 8 & 44 \\
    -76 & -74 & 69 & 92 \\
    -72 & -4 & 99 & -31 \\
    -144 & -8 & 198 & -62 \\
  \end{array}
\right).$

Ранг этой матрицы равен 3.

Каждый элемент здесь не больше произведения первых четырёх простых чисел: $2 \cdot 3 \cdot 5 \cdot 7 = 210$. Таким образом, надо найти $Rank(M_0 \mod 2)$, $Rank(M_0 \mod 3)$, $Rank(M_0 \mod 5)$, $Rank(M_0 \mod 7)$.
Получаем:
$M_0 \mod 2 = \left(
  \begin{array}{cccc}
    1 & 0 & 0 & 0 \\
    0 & 0 & 1 & 0 \\
    0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 0 \\
  \end{array}
\right), Rank(M_0 \mod 2) = 3;$

$M_0 \mod 3 = \left(
  \begin{array}{cccc}
    0 & 1 & 2 & 2 \\
    2 & 1 & 0 & 2 \\
    0 & 2 & 0 & 2 \\
    0 & 1 & 0 & 1 \\
  \end{array}
\right), Rank(M_0 \mod 3) = 3;$

$M_0 \mod 5 = \left(
  \begin{array}{cccc}
    2 & 3 & 3 & 4 \\
    4 & 1 & 4 & 2 \\
    3 & 1 & 4 & 4 \\
    1 & 2 & 3 & 3 \\
  \end{array}
\right), Rank(M_0 \mod 5) = 4;$

$M_0 \mod 7 = \left(
  \begin{array}{cccc}
    5 & 3 & 1 & 2 \\
    1 & 3 & 6 & 1 \\
    5 & 3 & 1 & 4 \\
    3 & 6 & 2 & 1 \\
  \end{array}
\right), Rank(M_0 \mod 7) = 4;$

Дальше я не очень понял Вашу фразу "ранг над целыми числами будет максимумом". То есть нужно взять максимум чисел $\{3,3,4,4\}$? Но тогда ранг будет равен 4.

И ещё, если можно, порекомендуйте пожалуйста литературу, где можно подробнее про эти свойства ранга почитать.

 Профиль  
                  
 
 Re: Ранг матрицы с большими целыми элементами
Сообщение18.07.2017, 23:13 
Заслуженный участник
Аватара пользователя


06/10/08
6314
Ранг надо считать не над целыми числами, а тоже по модулю. Например, $Rank(M_0 \bmod 5) \leq 3$, потому что $$2\cdot \begin{bmatrix}2 \\ 4 \\ 3 \\ 1 \end{bmatrix} + 2\cdot \begin{bmatrix}3 \\ 1 \\ 1 \\ 2 \end{bmatrix} + 2\cdot \begin{bmatrix}3 \\ 4 \\ 4 \\ 3 \end{bmatrix} + \begin{bmatrix}4 \\ 2 \\ 4 \\ 3 \end{bmatrix} = 0 \pmod 5$$.

Вычеты по модулю простого числа образуют поле, поэтому находить такой ранг можно так же, как обычно, например, методом Гаусса. Рассмотрим опять же $M_0 \bmod 5$ как пример.
$$
\begin{bmatrix}
   2 & 3 & 3 & 4 \\
   4 & 1 & 4 & 2 \\
   3 & 1 & 4 & 4 \\
   1 & 2 & 3 & 3 \\
\end{bmatrix}
\xrightarrow{\text{$1$ строка} \times 3}
\begin{bmatrix}
   1 & 4 & 4 & 2 \\
   4 & 1 & 4 & 2 \\
   3 & 1 & 4 & 4 \\
   1 & 2 & 3 & 3 \\
\end{bmatrix}
\xrightarrow{\text{очищаем $1$ столбец}}
\begin{bmatrix}
   1 & 4 & 4 & 2 \\
   0 & 0 & 3 & 4 \\
   0 & 4 & 2 & 3 \\
   0 & 3 & 4 & 1 \\
\end{bmatrix}
\xrightarrow{\text{меняем $2$ и $3$ строки}}
$$
$$
\rightarrow
\begin{bmatrix}
   1 & 4 & 4 & 2 \\
   0 & 4 & 2 & 3 \\
   0 & 0 & 3 & 4 \\
   0 & 3 & 4 & 1 \\
\end{bmatrix}
\xrightarrow{\text{$2$ строка} \times 4}
\begin{bmatrix}
   1 & 4 & 4 & 2 \\
   0 & 1 & 3 & 2 \\
   0 & 0 & 3 & 4 \\
   0 & 3 & 4 & 1 \\
\end{bmatrix}
\xrightarrow{\text{очищаем $2$ столбец}}
\begin{bmatrix}
   1 & 4 & 4 & 2 \\
   0 & 1 & 3 & 2 \\
   0 & 0 & 3 & 4 \\
   0 & 0 & 0 & 0 \\
\end{bmatrix}
$$

Для нахождения обратных элементов моно использовать малую теорему Ферма: $a^{p} \equiv a \pmod p$, откуда для $a\neq 0$ имеем $a^{p - 1} = a^{p - 2}\cdot a\equiv 1 \pmod p$, то есть обратным к $a$ по модулю $p$ будет $a^{p - 2}$. В программе эти обратные элементы можно заранее вычислить в таблицу.

-- Вт июл 18, 2017 21:25:02 --

Доказывается это с помощью китайской теоремы об остатках. Я ошибся насчет того, сколько простых надо брать. Если мы возьмем простые числа $p_1, \dots, p_k$ и их произведение $P = p_1 \cdot \dots \cdot p_k$, то нам надо, чтобы определитель ненулевого минора гарантированно был меньше $P$. Тогда он будет ненулевым по модулю $P$, и по китайской теореме он будет ненулевым по модулю какого-то из простых чисел $p_1,\dots,p_k$. Определитель можно оценить сверху числом $D = n! M^n$, где $n$ - минимальный из размеров матрицы, $M$ - максимальное абсолютное значение элементов матрицы, так что простые надо брать где-то до $\ln D < n (\ln n + \ln M)$.

 Профиль  
                  
 
 Re: Ранг матрицы с большими целыми элементами
Сообщение18.07.2017, 23:51 


02/10/15
41
Xaositect, спасибо за поправку, с рангом теперь всё понятно.
Получается, в данном примере, так как $n(\ln n + \ln M) = 4(\ln 4 + \ln 198) \approx 26.7$, нужно было подсчитать ещё ранги по модулю $11$, $13$, $17$, $19$, $23$? И дальше среди всех получившихся рангов выбрать максимальный?

 Профиль  
                  
 
 Re: Ранг матрицы с большими целыми элементами
Сообщение18.07.2017, 23:59 
Заслуженный участник
Аватара пользователя


06/10/08
6314
D'Amir в сообщении #1234474 писал(а):
Получается, в данном примере, так как $n(\ln n + \ln M) = 4(\ln 4 + \ln 198) \approx 26.7$, нужно было подсчитать ещё ранги по модулю $11$, $13$, $17$, $19$, $23$? И дальше среди всех получившихся рангов выбрать максимальный?
Да.

 Профиль  
                  
 
 Re: Ранг матрицы с большими целыми элементами
Сообщение19.07.2017, 00:02 


02/10/15
41
Xaositect, огромное спасибо за помощь!

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

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



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

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


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

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