О матрицах и факторизации.

[AlexSam]

Существуют ли алгоритмы приведения матрицы к треугольному виду так, чтобы по диагонали стояли делители определителя матрицы?

Т.е. как из матрицы: $\begin{pmatrix}1 & 7 & 3\cr 4 & 5 & 6\cr 1 & 1 & 1\end{pmatrix}$ прийти к $\begin{pmatrix}1 & a & b\cr 0 & 2 & c\cr 0 & 0 & 5\end{pmatrix}$?

[provincialka]

AlexSam
Ну... приведите к жордановой форме!
Кстати, вы не объяснили, что понимаете под словом "привести". Чем пользоваться можно?

[grizzly]

AlexSam в сообщении #1103156 писал(а):

к треугольному виду так, чтобы по диагонали стояли делители определителя матрицы?

Вы, может, думаете, что у треугольной матрицы может быть ещё какой-то "не такой" вид?

[provincialka]

grizzly
Может "делители" понимается в целочисленном смысле? Хм...

[grizzly]

provincialka
Так там, должно быть, и матрица понимается в каком-нибудь узком смысле -- как в примере, например. А то ведь если определитель будет $\sqrt2$, то какие там у него делители? Ладно, подождём расшифровку условия.

[AlexSam]

Цитата:

Кстати, вы не объяснили, что понимаете под словом "привести". Чем пользоваться можно?

Пользоваться можно всем.

Цитата:

Вы, может, думаете, что у треугольной матрицы может быть ещё какой-то "не такой" вид?

Обычно результат такой:$\begin{pmatrix}1 & a & b\cr 0 & 1 & c\cr 0 & 0 & 10\end{pmatrix}$
Меня интересует факторизация определителя матрицы.

[grizzly]

AlexSam в сообщении #1103178 писал(а):

Меня интересует факторизация определителя матрицы.

Ничего не понял. Допустим, получилось вот так:

$$ $\begin{pmatrix}1 & a & b\cr 0 & 1 & c\cr 0 & 0 & 1000\end{pmatrix}$ $$

А как Вы бы хотели получить?

[Xaositect]

AlexSam в сообщении #1103178 писал(а):

Пользоваться можно всем.

Это не ответ. Если всем можно пользоваться, то давайте просто разложим определитель и напишем его по диагонали. Опишите, какие преобразования рассматриваются.

Я подозреваю, что все-таки рассматриваются элементарные операции, не меняющие определитель, и тогда, например $\left(\begin{matrix} 1 & 0 \\ 0 & 4\end{matrix}\right)$ нельзя привести к $\left(\begin{matrix}2 & 0\\0 & 2\end{matrix}\right)$.

[AlexSam]

Цитата:

Ничего не понял. Допустим, получилось вот так:

$$ $\begin{pmatrix}1 & a & b\cr 0 & 1 & c\cr 0 & 0 & 1000\end{pmatrix}$ $$

А как Вы бы хотели получить?

А хотелось получить:$\begin{pmatrix}1 & a & b\cr 0 & 100 & c\cr 0 & 0 & 10\end{pmatrix}$ или $\begin{pmatrix}10 & a & b\cr 0 & 10 & c\cr 0 & 0 & 10\end{pmatrix}$ (есть еще варианты, но как можно меньше единиц по диагонали)

Цитата:

то давайте просто разложим определитель и напишем его по диагонали

а если определитель очень большой? Ооочень большой.

[grizzly]

AlexSam в сообщении #1103186 писал(а):

а если определитель очень большой? Ооочень большой.

Больше, чем число Грэма? Ну так всё равно можно "решетом Эратосфена" находить следующее простое, потом "столбиком" пытаться делить. Сможете записать алгоритм? :)

[AlexSam]

Цитата:

Больше, чем число Грэма? Ну так всё равно можно "решетом Эратосфена" находить следующее простое, потом "столбиком" пытаться делить.

Чтобы не делить столбиком я и спрашиваю про алгоритм:
как можно получить треугольную матрицу и делители определителя одновременно.
(Под делителями я имею ввиду числа отличные от единицы и самого определителя, в случае если определитель не простое число).

[grizzly]

Не представляю, чем Вас тогда ответ Xaositect не устроил.

Ответьте, пожалуйста, на вопрос, который задали provincialka и Xaositect, пока тема в карантин не ушла, а то ведь цель обсуждения становится всё менее понятной.

[AlexSam]

Сформулирую так: как можно получить треугольную матрицу и делители определителя ОДНОВРЕМЕННО, т.е в процессе получения треугольной матрицы.
(Под делителями я имею ввиду числа отличные от единицы и самого определителя, в случае если определитель не простое число).

[dsge]

Для преобразований вида $A_1=Q^{-1}AQ$, где $Q$ невырожденная матрица на диагонали всегда будут получаться собственные числа. Одним из преобразований, приводящих матрицу к треугольному виду, является преобразование Шура.

[venco]

Попробую протелепатить...
Мне кажется, AlexSam хочет магическим образом свести задачу факторизации целого числа к диагонализации матрицы, и таким образом получить полиномиальный алгоритм факторизации.
Естественно, даром ничего не получится, и такой волшебный алгоритм диагонализации будет включать в себя факторизацию самого определителя.