Ранг матрицы с большими целыми элементами

[D'Amir]

Здравствуйте!

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

131339694543293569856427180570087681403525427113356165120000000000000000000000000000000000000000000000000

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

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

[Xaositect]

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

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

[D'Amir]

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.

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

[Xaositect]

Ранг надо считать не над целыми числами, а тоже по модулю. Например, $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)$.

[D'Amir]

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

[Xaositect]

D'Amir в сообщении #1234474 писал(а):

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

Да.

[D'Amir]

Xaositect, огромное спасибо за помощь!