О РЕШЕНИИ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ НАД КОММУТАТИВНЫМ

КОЛЬЦОМ ^{∗}

Г. И. Малашонок

Пусть R — коммутативное кольцо. Рассмотрим систему линейных уравнений над R

Ax = a,  (1)

где A ∈ R^{n×m}, a ∈ R^{n}, x ∈ R^{m}, с расширенной матрицей коэффициентов A^{∗} = ∥α_{i,j}∥ (i = 1, …, n, j = 1, …, m + 1). Будем называть систему (1) вырожденной, если аннулятор всех коэффициентов системы — это ненулевой идеал.

Для решения системы (1), вообще говоря, достаточно указать метод понижения порядка системы, т. е. свести решение системы к одной или нескольким системам с меньшим числом неизвестных, возможно, в другом коммутативном кольце. В настоящей работе будет получен метод понижения порядка произвольной невырожденной системы, возможно, с переходом к фактор-кольцу (см. теоремы 1, 2), и приведены два удобных алгоритма: метод обращающей матрицы и метод прямого и обратного хода. Для вырожденных систем будут рассмотрены способы для снятия вырождения, т. е. для перехода к невырожденным системам того же порядка в подходящем фактор-кольце (см. теоремы 3—5). В частности, можно снять вырождение, если коэффициенты системы порождают главный идеал и кольцо R содержит 1, это, к примеру, позволяет находить решение произвольной системы над коммутативным кольцом главных идеалов с единицей.

1. Невырожденные системы. Систему линейных уравнений A′x′ = a′ над коммутативным кольцом R′ назовем φ-эквивалентной системе (1), если существует такой гомоморфизм φ : R → R′, что

{x : Ax = a} = φ^{−1}{x′ : A′x′ = a′}.

В случае, когда φ – тождественный автоморфизм, получаем обычную эквивалентность систем.

Теорема 1 Пусть N ⊂ R и Ann N – аннулятор множества N, тогда

⋂_{δ∈N}{x : δAx = δa}

является множеством решений системы Ax = a mod (Ann N)^{n}, где ( )^{n} обозначает n-ю кронекерову степень.

∗МАТЕМАТИЧЕСКИЕ ЗАМЕТКИ т. 42, � 4 (1987)

Доказательство. Пусть t — одно из решений этой системы, тогда найдется такое b ∈ (Ann N)^{n}, что At = a + b. Так как δb = 0 ∀δ ∈ N, то, умножая последнее равенство на δ, находим δAt = δa ∀δ ∈ N. И наоборот, если δAt = δa ∀δ ∈ N и Ann δ – аннулятор δ, то At − a ∈ (Ann δ)^{n} ∀δ ∈ N. Так как ⋂_{δ∈N} Ann δ = Ann N, то отсюда At − a ≡ 0 mod (Ann N)^{n}.

В частности, когда N = {δ}, получим

Следствие 1. Пусть δ ∈ R, R′ = R/Ann δ – фактор-кольцо и φ : R → R′ – канонический гомоморфизм. Тогда система δAx = δa над R φ-эквивалентна системе φ(A)x′ = φ(a) над R′.

Это следствие позволяет избавиться от общих множителей у коэффициентов системы. Пусть теперь δ – это некоторый минор порядка r матрицы A. Не уменьшая общности,

положим, что δ = det A_{0},

A = (A′, A′′), A′ = ( \begin{matrix}A_{0} \\ A_{1} \end{matrix} ) , A′′ = ( \begin{matrix}B_{0} \\ B_{1} \end{matrix} ) , x = ( \begin{matrix}x_{0} \\ x_{1} \end{matrix} ) , a = ( \begin{matrix}a_{0} \\ a_{1} \end{matrix} ) .  (2)

