#import "../../utils/core.typ": *

== Элементарные преобразования и элементарные матрицы

#def[
    Элементарное преобразование $1$ типа:

    К $i$ строке прибавить $j$ строку, умноженную на $lambda in R$. Обозначается $T_(i j) (lambda)$
]

#def[
    Элементарное преобразование $2$ типа:

    Поменять местами $i$ и $j$ строки. Обозначается $S_(i j)$
]

#def[
    Элементарное преобразование $3$ типа:

    Умножить $i$ строку на $lambda in R, space lambda eq.not 0$. Обозначается $D_(i j) (lambda)$
]

#notice[
    Аналогичные преобразования можно делать с столбцами.
]

#def[
    Матрица $A in M_(m, n) (K)$ называется ступенчатой, если существует $0 <= r <= m$ и числа $j_1, ..., j_r: 1 <= j_1 < ... < j_r <= n$ такие, что:
    
    + $a_(k j_k) eq.not 0, space k = 1, ..., r$
    
    + $a_(k j) = 0, space k = 1, ..., r, space j < j_k$
    
    + $a_(k j) = 0, space forall j, k: space  k > r$
] 

#example[
    $display(mat(
        1, 1, 1, 1, 1, 1;
        0, 0, 1, 1, 1, 1;
        0, 0, 0, 0, 0, 1;
        0, 0, 0, 0, 0, 0;
    ))$
]

#pr[
    Любую матрицу можно превратить в ступенчатую с помощью преобразования строк $1$ и $2$ типа.
]

#proof[(короче Гаусса пишем и работает)

    $A = a(i, j) in M_(m, n) (K)$

    Индукция по $m$.

    "База": $m = 1$. $A$ ступенчатая по определению.

    "Переход": $m > 1$:

    Если $A = 0$, то $A$ ступенчатая по определению.

    $j_1$ --- номер первого ненулевого столбца. 

    $exists i : a_(i j_1) eq.not 0$

    $i eq.not 1 ==>$ применим $S_(1 i)$

    Таким образом можно считать $a_(1 j_1) eq.not 0$.

    Применим $T_(2 1) (-(a_(2 j_1))/(a_(1 j_1)) ), T_(3 1) (-(a_(3 j_1))/(a_(1 j_1))), ..., T_(m 1) (-(a_(m j_1))/(a_(1 j_1)))$

    Получим $A' = display(mat(
        a_(1 1), a_(1 2), ..., a_(1 n);
        0, a_(2 2), ..., a_(2n);
        dots.v, dots.v, dots.down, dots.v;
        0, a_(m m), ..., a_(m n);
    ))$

    По индукции $A'$ ступенчатая.
]

#def[
    Окаймленная единичная матрица --- матрица вида:

    $display(mat(
        1, 0, ..., 0, 0, ..., 0;
        0, 1, ..., 0, 0, ..., 0;
        dots.v, dots.v, dots.down, dots.v, dots.v, dots.down, dots.v;
        0, 0, ..., 1, 0, ..., 0;
        0, 0, ..., 0, 0, ..., 0;
        dots.v, dots.v, dots.down, dots.v, dots.v, dots.down, dots.v;
        0, 0, ..., 0, 0, ..., 0;
    ))$
]

#th[
    Пусть $A in M_(m, n) (K)$. Тогда ее можно преобразовать в окаймленную единичную матрицу с помощью преобразования строк и столбцов.
]

#proof[
    
    Сделаем $A$ ступенчатой.

    С помощью третьего преобразования сделаем все ведущие элементы равными $1$.

    Превратим ступеньки разной длины в единичные. (меняя столбцы)

    Применим $D_1 (a_(11)^(-1)), ..., D_r (a_(r r)^(-1))$. 

    Потом будем от верхней строки к нижней превращать их в строки с одной $1$ и нулями. (вычитая строки и столбцы)
]

#example[
    $display(mat(
        1, 1;
        1, 1;
    )) -> 
    display(mat(
        1, 1;
        0, 0;
    )) limits(->)^("вычесть столбцы") 
    display(mat(
        1, 0;
        0, 0;
    ))$
]

#def[
    Элементарная матрица:
    
    "Первого типа":

    Пусть $1 <= i, j <= n, i eq.not j, lambda in K$


    $T_(i j) (lambda) = display(mat(
        1, 0, ..., 0, ..., 0;
        0, 1, ..., 0, ..., lambda;
        dots.v, dots.v, dots.down, dots.v, dots.down, dots.v;
        0, 0, ..., 1, ..., 0;
        dots.v, dots.v, dots.down, dots.v, dots.down, dots.v;
        0, 0, ..., 0, ..., 1
    )) = E_n + lambda e_(i j)$

    "Второго типа":

    $S_(i j) = display(mat(
        1, 0, ..., 0, ..., 0;
        0, 0, ..., 1, ..., 0;
        dots.v, dots.v, dots.down, dots.v, dots.down, dots.v;
        0, 1, ..., 0, ..., 0;
        dots.v, dots.v, dots.down, dots.v, dots.down, dots.v;
        0, 0, ..., 0, ..., 1
    )) = E_n - e_(i i) - e_(j j) + e_(i j) + e_(j i)$

    "Третьего типа":

    $D_i (lambda) = display(mat(
        1, 0, ..., 0, ..., 0;
        0, 1, ..., 0, ..., 0;
        dots.v, dots.v, dots.down, dots.v, dots.down, dots.v;
        0, 0, ..., lambda, ..., 0;
        dots.v, dots.v, dots.down, dots.v, dots.down, dots.v;
        0, 0, ..., 0, ..., 1
    )) = E_n + (lambda - 1) e_(i i)$
]

