Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 196

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

382 ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

 

Л емма 19.1.

Фактор-модуль

{А}/ кег фВ- 1

и группа{а'}

изо­

морфны х). Эта

лемма

в более общем виде формулируется

так:

пусть / — гомоморфизм модулей {А} и

{А'}.

Тогда ядро f

обра­

зует нормальный

подмодуль

{Н} модуля {А} и отображение

/*:

{А}/{Н} -> {А '},

 

определенное соотношением /*

(aj

+ Н)

=

=

/ (at), является изоморфизмом между

{А}/{Н}

и {А'} 2)*-

 

 

 

Д оказательство.

 

Пусть

х — произвольный

элемент

ядра

/,.

т. е. / (х)

= 0',

где 0'

— нейтральный или нулевой элемент {А"}.

Пусть

aj — произвольный

 

элемент

из

{А}.

Тогда

/ (— aj +

х +

а,)

=

/ (— at)

+

/ (х) +

/ (аД

=

/ (— аД +

0 ' +

+

/ (аД = —/ (аД +

/ (а^

=

0'. Это означает, что —

+

х +

а*

принадлежит

Н

или

—ai +

Н + ai содержится в Н. Меняя

местами af и

—ai

в рассуждении, мы можем показать, что at +

+

х — at также принадлежит Н, или что aj +

Н — at содержит­

ся

в Н.

Заменяя

х

на

at +

Н — alt

получаем,

что

—а4 +

+

(ai +

Н — ai) +

aj

содержится в —а4 +

Н + at

или что Н

содержится в —aj +

Н +

at. Следовательно,

Н = —at +

Н +

+

aj для любого элемента

aj £

{А} и,

значит,

Н — нормальный

подмодуль модуля {А}.

 

 

утверждения

предположим,

что-

 

Для доказательства второго

aj и а2 принадлежат одному смежному классу по Н. Так как Н — подмодуль, то —aj + а2 также принадлежит Н и / (—at + а2)| =

=

0'. Используя этот факт,

получаем

 

 

 

/ (а2) = / (а4 — aj + а2) = / (аД + / (—а4 + а2) =

 

 

 

 

 

 

 

 

 

= / (аД + 0' = / (аД-

Следовательно,

/*

отображает

все элементы любого смежного-

класса

{А}

по Н в один элемент из {А '},

т. е. если aj

+ Н =

=

а2 +

Н,

то

/ ( аД = / ( а2). Положим /

=

ф £ _1.и

 

 

Л емма 19.2.

кег ф В -1 =

{В}.

 

 

 

 

Д оказательство.

 

 

 

 

 

 

 

 

П

 

 

 

п

 

 

 

 

 

2

h j & ] 6 кег ф В-1 <=> ф (В -1 ( ^

М с ) ) — 0 <=>

 

 

 

3= 1

 

 

 

1 = 1

 

 

 

 

 

П

 

 

 

 

 

 

 

 

<=> В"1 ( I 1 V

j) = Р (J* —некоторый целочисленный вектор) <=>

 

 

i — 1

п

 

т

п

 

 

 

 

 

 

 

 

 

 

 

 

 

2 ^7®; “ В(1 =

2

fnbj Cv- 2

kjbj 6 {В}. Щ

 

 

 

 

3 = 1

 

i = l

3 = 1

 

 

 

 

!) Здесь и далее

под модулем

подразумевается аддитивная

абелева)

группа без операторов, которую можно рассматривать как модуль над коль­ цом целых чисел.— Прим. ред.

2) Доказательство леммы 19.1 содержится по существу в теореме о гомо­ морфизмах групп. См., например Ван-дер-Варден Б. Л., Современная алгеб­ ра, ОГИЗ, М., 1947.— Прим, перее.

19.1. ВВЕДЕНИЕ

383

Теорема 19.2. {А}/{В} ^ {а ).

Эта теорема непосредственно следует из лемм 19.1 и 19.2.

Как отмечалось ранее, В является базисом в R, так что каж­ дый вектор можно выразить через векторы из В, если допустимы действительные коэффициенты. Если бы линейные комбинации векторов из В с целочисленными коэффициентами содержали все векторы из А, то фактор-модудь {А}/{В} состоял бы только

из нейтрального элемента 0 + {В} и модуль {а'} также содержал бы только один элемент нуль. Следовательно, порядок модуля

{а} в некотором смысле является мерой невозможности получения векторов А с помощью целочисленных линейных комбинаций век­ торов из В.

Изучим структуру фактор-модуля {Z}/{B}. Так как {Z} — множество m-мерных векторов, то единичные векторы ег (i = 1 , . . ., т)

“ O’

6

ег = 1

(—i-я компонента

О

служат базисом для {Z}, а также, конечно, и для {В}, где

bj= 2 btfii

(/ = 1, . . . , т ) .

г—\

Следовательно, матрица В

Ьд • • • Ьт

ei ъп him

«2 ^21 Ь%т

- ^ml Ьтт -

выражает каждый вектор Ь* через векторы е;-.

384 ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Изменяя базисные векторы Ьг и единичные векторы ej, мы можем сделать матрицу диагональной

bj

b2 .. • ь„

 

 

е 2

= в \

 

 

 

^7П-

 

где ег является делителем

ег+ 1 (i = 1, . . т — 1). (Процесс

приведения матрицы к нормальной форме Смита детально описан в приложении А). Поскольку этот процесс не изменяет величины

определителя, D =

| det

В | = | det

В' |

=

е^ е^ . . .

гт и bj

=

= егв{ (i = 1,

. . .,

т).

Так как система е\

(i

= 1, . . .,

т) являет­

ся базисом для

{Z}, то

 

 

 

 

 

 

 

(Z) =

ze, © ze2 ®

.. . ®.zeJn

(z —любые целые),

(2)

а так как bj

(i = l,

.. .,

т) является

базисом для {В},

то

 

{В} = zb' ® zb' © . . . ® zb'm= zBfil ф ze2e2 © . . . © zBme'm. (3)

Из (2) и (3) следует

{Z}/{B} = {ze[ ф ze'2 ф . . . © ze^ }/-^ ^ ф ze2e' ф . . . ф ггте'т} ^

^ {ze[}l{ze.&[} ф (ze'}/{ze2e'} ф . . . @ {ze'm}l{zBme'm} s*

^ (z}/{ze'} Ф'(г}/{ге2} ф . . . ф {z}!{z&'m}.

Заметим, что Ь| = е,еь поэтому в группе zej/zgjej не более чем е*

элементов,

а именно 0 , е'{, 2 ej,

. . . , (ej — 1 )

 

и следовательно,

порядок этой циклической группы равен е,.

 

 

 

 

Итак, {Z}/{B} — прямая сумма т циклических групп,

поря­

док i-й циклической группы

равен

ег (i =

1 ,

. .

т), где ег

делит е;+1. Поэтому

порядок группы

{Z}/{В}

равен

е г е 2* . . .

. . . • Ет =

D.

— индекс

подгруппы

(А ) в группе

{Z},

Пусть

[{Z} : {А}]

а [{А} : {В}] — индекс подгруппы {В} в {А}. Тогда

D =

[{Z}

: {В}] = [{Z} : {А }].[{А } : {В}],

так как (А ) гз

{В}.

Это означает, что [{А} : {В}] всегда делит D.

Если бы матрица А содержала единичную подматрицу размер­ ности т X т, то {Z} = {А} и [{Z} : {А}] = 1, так что

D = l{ А> : {В}] = |

|.

Так как группа {а} изоморфна {А }/{В },

мы получаем следующую

теорему.

 

 

 

 

19. f . ВВЕДЕНИЕ

 

385

Т е о р е м а 19.3.

Для любой целочисленной матрицы А, ее под­

матрицы В и а =

В - 1 А существуют положительные целые числа

«г (г = 1 ,

. . .,

т),

такие,

что ег

делит ег-и (г = 1 , . .

т — 1 )

е2- . . .

• em

=

D = | det В |,

и

{а}

изоморфна модулю

 

 

 

Z

Z

 

 

Z

 

 

 

 

еjz

e2z

 

 

emz

 

шга же одному

из

его подмодулей.

Порядок {а} никогда не пре­

вышает D

и всегда делит D. Если А содержит единичную подмат­

рицу, то {А}/{В} имеет порядок D.

 

 

 

Ранее

было

показано,

что строки

(/0, /ь . . . , / „ )

образуют

абелеву группу с операцией сложения по модулю 1 и, кроме того,

что эта абелева группа есть прямая сумма нескольких цикличе­

ских

групп,

имеющих

порядок

е; (i

= 1 , . .

., т), причем

£i-e2-

. . . ет = D.

Рассмотрим

строку

дробей

 

 

 

 

 

f — (Е е

E l

El

’ ' ‘

Рп ^

 

 

 

 

 

'

\ D ’

D ’

D

’ D )

'

 

 

Эта строка является элементом одной из циклических групп.

 

 

Если числа pj (]'

= 0, 1, . . ., п)

и D

не имеют общих множи­

телей, то строка имеет порядок D и, следовательно, порождает

всю группу.

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

 

 

Если числа pj (/

= 0,

1, . . .,

п) и D

имеют общий множитель

с,

то строка имеет порядок Die. Таким образом,

порядок строки

F I

равен общему

знаменателю

 

сокращенных

дробей

p t!D

(i = 0 , 1 , . . ., п).

 

 

 

 

 

 

 

 

 

Мы показали, что {а} изоморфна прямой сумме циклических

групп,

имеющих порядок ег.

 

 

 

 

 

 

 

Т еорема

19.4.

Пусть (т X

п)-матрица

А

содержит

еди­

ничную подматрицу Ет , а матрица В диагонализирована так,

что Ъ\ = ete'i (£

=

1, . . .,

т). Тогда

 

 

 

{« }= {ф в -1 (е;)}© {ф в -1 (е ;)}е

. . .

© {ф в -1^ ) } .

 

Д оказательство.

Пусть

фВ- 1 (е') = hi.

Покажем, что

имеет

порядок

 

 

 

 

 

 

Так как {ос} ^

{А}/{В},

то наименьшим

положительным

крат­

ным е', которое будет обращаться в нуль отображением фВ-1,

является

e1e j= b '. Поэтому фВ- 1 (е^,) = e^B^eJ = ejii =

0

и hi

имеет порядок е4. Подобные рассуждения можно провести

и

для

фВ_1 (е^)}

(г = 1 , . . . , т ) . Таким образом,

 

 

{ос} = {фВ 1 (е,)} ® . . . ® {фВ 1 (em)} = {hi} © {А2} © ■• • © {hm}. щ

25 т. ху

Смотрите также файлы