On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals
We propose new necessary and sufficient conditions for the solvability of a system of linear equations over the domain of principal ideals and an algorithm for the solution of this system.
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2014
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/2159 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860508100071522304 |
|---|---|
| author | Prokip, V. M. Прокіп, В. М. |
| author_facet | Prokip, V. M. Прокіп, В. М. |
| author_sort | Prokip, V. M. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T10:25:15Z |
| description | We propose new necessary and sufficient conditions for the solvability of a system of linear equations over the domain of principal ideals and an algorithm for the solution of this system. |
| first_indexed | 2026-03-24T02:19:50Z |
| format | Article |
| fulltext |
УДК 512.643.4
В. М. Прокiп (Iн-т прикл. проблем механiки i математики НАН України, Львiв)
ПРО РОЗВ’ЯЗНIСТЬ СИСТЕМИ ЛIНIЙНИХ РIВНЯНЬ
НАД ОБЛАСТЮ ГОЛОВНИХ IДЕАЛIВ
We propose new necessary and sufficient conditions for the solvability of a system of linear equations over the domain of
principal ideals and an algorithm for the solution of this system.
Установлены необходимые и достаточные условия разрешимости системы линейных уравнений над областью глав-
ных идеалов. Предложен метод нахождения ее решений.
Вступ. Нехай R — комутативна область головних iдеалiв з одиницею e 6= 0, Mm,n(R) —
множина (m× n)-матриць над R, In — одинична матриця вимiрностi n; 0m,k — нульова (m×k)-
матриця.
Розглянемо систему лiнiйних неоднорiдних рiвнянь
Ax = b, (1)
де A ∈ Mm,n(R), b ∈ Mm,1(R), b 6= 0m,1, i x — невiдомий елемент iз Mn,1(R). Методам
розв’язностi систем лiнiйних рiвнянь (1) присвячено значну кiлькiсть робiт. Це обумовлено
не лише академiчним iнтересом до цiєї задачi [1 – 6], але i багатьма задачами прикладного
характеру, для розв’язування яких використовуються системи лiнiйних рiвнянь [7, 8].
Нехай A ∈Mm,n(R), b ∈Mm,1(R) i Ā =
[
A b
]
∈Mm,n+1(R) — розширена матриця сис-
теми лiнiйних рiвнянь (1). Нехай, далi, dk(A) i dk(Ā) — iдеали кiльця R, якi породженi мiнорами
k-го порядку матриць A i Ā вiдповiдно, k = 1, 2, . . . ,min{m,n}. Вiдомо (див. [1, 2, 4 – 6]), що
система лiнiйних неоднорiдних рiвнянь Ax = b над областю головних iдеалiв R розв’язна
тодi i тiльки тодi, коли rank A = rank Ā = r i dk(A) = dk(Ā) для всiх k = 1, 2, . . . , r, тобто
коли форми Смiта матриць
[
A 0m,1
]
i
[
A b
]
збiгаються мiж собою. В цiй статтi в термi-
нах форм Ермiта матриць
[
A 0m,1
]
i
[
A b
]
встановлено простiший критерiй розв’язностi
системи лiнiйних неоднорiдних рiвнянь (1) над областю головних iдеалiв та запропоновано
метод знаходження її розв’язкiв. Наведенi результати справедливi для матриць над областями
елементарних дiльникiв та областями Безу. Крiм того, вони можуть бути узагальненi для сис-
тем лiнiйних неоднорiдних рiвнянь над комутативними кiльцями бiльш загальної алгебраїчної
природи.
Основнi результати. Нижче встановимо необхiднi та достатнi умови розв’язностi системи
лiнiйних неоднорiдних рiвнянь над областю головних iдеалiв. В областi головних iдеалiв R
зафiксуємо множину неасоцiйованих елементiв R̃. Кожному неасоцiйованому елементу a ∈ R̃
поставимо у вiдповiднiсть повну систему лишкiв за модулем iдеалу (a).
Нехай A ∈ Mm,n(R) — матриця рангу rankA = r над областю головних iдеалiв R. Якщо
перший рядок матрицi A не нульовий, то для A iснує матриця W ∈ GL(n,R) така, що
AW = HA =
H1 0m1,n−1
H2 0m2,n−2
. . . . . .
Hr 0mr,n−r
, m1 + m2 + . . . + mr = m.
c© В. М. ПРОКIП, 2014
566 ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
ПРО РОЗВ’ЯЗНIСТЬ СИСТЕМИ ЛIНIЙНИХ РIВНЯНЬ НАД ОБЛАСТЮ ГОЛОВНИХ IДЕАЛIВ 567
Якщо ж A ∈ Mm,n(R) — матриця рангу rankA = r, в якiй першi k рядки є нульовими, тобто
A =
[
0k,n
A1
]
, k ≥ 1, а перший рядок матрицi A1 вiдмiнний вiд нульового, то для A iснує матриця
W1 ∈ GL(n,R) така, що
AW1 = HA =
0k,n
H1 0m1,n−1
H2 0m2,n−2
. . . . . .
Hr 0mr,n−r
, k + m1 + m2 + . . . + mr = m.
Матрицi Hi в нижнiй блочно-трикутнiй матрицi HA визначено таким чином:
H1 =
[
a1
∗
]
∈Mm1,1(R), H2 =
[
h̃21 a2
∗ ∗
]
∈Mm2,2(R), . . . ,
Hr =
[
h̃r1 . . . h̃r,r−1 ar
∗ ∗ ∗ ∗
]
∈Mmr,r(R),
де елементи ai належать множинi неасоцiйованих елементiв R̃ при всiх i = 1, 2, . . . , r. Крiм
цього, в перших рядках
[
h̃i1 . . . h̃i,i−1 ai
]
матриць Hi, i ≥ 2, елементи h̃ij належать
повнiй системi лишкiв за модулем iдеалу (ai) при всiх j = 1, 2, . . . , i − 1. Нижня блочно-
трикутна матриця HA називається (правою) формою Ермiта матрицi A, i вона для матрицi
A визначена однозначно (див. [6]). Далi пiд термiном „форма Ермiта матрицi A” будемо
розумiти, що матриця A ∈ Mm,n(R) домноженням справа на зворотну матрицю iз GL(n,R)
зводиться до матрицi HA, яка визначена вище.
Теорема 1. Система лiнiйних неоднорiдних рiвнянь
Ax = b, (2)
де A ∈ Mm,n(R) i b ∈ Mm,1(R), розв’язна тодi i тiльки тодi, коли форми Ермiта матриць[
A 0m,1
]
i
[
A b
]
збiгаються мiж собою.
Доведення. Нехай x0 ∈ Mn,1(R) — розв’язок системи рiвнянь (2). Розглянемо матрицю
V =
[
In x0
01,n −e
]
. Очевидно, що
[
A b
]
V =
[
A 0m,1
]
.
Оскiльки V ∈ GL(n + 1,R), то матрицi
[
A b
]
i
[
A 0m,1
]
є прaвоеквiвалентними. Отже,
форми Ермiта матриць
[
A b
]
i
[
A 0m,1
]
збiгаються мiж собою.
Навпаки, нехай форми Ермiта матриць
[
A b
]
i
[
A 0m,1
]
збiгаються мiж собою, тобто[
A b
]
U = H[Ab] =
[
A 0m,1
]
V = H[A 0],
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
568 В. М. ПРОКIП
де U, V ∈ GL(n + 1,R). З останньої рiвностi отримуємо, що матрицi
[
A b
]
i
[
A 0m,1
]
є
прaвоеквiвалентними, тобто [
A b
]
=
[
A 0m,1
]
W. (3)
Матрицю W запишемо у виглядi W =
[
W11 W12
W21 W22
]
, де W11 ∈ Mn,n(R), W12 ∈ Mn,1(R) i
W22 ∈ R. Тепер з рiвностi (3) отримуємо
AW11 = A i AW12 = b.
З останньої рiвностi випливає розв’язнiсть системи лiнiйних неоднорiдних рiвнянь (2), що i
доводить теорему.
Iз теореми 1 випливають наступнi твердження.
Наслiдок 1. Нехай A ∈Mm,n(R) i B ∈Mm,k(R) — ненульовi матрицi. Матричне рiвняння
AX = B
розв’язне тодi i тiльки тодi, коли форми Ермiта матриць
[
A 0m,k
]
i
[
A B
]
збiгаються
мiж собою.
Наслiдок 2. Нехай A ∈ Mm,n(R) i B ∈ Mm,k(R) — ненульовi матрицi. Матриця B є
лiвим дiльником матрицi A, тобто A = BC, тодi i тiльки тодi, коли форми Ермiта матриць[
B 0m,n
]
i
[
B A
]
збiгаються мiж собою.
Наступний наслiдок встановлює умови розв’язностi матричних дiофантових рiвнянь (див.
[8], роздiл 6, теорема 6.1.1).
Наслiдок 3. Нехай A ∈ Mm,n(R), B ∈ Mm,k(R), C ∈ Mm,l(R) i C 6= 0m,l. Матричне
дiофантове рiвняння
AX + BY = C
розв’язне тодi i тiльки тодi, коли форми Ермiта матриць
[
A B 0m,l
]
i
[
A B C
]
збiгаються мiж собою.
Алгоритм знаходження розв’язкiв. Наведемо алгоритм розв’язування системи лiнiйних
неоднорiдних рiвнянь над областю головних iдеалiв.
Нехай A ∈ Mm,n(R) — матриця рангу rank A = r ≥ 1 i b ∈ Mm,1(R) – ненульовий
стовпчик. Розглянемо систему лiнiйних неоднорiдних рiвнянь Ax = b. Оскiльки rank A ≥ 1,
то, не обмежуючи загальностi, будемо припускати, що в системi лiнiйних неоднорiдних рiвнянь
Ax = b перший рядок матрицi A є ненульовим. Нехай, далi, W ∈ GL(n,R) така, що
AW = HA =
H1 0m1,n−1
H2 0m2,n−2
. . . . . .
Hr 0mr,n−r
, Hi ∈Mmi,i(R), i = 1, 2, . . . , r,
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
ПРО РОЗВ’ЯЗНIСТЬ СИСТЕМИ ЛIНIЙНИХ РIВНЯНЬ НАД ОБЛАСТЮ ГОЛОВНИХ IДЕАЛIВ 569
— форма Ермiта матрицi A. Очевидно, що системи лiнiйних рiвнянь Ax = b i HAy = b, де
y = W−1x, розв’язнi або нерозв’язнi одночасно. Матрицi H2, H3 , . . . , Hr та стовпчик b
запишемо у виглядi
H2 =
a2
H21 hm2,2
...
hm2,m2
, H3 =
a3
H31 hm3,2
...
hm3,m3
, . . . ,Hr =
ar
Hr1 hmr,2
...
hmr,mr
,
b =
b1
b2
...
br
, y =
y1
y2
...
yn
, де Hk1 ∈ Mmk,k−1(R) для всiх k = 2, 3, . . . , r i bi ∈ Mmi,1(R) для всiх
i = 1, 2, . . . , r.
Тепер систему лiнiйних рiвнянь HAy = b запишемо у виглядi
a1
hm1,2
...
hm1,m1
y1 = b1,
a2
hm2,2
...
hm2,m2
y2 = b2 −H21y1,
(4)
a3
hm3,2
...
hm3,m3
y3 = b3 −H31
[
y1
y2
]
,
. . . . . . . . . . . . . . . . . . . . .
ar
hmr,2
...
hmr,mr
yr = br −Hr1
y1
y2
...
yr−1
, r ≤ n.
Cистема рiвнянь (4) розв’язується безпосередньою пiдстановкою, яка виконується зверху
донизу. З першого рiвняння знаходимо y1. Пiдставляючи y1 у друге рiвняння, знаходимо y2.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
570 В. М. ПРОКIП
Аналогiчнi мiркування проводимо з рештою рiвнянь. В результатi отримуємо розв’язок y сис-
теми рiвнянь HAy = b. Тодi x = Wy — розв’язок системи рiвнянь Ax = b. Очевидно, якщо
хоча б одне з рiвнянь системи (4) не є розв’язним, то i система (4) також не має розв’язкiв.
Нехай система лiнiйних рiвнянь Ax = b розв’язна, де A ∈ Mm,n(R) i b ∈ Mm,1(R). Якщо
rank A = n, то система рiвнянь HAy = b має єдиний розв’язок. Тодi x = Wy — єдиний
розв’язок системи рiвнянь Ax = b. Якщо ж rankA = r < n, то iз системи рiвнянь HAy = b
невiдомi y1, y2, . . . , yr визначаються однозначно, а невiдомi yr+1, yr+2, . . . , yn можуть бути
вибранi довiльно, тобто вони є вiльними змiнними. Тодi загальний розв’язок x = Wy системи
рiвнянь Ax = b залежить вiд вiльних змiнних yr+1, yr+2, . . . , yn.
1. Казимирский П. С. Условия совместности неоднородной системы линейных уравнений в некоммутативном
кольце главных идеалов // Науч. зап. Львов. политехн. ин-та. Сер. физ.-мат. – 1955. – 30, вып. 1. — С. 45 – 51.
2. Клейнер Г. Б. О системах линейных уравнений над коммутативными кольцами // Успехи мат. наук. – 1973. –
286, № 6. – С. 211 – 212.
3. Елизаров В. П. Условия, необходимые для разрешимости системы линейных уравнений над кольцом // Дискрет.
математика. – 2004. – 16, № 2. – С. 44 – 53.
4. Newman M. The Smith normal form // Linear Algebra and Appl. – 1997. – 254. – P. 367 – 381.
5. Hermida-Alonso J. A. On linear algebra over commutative rings // Handbook Algebra. – 2003. – 3. – P. 3 – 61.
6. Friedland S. Matrices. – Chicago: Univ. Illinois at Chicago, 2010. – 437 p.
7. Mulders T., Storjohann A. Certified dense linear system solving // J. Symbol. Comput. – 2004. – 37, № 4. –
P. 485 – 510.
8. Kaczorek T. Polynomial and rational matrices. applications in dynamical systems theory, communications and control
engineering. – Dordrecht: Springer, 2007. – 503 p.
Одержано 15.02.13
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 4
|
| id | umjimathkievua-article-2159 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:19:50Z |
| publishDate | 2014 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/c2/991ec4b16efafb7f4e8cf637da42f6c2.pdf |
| spelling | umjimathkievua-article-21592019-12-05T10:25:15Z On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals Про розв’язність системи лінійних рівнянь над областю головних ідеалів Prokip, V. M. Прокіп, В. М. We propose new necessary and sufficient conditions for the solvability of a system of linear equations over the domain of principal ideals and an algorithm for the solution of this system. Установлены необходимые и достаточные условия разрешимости системы линейных уравнений над областью главных идеалов. Предложен метод нахождения ее решений. Institute of Mathematics, NAS of Ukraine 2014-04-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/2159 Ukrains’kyi Matematychnyi Zhurnal; Vol. 66 No. 4 (2014); 566–570 Український математичний журнал; Том 66 № 4 (2014); 566–570 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/2159/1320 https://umj.imath.kiev.ua/index.php/umj/article/view/2159/1321 Copyright (c) 2014 Prokip V. M. |
| spellingShingle | Prokip, V. M. Прокіп, В. М. On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals |
| title | On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals |
| title_alt | Про розв’язність системи лінійних рівнянь над областю головних ідеалів |
| title_full | On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals |
| title_fullStr | On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals |
| title_full_unstemmed | On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals |
| title_short | On the Solvability of a System of Linear Equations Over the Domain Of Principal Ideals |
| title_sort | on the solvability of a system of linear equations over the domain of principal ideals |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/2159 |
| work_keys_str_mv | AT prokipvm onthesolvabilityofasystemoflinearequationsoverthedomainofprincipalideals AT prokípvm onthesolvabilityofasystemoflinearequationsoverthedomainofprincipalideals AT prokipvm prorozvâznístʹsistemilíníjnihrívnânʹnadoblastûgolovnihídealív AT prokípvm prorozvâznístʹsistemilíníjnihrívnânʹnadoblastûgolovnihídealív |