#pr[
    Пусть $A in M_(m, n) (K)$. Тогда при элементарных преобразованиях строк матрицы $A$ получаются матрицы $T_(i j) A, S_(i j) A, D_i A$.
]

#proof[
    + "Первого типа": #[
        Поскольку матрица $T_(i j) (lambda)$ отличается от $E_n$ только в $i$-ой строке, то произведение тоже. В $i$-ой строке $T_(i j) (lambda)$ только две позиции отличаются от нуля, это $i$ и $j$. При умножении получаем следующее:

        $
            display(mat(
                0, ..., 1, ..., lambda, ..., 0
            )) dot display(mat(
                a_(1 k);
                dots.v;
                a_(i k);
                dots.v;
                a_(j k);
                dots.v;
                a_(n k);
            )) = a_(i k) + lambda a_(j k)
        $

        Такое происходит в каждом столбце матрицы, поэтому получаем, что $i$ строка матрицы $T_(i j) A$ равна $display(mat(
            a_(i 1) + lambda a_(j 1), ..., a_(i k) + lambda a_(j k), ..., a_(i n) + lambda a_(j n);
        ))$
    ]

    + "Второго типа": #[
        Поскольку матрица $S_(i j)$ отличается от $E_n$ только в $i$-ой и $j$-ой строках, то произведение тоже. $i$-ая строка равна произведению $display(mat(
            0, ..., 1, ..., 0;
        ))$ на матрицу $A$, то есть на её $j$-тую строку. Аналогично с $j$-ой строкой. 
    ]

    + "Третьего типа": #[        
        Поскольку матрица $D_i (lambda)$ отличается от $E_n$ только в $i$-ой строке, то произведение тоже. $i$-ая строка равна произведению $display(mat(
            1, ..., lambda, ..., 1;
        ))$ на матрицу $A$, то есть на её $i$-тую строку. Что равно произведению $i$-ой строки на $lambda$.
    ]
]

#follow[
    Аналогично, преобразования столбцов можно записать в виде $A T_(j i) (lambda), A S_(j i), A D_j (lambda)$.
]

#proof[
    $A --> A'$ --- результат прибавления к $i$ столбцу $j$-го с коэффицентом $lambda$.

    $==> (A')^T = T_(i j) (lambda) A^T$

    $==> A' = (T_(i j) (lambda) A^T)^T = (A^T)^T (T_(i j) (lambda))^T = A T_(j i) (lambda)$

    Аналогично: элементарные преобразования столбцов $2$ и $3$ типов сводятся к умножению справа на $S_(i j)$ и $D_i (lambda)$ соответственно.
]

#follow[
    + $T_(i j) (-lambda) T_(i j) (lambda) = E_n$
    
    + $S_(i j) S_(i j) = E_n$
    
    + $D_i (lambda) D_i (lambda^(-1)) = E_n$
]

#follow[
    $T_(i j) (lambda), S_(i j), D_i (lambda) in GL_n (K)$ --- все они обратимы.
]

#pr(name: [PDQ разложение матриц])[ 
    Пусть $A in M_(m, n) (K)$. Тогда существуют элементарные матрицы $P_1, ..., P_k in GL_m (K), space Q_1, ..., Q_l in GL_n (K)$, окаймленная единичная матрица $D in M_(m, n) (K)$, такие, что $A = P_1 ... P_k D Q_1 ... Q_l$.
]

#proof[
    Существуют элементарные преобразования строк и столбцов, превращающие $A$ в окаймленную единичную матрицу $D$.

    $==> D = underbrace(u_k ... u_1, "обратимы") A underbrace(v_1 ... v_l, "обратимы")$, где $u_1, ..., u_k, space  v_1, ..., v_l$ --- элементарные матрицы

    $==> A = u_1^(-1) ... u_k^(-1) D v_l^(-1) ... v_1^(-1)$
]

#follow[    
    Пусть $A in M_n (K)$? Тогда условия эквивалентны:

    + $A in GL_n (K)$
    
    + $A = P_1 ... P_m$, где $P_1, ..., P_m$ --- элементарные матрицы
]

#proof[

    "$2 ==> 1$": так как все $P_i in GL_n (K)$

    "$1 ==> 2$": 

    $A = P_1 ... P_k D Q_1 ... Q_l, space  D = display(mat(
        E_n, 0;
        0, 0;
    ))$

    $==> D = P_k^(-1) ... P_1^(-1) A Q_l^(-1) ... Q_1^(-1) ==> D in GL_n (K)$

    В $D$ есть нулевая строка, значит $forall C in M_n (K)$: в $D C$ есть нулевая строка $==> D C eq.not E_n$, но ведь $D in GL_n (K)$, значит $D = E_n ==> A = P_1 ... P_k Q_1 ... Q_l$, где все матрицы элементарны.
]