Введем также четыре типа миноров, связанных с минором δ: δ_{ij} – минор, полученный окаймлением минора δ строкой i и столбцом j матрицы A^{∗}, δ^{(ij)} – минор, который будет стоять на месте минора δ, если в матрице A^{∗} столбец i заменить на столбец j, δ_{(ij)} – минор, который будет стоять на месте минора δ, если в матрице A^{∗} строку i заменить на строку j, δ^{ij} — алгебраическое дополнение элемента (i, j) в матрице A_{0}. И соответственно введем четыре новые матрицы и два вектора, элементами которых являются эти миноры:

D = ∥δ_{ij}∥ (i = r + 1, …, n; j = r + 1, …, m);
d = ∥δ_{i,m+1}∥ (i = r + 1, …, n);  (3)
D_{C} = ∥δ^{(ij)}∥ (i = 1, …, r; j = r + 1, …, m);
d_{C} = ∥δ^{(i,m+1)}∥ (i = 1, …, r);
D_{L} = ∥δ_{(ij)}∥ (i = 1, …, r; j = r + 1, …, n);
D_{O} = ∥δ^{ij}∥ (i = 1, …, r; j = 1, …, r).

Теорема 2 Системы линейных уравнений

\{ \begin{matrix}δA_{0}x_{0} & + & δB_{0}x_{1} & & & = & δa_{0} \\ δA_{1}x_{0} & + & δB_{1}x_{1} & & & = & δa_{1} \\ δx_{0} & + & D_{C}x_{1} & − & x_{2} & = & d_{C} \end{matrix}

и

\{ \begin{matrix}δx_{0} & + & D_{C}x_{1} & − & x_{2} & = & d_{C} \\ & & Dx_{1} & + & A_{1}x_{2} & = & d \\ & & & & A_{0}x_{2} & = & 0 \end{matrix}

эквивалентны.

Доказательство. Преобразуем первую систему: из первого и второго уравнения вычтем третье уравнение, умножая его предварительно на A_{0} и A_{1} соответственно. Для получения второй системы теперь осталось воспользоваться легко проверяемыми тождествами A_{0}D_{C} = δB_{0}, D = δB_{1} − A_{1}D_{C}, d = δa_{1} − A_{1}d_{C}.

Вторую систему назовем канонической. Доказанная теорема позволяет искать решения системы δAx = δa, поочередно решая подсистемы меньшего порядка, входящие в каноническую систему. Если же система (1) невырожденная, то у матрицы A найдется такое множество миноров N, что Ann N = 0, и по теореме 1 решение системы (1) сводится к нахождению пересечения решений совокупности систем δAx = δa, δ ∈ N.

Систему линейных уравнений называют согласованной по рангу, если ранг основной и расширенной матрицы коэффициентов системы равны [1]. Как известно, не согласованные по рангу системы несовместны.

Рассмотрим теперь некоторые следствия теоремы 2, при этом учтем, что если δ – не делитель нуля, то система A_{0}x_{2} = 0 имеет только нулевое решение и системы Ax = a и δAx = δa эквивалентны.

Следствие 1. Если система (1) согласована по рангу, δ ≠ 0 и r = rankA, то каноническая система сводится к трем подсистемам A′x_{2} = 0, D_{C}x_{1} ≡ (d_{C} + x_{2}) mod (δR)^{r}, δx_{0} = d_{C} + x_{2} − D_{C}x_{1}.

Следствие 2.Если δ – не делитель нуля, то система (1) сводится к двум подсистемам Dx_{1} = d, δx_{0} = d_{C} − D_{C}x_{1}.

Следствие 3. Если система (1) согласована по рангу, r = rankA и δ – не делитель нуля, то система (1) сводится к двум подсистемам D_{C}x_{1} ≡ d_{C} mod (δR)^{r} и δx_{0} = d_{C} − D_{C}x_{1}

2. Вырожденные системы. Пусть J и J^{∗} – идеалы, порожденные элементами матриц A и A^{∗} соответственно. Для совместности системы (1), очевидно, необходимо, чтобы эти идеалы были равны.

Теорема 3 Пусть R содержит единицу, λ ∈ R, J = J^{∗} = λR – ненулевой главный идеал и φ : R → R/Ann λ – канонический гомоморфизм, тогда система (1) φ-эквивалентна невырожденной системе φ(G)x′ = φ(g), при этом матрица G = ∥γ_{i,j}∥ (i = 1, …, n; j = 1, …, m) и вектор g = ∥γ_{i,m+1}∥ (i = 1, …, n) определяются равенством (A a) = λ(G g).

Доказательство. φ-эквивалентность систем устанавливается следствием 1 теоремы 1. Покажем, что φ(G)x′ = φ(g) – невырожденная система. По условию a_{ij} = λγ_{ij} и найдутся такие элементы τ_{ij} ∈ R, что ∑_{i=1}^{n} ∑_{j=1}^{m} τ_{ij}a_{ij} = λ. Отсюда следует, что ∑_{i=1}^{n} ∑_{j=1}^{m} τ_{ij}γ_{ij}−1 ∈ Ann λ, и в соответствии с гомоморфизмом φ находим, что ∑_{i=1}^{n} ∑_{j=1}^{m} φ(τ_{ij})φ(γ_{ij}) = φ(1), т. е. элементы матрицы φ(G) порождают единичный идеал.

Теорема 4 Пусть J = J^{∗} ≠ 0, Ann J ⋂ J = 0 и φ : R → R/Ann J — канонический гомоморфизм. Тогда система (1) φ-эквивалентна невырожденной системе φ(A)x′ = φ(a).

Доказательство. Пусть для некоторого t ∈ R^{m} φ(A)φ(t) = φ(a), тогда At − a ∈ (Ann J)^{n}, но At − a ∈ J^{n}, а по условию теоремы Ann J ⋂ J = 0, следовательно, At = a, т. е. имеет место φ-эквивалентность. Пусть теперь μ ∈ φ^{−1}(Ann φ(J)). Тогда для каждого элемента a матрицы A φ(μ)φ(a) = 0, следовательно, μa ∈ Ann J, но μa ∈ J , отсюда μa = 0. Таким образом, μ ∈ Ann J и φ(μ) = 0, следовательно, Ann φ(J) = 0, что доказывает невырожденность.

Теорема 5 Пусть J = J^{∗} ≠ 0 и I_{i} (i = 1, …, k) – такие идеалы, кольца R, что λJ ⊈ I_{i} ∀λ ∈ R \ I_{i}, и ⋂_{i=1}^{k} I_{i} ⋂ J = 0, φ_{i} : R → R/I_{i} – канонические гомоморфизмы. Тогда

⋂_{i=1}^{k} φ_{i}^{−1}{x_{i} : x_{i} ∈ R/I_{i}, φ_{i}(A)x_{i} = φ_{i}(a)}

является множеством решений системы (1), а каждая система φ_{i}(A)x_{i} = φ_{i}(a) не вырождена.

Доказательство. Пусть t ∈ R^{m} и φ_{i}(A)φ_{i}(t) = φ_{i}(a) ∀i, тогда At − a ∈ I_{i} ∀i, но At − a ∈ J^{n} и по условию ⋂_{i=1}^{k} I_{i} ⋂ J = 0, следовательно, At − a = 0.

И наоборот, если At = a, то φ_{i}(A)φ_{i}(t) = φ_{i}(a) ∀i.

Покажем теперь невырожденность. Пусть μ ∈ φ_{i}^{−1}(Ann φ_{i}(J)), тогда для каждого элемента a матрицы A φ_{i}(μ)φ_{i}(a) = 0, т. е. μa ∈ I_{i}. Следовательно, μJ ⊂ I_{i}, но по условию λJ ⊈ I_{i} ∀λ ∈ R \ I_{i}, значит, μ ∈ I_{i}. Таким образом, Ann φ_{i}(J) = 0.

3. Построение канонической системы. Для любых целых чисел r, n, m таких, что 1 ⩽ r ⩽ n, 1 ⩽ r ⩽ m, можно ввести функцию F_{r} : R^{n×m} → R^{n×m}, которую назовем обращающей функцией порядка r, определив ее уравнением

F_{r}(A) = ( \begin{matrix}E_{δ} & D_{C} \\ 0 & D \end{matrix} ) .

Здесь и ниже мы используем обозначения (2) и (3), а через E_{ξ} обозначаем матрицы вида diag(ξ, ξ, … ξ) ∀ξ ∈ R. Отметим, что определенная таким образом функция позволяет обратить матрицу A^{∗} в расширенную матрицу коэффициентов канонической системы без неизвестного x_{2}:

F_{r}(A^{∗}) = (\begin{matrix}E_{δ} & D_{C} & d_{C} \\ 0 & D & d \end{matrix})

которая легко достраивается до полной канонической системы.

Введем также для матрицы A′ ∈ R^{n×r} (n ⩾ r) ее обращающую матрицу

Â′ = ( \begin{matrix}D_{O}^{T} & 0 \\ D_{L}^{T} & E_{δ} \end{matrix} ) ∈ R^{n×n}.

Заметим, что для квадратной матрицы ее обращающей матрицей будет присоединенная матрица. Как обобщение соответствующего равенства для присоединенной матрицы име-

ет место следующее равенство: Â′ · A′ = ( \begin{matrix}E_{δ} \\ 0 \end{matrix} ). Непосредственной проверкой можно

показать справедливость следующих предложений.

Предложение 1. Вычисление обращающей функции порядка r матрицы A осуществляется умножением матрицы A слева на обращающую матрицу такой подматрицы, которая образована первыми r столбцами матрицы A : F_{r}(A) = Â′ · A.

Предложение 2. Элементы обращающей матрицы могут быть вычислены с помощью обращающей функции:

F_{r}(A_{0}^{T} A_{1}^{T} E_{ξ}) = (E_{δ} D_{L} ξ · D_{O}).

Другим способом вычисления обращающей функции является метод прямого и обратного хода, который получается простым обобщением метода, описанного в [2]. Обозначая через α_{ij}^{k} минор порядка k матрицы A^{∗}, образованный окаймлением минора порядка k − 1, стоящего в верхнем левом углу, строкой i и столбцом j, можем записать детерминантные тождества прямого хода

α_{ij}^{k+1}α_{k−1,k−1}^{k−1} = α_{kk}^{k}α_{ij}^{k} − α_{ik}^{k}α_{kj}^{k}
(2 ⩽ k ⩽ r, k < i ⩽ n, k < j ⩽ m + 1)

и деторминантные тождества обратного хода

δ^{(kp)}α_{k,k}^{k} = δα_{kp}^{k} − ∑_{j=k+1}^{r} δ^{(ip)}α_{kj}^{k}

(1 ⩽ k ⩽ r, r + 1 ⩽ p ⩽ m + 1).

Если среди угловых миноров α_{kk}^{k} (k = 1, 2, …, r − 1) нет делителей нуля, то, применяя тождества прямого хода, найдем все окаймляющие миноры вплоть до миноров порядка r+ 1, при этом получим все элементы δ_{ij} = α_{ij}^{r+1} матрицы (D d), элементы δ^{(rj)} = α_{rj}^{r} последней строки r матрицы (D_{C} d_{C}) и минор δ = α_{rr}^{r}. Затем, применяя тождества обратного хода, найдем все остальные элементы δ^{(kp)} матрицы (D_{C} d_{C}).

СКТБ Фпзпко-механпческого Поступило института АН УССР 16.09.85

СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ

[1] Клейнер Г. Б. О системах линейных уравнении над коммутатпнными кольцами // УМН. 1973. Т. 28, выц. 6. С. 211–212.

[2] Малaшонок Г. И. Решение системы линейных уравнений в целостном кольцо // Журн. вычисл. математики п мат. физики. 1983. Т. 23, � 6. С. 1497–1500.