Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лекції 1-9
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Конспект лекцій
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
§ 1. Основні поняття і теореми
Вступ.
Відображення.
Нехай EMBED Equation.3 s EMBED Equation.3 дві множини. Припустимо, що кожному елементові EMBED Equation.3 множини EMBED Equation.3 поставлено у відповідність деякий елемент EMBED Equation.3 множини EMBED Equation.3 . В такому випадку кажемо, що задана відображення або функцію EMBED Equation.3 із множини EMBED Equation.3 у множину EMBED Equation.3 . Відображення EMBED Equation.3 називається ін’єктивним, якщо воно різним аргументам співставляє різні значення: EMBED Equation.3 для EMBED Equation.3 . Відображення EMBED Equation.3 сюр’єктивне, якщо кожен елемент EMBED Equation.3 з множини EMBED Equation.3 має прообраз–такий елемент EMBED Equation.3 , що EMBED Equation.3 . Бієктивним є відображення, яке ін’єктивне і сюр’єктивне одночасно. Для двох відображень EMBED Equation.3 і EMBED Equation.3 їх композиція EMBED Equation.3 задається співвідношенням EMBED Equation.3 для EMBED Equation.3 . Тотожне відображення EMBED Equation.3 залишає елементи множини EMBED Equation.3 на місці: EMBED Equation.3 . Відображення EMBED Equation.3 вважається лівим оберненим до відображення EMBED Equation.3 за умови, що їх композиція EMBED Equation.3 ; і правим оберненим за умови, що EMBED Equation.3 . Відображення EMBED Equation.3 називається оберненим до EMBED Equation.3 , якщо воно є одночасно і лівим, і правим оберненим до EMBED Equation.3 .
ТЕОРЕМА ПРО ОБЕРНЕНЕ ВІДОБРАЖЕННЯ.
Відображення EMBED Equation.3 ін’єктивне тоді і лише тоді, коли до нього існує ліве обернене.
Відображення EMBED Equation.3 сюр’єктивне тоді і лише тоді, коли до нього існує праве обернене.
Якщо відображення EMBED Equation.3 бієктивне, то його ліве обернене збігається із правим оберненим.
У випадку, коли множини EMBED Equation.3 та EMBED Equation.3 скінченні і містять однакову кількість елементів, відображення EMBED Equation.3 має ліве обернене тоді і тільки тоді, коли воно має праве обернене.
Б.3. Групи. Групою називається множина EMBED Equation.3 , наділена бінарною операцією EMBED Equation.3 з такими властивостями:
EMBED Equation.3 для будь-яких елементів EMBED Equation.3 (асоціативність);
В EMBED Equation.3 існує нейтральний елемент EMBED Equation.3 такий, що EMBED Equation.3 для всіх EMBED Equation.3 ;
Для кожного елемента EMBED Equation.3 в EMBED Equation.3 є обернений елемент EMBED Equation.3 такий, що EMBED Equation.3 .
Якщо підмножина EMBED Equation.3 множини EMBED Equation.3 утворює групу відносно тієї ж операції EMBED Equation.3 , то вона називається підгрупою групи EMBED Equation.3 . Так, множина раціональних чисел EMBED Equation.3 утворює групу за додаванням( EMBED Equation.3 ), а множина цілих чисел EMBED Equation.3 є її підгрупою. Множина додатніх раціональних чисел EMBED Equation.3 утворює групу за множенням( EMBED Equation.3 ). Якщо групову операцію називаємо групу за множенням, то саму групу називаємо мультиплікативною, а її нейтральний елемент-одиницею. Якщо ж операцію називаємо додаванням, то групу називаємо адитивною, нейтральний елемент нулем, а обернений елемент-протилежним елементом.
Для елемента EMBED Equation.3 групи EMBED Equation.3 через EMBED Equation.3 позначається його і-тий степінь–елемент EMBED Equation.3 , де операція виконана і-1 раз. (В адитивній формі те ж саме записується як EMBED Equation.3 ). Нескладною вправою є доведення того, що для кожного елемента EMBED Equation.3 скінченної групи для деякого показника EMBED Equation.3 виконується рівність EMBED Equation.3 . Найменше з таких EMBED Equation.3 називається порядком елемента EMBED Equation.3 у групі EMBED Equation.3 .
Порядком скінченної групи називається кількість її елементів. Легко зауважити, що всі степені елемента групи утворюють у ній підгрупу, порядок якої дорівнює порядку елемента.
ТЕОРЕМА ЛАГРАНЖА(1771).
Порядок підгрупи є дільником порядку групи.
Порядок елемента є дільником порядку групи.
Нехай маємо дві групи EMBED Equation.3 і EMBED Equation.3 з операціями EMBED Equation.3 і EMBED Equation.3 відповідно. Кажемо, що відображення EMBED Equation.3 зберігає операцію, якщо EMBED Equation.3 для всіх EMBED Equation.3 . Таке відображення називається гомоморфізмом з групи EMBED Equation.3 у групу EMBED Equation.3 . Ядром гомоморфізму EMBED Equation.3 є множина всіх тих елементів групи EMBED Equation.3 , які EMBED Equation.3 відображає в нейтральний елемент групи EMBED Equation.3 . Наприклад, відображення, яке кожному цілому числу ставить у відповідність його остачу від ділення на натуральне EMBED Equation.3 , є гомоморфіізмом із адитивної групи EMBED Equation.3 в адитивну групу EMBED Equation.3 , ядро якого утворюють цілі числа, кратні EMBED Equation.3 . Легко показати, що ядро гомоморфізму EMBED Equation.3 утворює в EMBED Equation.3 підгрупу.
Гомоморфізм EMBED Equation.3 є ін’єктивним тоді і лише тоді, коли його ядро складається тільки із нейтрального елемента групи EMBED Equation.3 . Таке ядро називається тривіальним.
Гомоморфізм, який є бієктивним відображенням, називається ізоморфізмом. Дві групи ізоморфні, якщо існує ізоморфізм з однієї з них на іншу. Наприклад, двійковий логарифм EMBED Equation.3 задає ізоморфізм із мультиплікативної групи невід’ємних дійсних чисел EMBED Equation.3 в адитивну групу всіх дійсних чисел EMBED Equation.3 . Ізоморфні групи мають тотожні алгебраїчні властивості.
Для груп EMBED Equation.3 s EMBED Equation.3 з операціями EMBED Equation.3 і EMBED Equation.3 відповідно, через EMBED Equation.3 позначаємо їх прямий добуток–множину пар EMBED Equation.3 , де EMBED Equation.3 , із покомпонентним виконанням операцій. А саме, результатом виконання операцій над елементами EMBED Equation.3 s EMBED Equation.3 множини EMBED Equation.3 вважається елемент EMBED Equation.3 . Нескладно перевірити, що відносно введеної операції прямий добуток груп є групою.
Група називається комутативною або абелевою, якщо групова операцція володіє властивістю комутативності: EMBED Equation.3 для будь-яких елементів EMBED Equation.3 та EMBED Equation.3 .
Якщо кожен елемент групи EMBED Equation.3 є степенем її елемента EMBED Equation.3 , то цей елемент називається твірним і кажуть, що він породжує групу EMBED Equation.3 . Якщо група EMBED Equation.3 має порядок EMBED Equation.3 , то EMBED Equation.3 є її твірним елементом тоді і лише тоді, коли його порядок теж дорівнює EMBED Equation.3 . Група, яка має твірний елемент, називається циклічною. Циклічна група порядку EMBED Equation.3 ізоморфна групі EMBED Equation.3 , а нескінченна циклічна група–групі EMBED Equation.3 .
ТВЕРДЖЕННЯ Б.1. Циклічна група порядку EMBED Equation.3 має рівно EMBED Equation.3 твірних елементів.
ДОВЕДЕННЯ. Його досить провести для EMBED Equation.3 . Покажемо, що EMBED Equation.3 породжує EMBED Equation.3 тоді і лише тоді, коли числа EMBED Equation.3 і EMBED Equation.3 взаємно прості. Справді, якщо НСД EMBED Equation.3 , то маємо EMBED Equation.3 для деяких цілих EMBED Equation.3 і EMBED Equation.3 . Із цієї рівності випливає, що кожен елемент EMBED Equation.3 дорівнює EMBED Equation.3 -кратній сумі EMBED Equation.3 (можна вважати, що EMBED Equation.3 , а інакше коефіціент EMBED Equation.3 слід поміняти на його остачу від ділення на EMBED Equation.3 ).
Навпаки, якщо НСД EMBED Equation.3 і EMBED Equation.3 , то EMBED Equation.3 в EMBED Equation.3 . Отже, порядок EMBED Equation.3 не перевищує EMBED Equation.3 і не може бути твірним.
4. Група перестановок. Іншим прикладом групи є множина EMBED Equation.3 бієктивних відображень множини EMBED Equation.3 на себе з операцією композицій. Нейтральним елементом є тотожне відображення EMBED Equation.3 , а оберненим елементом до EMBED Equation.3 є відображення EMBED Equation.3 , обернене до EMBED Equation.3 . Бієкцію множини на себе називають ще перестановкою цієї множини. Якщо множина EMBED Equation.3 налічує EMBED Equation.3 елементів, то очевидним чином група EMBED Equation.3 ізоморфна групі EMBED Equation.3 . Остання називається симетричною групою степеня EMBED Equation.3 і позначається через EMBED Equation.3 .
Перестановку із звично записують у вигляді таблички
EMBED Equation.3 .
Цикл EMBED Equation.3 де EMBED Equation.3 різні числа від 1 до EMBED Equation.3 ,–це перестановка, яка елемент EMBED Equation.3 відображає в EMBED Equation.3 , а всі інші елементи самі в себе.називається довжиною циклу. Цикли EMBED Equation.3 та EMBED Equation.3 незалежні, якщо множини елементів EMBED Equation.3 та EMBED Equation.3 не перетинаються. Кожна перестановка є композицією (або добутком) попарно незалежних циклів. Наприклад, перестановка
EMBED Equation.3
дорівнює добутку (15)(364). Якщо перестановка EMBED Equation.3 розкладається в добуток EMBED Equation.3 незалежниж циклів з довжинами EMBED Equation.3 , то її знак обчислюється за формолою
EMBED Equation.3
Знак тотожної перестановки приймається рівним 1.
Група EMBED Equation.3 має порядок EMBED Equation.3 . Порядок циклу довжини EMBED Equation.3 як елемента групи EMBED Equation.3 дорівнює EMBED Equation.3 . Порядок перестановки, яка є добутком EMBED Equation.3 незалежних циклів з довжинами EMBED Equation.3 дорівнює НСК цих чисел.
5. Кільця. Кільцем називається множина EMBED Equation.3 з двома заданими на ній операціями,+(додавання) та EMBED Equation.3 (множення), яка має такі властивості:
Відносно додавання EMBED Equation.3 утворює абелеву групу;
Операція множення асоціативна;
Множення дистрибутивне за додаванням, що означає виконання рівностей
EMBED Equation.3
для всіх EMBED Equation.3 .
Якщо крім того операція множення комутативна, то кільце називається комутативним. EMBED Equation.3 називається кільцем з одиницею, якщо в ньому є нейтральний відносно множення елемент. Через 1 позначимо нейтральний елемент для множення, а через 0-для додавання. Прикладом комутативного кільця з одиницею є множина EMBED Equation.3 цілих чисел зі звичайним додаванням та множенням. Прикладом некомутативного кільця з одиницею є кільце матриць, яке розглядається нижче.
Елемент кільця з одиницею називається оборотнім справа [зліва], якщо EMBED Equation.3 для деякого EMBED Equation.3 . Кажуть, що елемент EMBED Equation.3 є правим [лівим] оберненим до EMBED Equation.3 . Елемент EMBED Equation.3 називається оборотнім або дільником одиниці, якщо він оборотній і зліва, і справа. Кожен оборотній елемент має єдиний лівий і правий обернені елементи, які рівні між собою. Цей єдиний елемент називається оберненим до EMBED Equation.3 і позначається через EMBED Equation.3 . Для оборотних елементів EMBED Equation.3 та EMBED Equation.3 неважко перевірити рівність EMBED Equation.3 . Звідси випливає, що множина всіх оборотних елементів кільця з одиницею EMBED Equation.3 утворює групу, яка називається мультиплікативною групою кільця і позначається через EMBED Equation.3 . Наприклад, EMBED Equation.3 . Зрозуміло, що мультиплікативна група комутативного кільця сама є комутативною.
Відображення EMBED Equation.3 називається гомоморфізмом, якщо воно зберігає операції додавання та множення. Для кілець з одиницею повинна виконуватися ще одна умова: EMBED Equation.3 має відображати одиниця кільця EMBED Equation.3 в одиницю кільця EMBED Equation.3 . Ядром гомоморфізму EMBED Equation.3 є множина всіх тих елементів кільця EMBED Equation.3 , які EMBED Equation.3 відображає в нуль кільця EMBED Equation.3 . Прикладом гомоморфізму є відображення із EMBED Equation.3 в EMBED Equation.3 , яке кожному цілому числу ставить у відповідність його остачу від ділення на натуральне EMBED Equation.3 . Ядро утворює цілі числа, кратні EMBED Equation.3 . Як і у випадку груп, гомоморфізм EMBED Equation.3 є ін’єктивним тоді і лише тоді, коли його ядро тривіальне, тобто складається тільки із нуля кільця EMBED Equation.3 . Гомоморфізм, який є бієктивним відображенням, називається ізоморфізмом. Кільця EMBED Equation.3 і EMBED Equation.3 ізоморфні, якщо існує ізоморфізм з EMBED Equation.3 на EMBED Equation.3 .
Для кілець EMBED Equation.3 і EMBED Equation.3 через EMBED Equation.3 позначаємо їх прямий добуток–множину пар EMBED Equation.3 , де EMBED Equation.3 із покомпонентним додаванням та множенням. Неважко впевнитись, що прямий добуток кілець є кільцем. Простим наслідком означень є
ТВЕРДЖЕННЯ Б.2. Мультиплікативні групи EMBED Equation.3 і EMBED Equation.3 ізоморфні.
6. Кільце матриць. У цьому пункті EMBED Equation.3 позначає кільце з одиницею. Матрицею розміру EMBED Equation.3 над EMBED Equation.3 називається індексована сукупність EMBED Equation.3 елементів з EMBED Equation.3 ,де EMBED Equation.3 . Елементи EMBED Equation.3 називають коефіцієнтами матриці і звичайно розміщують у вигляді
EMBED Equation.3
так що матриця розміру EMBED Equation.3 складається із EMBED Equation.3 рядків та EMBED Equation.3 стовпчиків. Матриця розміру EMBED Equation.3 називається вектором-стовпчиком, а розміру EMBED Equation.3 –вектором-рядком.
Сумою матриць EMBED Equation.3 та EMBED Equation.3 однакового розміру є матриця EMBED Equation.3 того ж розміру з коефіцієнтами EMBED Equation.3 . Пишемо EMBED Equation.3 . Добутком матриці EMBED Equation.3 розміру EMBED Equation.3 на матрицю EMBED Equation.3 розміру EMBED Equation.3 є матриця EMBED Equation.3 розміру EMBED Equation.3 з коефіцієнтами EMBED Equation.3 . Пишемо EMBED Equation.3 . Нескладно перевірити, що операція множення матриць є асоціативною. Результатом множення матриці EMBED Equation.3 на елемент EMBED Equation.3 є матриця EMBED Equation.3 з коефіцієнтами EMBED Equation.3 .
Матриця розміру EMBED Equation.3 називається квадратною матрицею порядку EMBED Equation.3 . Коефіцієнти EMBED Equation.3 квадратної матриці EMBED Equation.3 називаються діагональними. Квадратні матриці заданого порядку EMBED Equation.3 відносно операцій додавання та множення утворюють кільце, яке ми позначаємо EMBED Equation.3 . Це кільце з одиницею, в ролі якої виступає одинична матриця EMBED Equation.3 , діагональні коефіцієнти якої рівні одиниці кільця EMBED Equation.3 , а всі інші–нулю.
ТВЕРДЖЕННЯ 3. Кільця EMBED Equation.3 і EMBED Equation.3 ізоморфні.
Це означає, що матриці порядку EMBED Equation.3 можна розбити на блоки розміру EMBED Equation.3 на EMBED Equation.3 , після чого додавати і множити такі матриці поблоково.
EMBED Equation.3 , мультиплікативна група оборотних матриць, має назву повної лінійної групи і позначається також як EMBED Equation.3 .
Далі кільце EMBED Equation.3 вважається комутативним.
Визначник EMBED Equation.3 квадратної матриці EMBED Equation.3 порядку EMBED Equation.3 дорівнює наступному виразу:
EMBED Equation.3 ,
де сумування проводиться за всіма перестановками EMBED Equation.3 з EMBED Equation.3 , а EMBED Equation.3 означає знак перестановки.
ТВЕРДЖЕННЯ 4. Визначник добутку матриць дорівнює добутку їх визначників EMBED Equation.3 .
Якщо взяти в останній рівності в якості EMBED Equation.3 матрицю EMBED Equation.3 , праву обернену до EMBED Equation.3 , то отримаємо EMBED Equation.3 . Подібна рівність справедлива і для оберненої зліва матриці. Отже,
Якщо матриця EMBED Equation.3 оборотна зліва або справа,
то EMBED Equation.3
Алгебраїчним доповненням елемента EMBED Equation.3 матриці EMBED Equation.3 називається значання EMBED Equation.3 , де EMBED Equation.3 –визначник матриці, яка отримується із матриці EMBED Equation.3 після викреслення її EMBED Equation.3 -го рядка та EMBED Equation.3 -го стовпчика. Має місце
ФОРМУЛА ОБЕРНЕНОЇ МАТРИЦІ. Для матриці EMBED Equation.3 з коефіцієнтами EMBED Equation.3 виконується співвідношення EMBED Equation.3 . Отже, в матриці EMBED Equation.3 , оберненій до EMBED Equation.3 , коефіціент з індексами EMBED Equation.3 дорівнює EMBED Equation.3 (порядок індексів помінявся!).
З формули випливає імплікація, що доповнює (1): якщо, то матриця має обернену. Зафіксуємо отриманий зв’язок у наступному твердженні.
ТВЕРДЖЕННЯ 5.
EMBED Equation.3 тоді і лише тоді, коли EMBED Equation.3 .
Якщо матриця EMBED Equation.3 має прваву або ліву обернену, то вона оборотня, тобто має матрицю, що є одночасно і правою і лівою оберненою.
За твердженням 4 відображення EMBED Equation.3 , яке співставляє матриці її визначник є гомоморфізмом мультиплікативних груп. Ядром цього гомоморфізму є підгрупа матриць з визначником 1, яка має назву спеціальної лінійної групи і позначається EMBED Equation.3 .
7. Поля. Полем називається множинм з двома заданими на ній операціями +(додавання) та *(множення), яка має такі властивості:
відносно додавання EMBED Equation.3 утворює абелеву групу з нейтральним елементом 0;
відносно множення EMBED Equation.3 утворює абелеву групу з нейтральним елементом 1;
множення дистрибутивне за додаванням.
ТВЕРДЖЕННЯ 6. Мультиплікативна група EMBED Equation.3 скінченного поля є циклічною.
Для повноти наведено і такий факт.
ТЕОРЕМА Гауса. Група EMBED Equation.3 є циклічною для значенm EMBED Equation.3 де число EMBED Equation.3 непарне просте, а EMBED Equation.3 натуральне і лише для них.
8. Кільце многочленів. Многочлен (або поліном) степеня EMBED Equation.3 від однієї змінної EMBED Equation.3 над комутативним кільцем з одиницею EMBED Equation.3 звичайно зображується у вигляді арифметичного виразу EMBED Equation.3 , де EMBED Equation.3 –коефіцієнти многочлена, причому старший коефіцієнт відмінний від 0. Відносно стандартних операцій додавання та множення многочлени над EMBED Equation.3 утворюють кільце, яке позначається EMBED Equation.3 . Далі у цьому пункті розглядається кільце EMBED Equation.3 многочленів над деяким полем EMBED Equation.3 .
У кільці EMBED Equation.3 стандартним чином вводиться операція ділення з остачею. Завдяки цьому у кільці EMBED Equation.3 цілком аналогічно до кільця EMBED Equation.3 працює алгоритм Евкліда, який дозволяє знаходити найбільший спільний дільник двох многочленів. Теорема про однозначність розкладу на множники в EMBED Equation.3 доводиться аналогічно до теореми Евкліда. Роль простих чисел відіграють незвідні многочлени, тобто многочлени ненульового степеня, які не мають дільників меншого(але ненульового) степеня. Теорема говорить, що кожен многочлен ненульового степеня над полем EMBED Equation.3 розкладається у добуток незвідних многочленів однозначно, якщо не брати до уваги співмножників і не розрізняти співмножники, які можуть бути отриманими одним із одного домноженням на елемент поля.
Нехай EMBED Equation.3 –деякий многочлен над EMBED Equation.3 . Для EMBED Equation.3 через EMBED Equation.3 позначимо елемент поля EMBED Equation.3 , який отримується як результат підстановки елемента EMBED Equation.3 у многочлен замість змінної EMBED Equation.3 і виконання операцій множення і додавання в EMBED Equation.3 . Елемент EMBED Equation.3 будемо називати значенням многочлена EMBED Equation.3 в точці EMBED Equation.3 . Якщо EMBED Equation.3 , то EMBED Equation.3 називається коренем многочлена EMBED Equation.3 . Діленням з остачею многочлена EMBED Equation.3 на многочлен EMBED Equation.3 і підстановкою EMBED Equation.3 в отриману рівність доводиться
ТЕОРЕМА Безу. Якщо EMBED Equation.3 –корінь ненульового многочлена EMBED Equation.3 над полем EMBED Equation.3 , то EMBED Equation.3 ділиться на многочлен EMBED Equation.3 .
Простим наслідком цієї теореми є
ТВЕРДЖЕННЯ 7. Ненульовий многочлен EMBED Equation.3 степеня EMBED Equation.3 над полем EMBED Equation.3 має не більше, ніж EMBED Equation.3 коренів.
Із твердження випливає, що два многочлени степеня не вищого від EMBED Equation.3 кожен, значення яких збігаються в EMBED Equation.3 різних точках мусять бути рівними, оскільки їх різниця є многочленом степеня не більшого від EMBED Equation.3 , який має EMBED Equation.3 корінь. Отже, щонайбільше один многочлен степеня не більшого ніж EMBED Equation.3 може набувати в EMBED Equation.3 заданій точці EMBED Equation.3 задані значення EMBED Equation.3 . Такий многочлен справді існує і дається такою формулою
ІНТЕРПОЛЯЦІЙНА ФОРМУЛА ЛАГРАНЖА.
EMBED Equation.3 .
9. Векторні простори. Лінійним(або векторним) простором над полем EMBED Equation.3 називається абелева група EMBED Equation.3 із груповою операцією + та операцією множення елемента групи(вектора) на елемент поля(скаляр), та результатом виконання якої є вектор. Операції мають задовольняти такі умови.
множення унітарне: EMBED Equation.3 , де 1–одиниця поля, а EMBED Equation.3 –довільний вектор з EMBED Equation.3 ;
множення асоціативне: EMBED Equation.3 для всіх EMBED Equation.3 і EMBED Equation.3 ;
множення і додавання повязані законами дистрибутивності
EMBED Equation.3
для всіх EMBED Equation.3 і EMBED Equation.3 .
Наприклад, множина EMBED Equation.3 для довільного натурального EMBED Equation.3 із покомпонентним додаванням та покомпонентним множенням на елемент поля EMBED Equation.3 є лінійним простором над EMBED Equation.3 .
Для векторів EMBED Equation.3 вектор EMBED Equation.3 називається їхньою лінійною комбинацією з коефіцієнтами EMBED Equation.3 . Всеможливі лінійні комбінації векторів EMBED Equation.3 утворюють їхню лінійну оболонку. Вектори EMBED Equation.3 є повною системою, якщо їх лінійна оболонка охоплює весь простір EMBED Equation.3 . Вектори EMBED Equation.3 називаються лінійно незалежними, якщо жоден з них не належить лінійній оболонці решти. Базою простору EMBED Equation.3 називається така система векторів EMBED Equation.3 , що кожен вектор з EMBED Equation.3 можна подати як лінійну комбінацію векторів цієї системи, причому однозначним чином. Зрозуміло, що база повинна бути лінійно незалежною і повною системою. Окрім того справедливе
ТВЕРДЖЕННЯ 8. Для системи векторів EMBED Equation.3 наступні три умови еквівалентні:
EMBED Equation.3 є базою;
EMBED Equation.3 є мінімально повною системою(іншими словами, якщо вилучити із EMBED Equation.3 будь-який вектор, система перестане бути повною);
EMBED Equation.3 є максимальною лінійною незалежною системою(іншими словами, якщо додати до EMBED Equation.3 будь-який вектор, система перестане бути лінійно незалежною).
Із твердження видно, що кожен скінченний лінійний простір EMBED Equation.3 має деяку базу EMBED Equation.3 . Припустимо, що поле EMBED Equation.3 також скінченне. З означення бази випливає, що EMBED Equation.3 складається із EMBED Equation.3 векторів, де EMBED Equation.3 –кількіість елементів поля EMBED Equation.3 . Отже, будь-які дві бази мусять мати однакову кількість векторів(цей факт має місце і для нескінченних полів, якщо лише лінійний простір має скінченну базу). Кількість векторів у базі називається вимірністю лінійного простору.
Будь-яка підмножина простору EMBED Equation.3 , замкнена відносно операцій, сама є лінійним простором над тим же полем і називається лінійним підпростором простору EMBED Equation.3 . Очевидно, лінійна оболонка системи із EMBED Equation.3 лінійно незалежних векторів є EMBED Equation.3 -вимірним підпростором.
Матриця з EMBED Equation.3 називається невиродженою, якщо її стовпчики є лінійно незалежними векторами лінійного простору EMBED Equation.3 .
Твердження 9. Квадратна матриця над полем невироджена тоді і тільки тоді, коли вона оборотна.
Пункт 1. Ділення з остачею.
Цілі числа — {..., –3, –2, –1, 0, 1, 2 , 3,...}. У цій книжці буде вживатися досить стандартне позначення цієї множини — літера Z. Відомо, що щодо звичайних операцій додавання і множення, множина цілих чисел є кільцем, або Z є моногенним асоціативно-комутативним кільцем з одиницею. Підмножина {1, 2, 3, 4,...} множини цілих чисел називається множиною натуральних чисел і стандартно позначається буквою N.
Визначення. Нехай a , b Z. Число а ділиться на число b якщо знайдеться таке число q Z , що а = qb . Синоніми: а кратне b ; b — дільник а . Запис: а(3 вертикальні крапки AL) INCLUDEPICTURE \d \z "../pict/1-001.gif"b чи b | a .
Легко помітити, що відношення подільності b | a є бінарним відношенням на множині Z, а якщо обмежитися розглядом тільки натуральних чисел, те нескладно установити, що на множині N це бінарне відношення є рефлексивним, антисиметричним і транзитивним, тобто відношенням часткового порядку. Легко перевіряється також наступна властивість:
Нехай а 1 + а 2 +...+ а n = c 1 + c 2 +...+ c k – рівність сум цілих чисел. Якщо всі доданки в цій рівності, крім одного, кратні b , то і доданок, що залишився, має бути кратним b .
Перераховані властивості відношення подільності дозволять нам довести основну теорему першого пункту:
Теорема . Для даного цілого відмінного від нуля числа b, усяке ціле число а єдиним чином представляється у виді а = bq + r , де 0 r < | b |.
Доказ. Зрозуміло, що одне представлення числа а рівністю а = bq + r ми одержимо, якщо візьмемо bq рівним найбільшому кратному числа b , що не перевищує а (див. рис. 1)
( a = 3b+r )
Рис. 1
Тоді, очевидно, 0 r < | b |. Доведемо одиничність такого представлення. Нехай а = bq + r і а = bq 1 + r 1 — два таких представлення. Значить 0 = а – а = b ( q – q 1 ) + ( r – r 1 ). Тут 0 ділиться на b; b ( q – q1 ) ділиться на b, отже ( r – r1 ) мусить ділитися на b . Оскільки 0r<b і 0r1<b , то r – r1 < b і r – r1 ділиться на b, значить r – r1 дорівнює нулю, а, значить і q — q1 дорівнює нулю, тобто два таких представлення збігаються.
Відразу після доказу теореми, поки не забулися позначення, що використовувалися в ньому, дамо
Визначення. Число q називається неповною часткою, а число r — залишком від ділення а на b.
Ідея малюнка 1, що пояснює доказ теореми, належить древнім грекам. Саме древні греки, чомусь, дуже любили багаторазово укладати один відрізок в інший, а частину більшого відрізка, що залишилася, природно, називали “залишком”.
Помітимо, що залишок — завжди є число невід’ємне, а от неповна частка може бути яким завгодно цілим числом. Тому на питання: “Скільки буде мінус п'ять поділити на три з залишком?”, кожний повинен відповідати: “Мінус два, у залишку — один!”.
Пункт 2. Найбільший спільний дільник.
Почнемо з визначення.
Визначення. Число d Z, що ділиться одночасно на числа а, b, c, ... , k Z, називається спільним дільником цих чисел. Найбільше d з такою властивістю називається найбільшим спільним дільником. Позначення: d = (a, b, c, ..., k).
Перелічимо, подекуди доводячи, основні властивості найбільшого спільного дільника.
Теорема (Властивість 1) . Якщо (a, b) = d, то знайдуться такі цілі числа u і v, що d=au+bv.
Доказ . Розглянемо множину P = { au + bv u,v Z }. Очевидно, що P Z , причому P – ідеал у Z. Очевидно, що a, b, 0 P. Нехай x, y P і y 0. Тоді залишок ділення x на y належить P. Дійсно:
x = yq + r, 0 r < y,
r = x – yq = (au1 + bv1) – (au2+bv2) q=a ( u1 – u2 q)+ b (v1–v2q) P.
Нехай d P - найменше додатне число з P (задумайтеся, чому таке існує!). Тоді а ділиться на d. Справді, a=dq+r1, 0 r1< d, a P, d P, значить r1P, отже r1=0. Аналогічно одержуємо, що b ділиться на d, отже d - спільний дільник a і b.
Оскільки d P, то d = au0+ bv0. Якщо тепер d1 - спільний дільник a і b, то d1 | (au0+bv0), тобто d1| d. Значить d d1 і d - найбільший спільний дільник.
Властивість 2 . Для будь-яких цілих чисел а і k справедливо: ( а , kа ) = а ; (1, а ) = 1.
Властивість 3 . Якщо a = bq + c , то сукупність спільних дільників a і b збігається із сукупністю спільних дільників b і c , зокрема,
( a , b ) = ( b , c ).
Доказ. Нехай d | a , d | b , тоді d | c . Нехай d | c , d | b , тоді d | a .
Проілюструємо цей доказ на давньогрецький лад. Подивіться на рис. 2:
Рис. 2
Якщо d ціле число разів укладається в а і в b , то, очевидно, що d мусить ціле число разів укластися й у с.
Властивість 4 . Нехай a , b і m - довільні цілі числа. Тоді
( am , bm ) = m ( a , b ).
Доказ. Якщо d - найбільший спільний дільник чисел а і b , то dm | am і dm | bm , тобто dm - дільник am і bm . Покажемо, що dm - найбільший спільний дільник цих чисел. Оскільки d - найбільший спільний дільник чисел а і b , то, відповідно до властивості 1, для деяких цілих чисел u і v виконується рівність d = au + bv. Помноживши цю рівність на m, одержимо:
dm = amu + bmv .
Видно, що якщо деяке число s ділиться одночасно на am і bm , то s має ділитися і на dm , тобто s dm , отже, dm - найбільший спільний дільник.
Властивість 5 . Нехай s - дільник а і b . Тоді:
(a/s,b/s)=(a,b)/s
Доказ .
(a,b)=(a/s*s,b/s*s)=s(a/s,b/s)
Властивість 6 . Очевидно тепер, що
(a/(a,b),b/(a,b))=1
Властивість 7 . Якщо ( a , b ) = 1, то ( ac , b ) = ( c , b ).
Доказ . Нехай ( c, b ) = d . Маємо: d | b , d | c , отже d | ac , тобто d - дільник ас і b . Нехай тепер ( ac , b ) = s . Маємо: s | b , s | ac , s - дільник b , тобто або s = 1, або s не ділиться на а . Це означає, що s | c , значить s | d . Отже, d і s поділяються один на одного, тобто d = s.
Пункт 3. Взаємно прості числа.
Визначення. Цілі числа a і b називаються взаємно простими, якщо ( a , b ) = 1.
Згадуючи властивість 1 з попереднього пункту, легко помітити, що два числа a і b є взаємно простими тоді і тільки тоді, коли знайдуться цілі числа u і v такі, що au + bv = 1.
Здавалося б, що особливого можна сказати про взаємно прості числа? Ну немає в них спільних дільників, відмінних від 1 і -1, і все. Однак, задамося питанням: "Як часто зустрічаються пари взаємно простих чисел?", і постараємося відповісти на нього у термінах теорії імовірностей.
Нехай X = { x n | n = 1, 2,...} - довільна строго зростаюча послідовність натуральних чисел (або X - довільна підмножина натуральних чисел, упорядкована звичайним чином). Позначимо через ( N ; X ) число членів послідовності X , що не перевищують N.
Визначення. Число
EMBED Equation.3
називається (верхньою асимптотичною) густиною послідовності X = { x n | n = 1, 2,...} у множині N.
Приклад 1. Нехай xn = 2 n , де n належить N, - послідовність усіх парних чисел. Очевидно, що
EMBED Equation.3
Між іншим, це добре узгоджується з нашими інтуїтивними представленнями про те, що парних чисел - половина.
Приклад 2. Нехай xn=2n, де n належить N, - геометрична прогресія. Інтуїтивно ясно, що таких чисел у натуральному ряді мало, тому що чим далі в натуральному ряді, тим рідше зустрічається ступінь двійки. Поняття густини підтверджує це відчуття: (2k ; { xn }) = k , і, легко перевірити, що
EMBED Equation.3
Резонно вважати, що густина - це імовірність навмання витягти з натурального ряду число, що належить заданій послідовності. (Погодьтеся, що ви завжди так і думали. Імовірність дістати парне число є 1/2, а імовірність напоротися на ступінь двійки, особливо серед великих чисел, узагалі говорячи, мізерно мала).
Аналогічно визначенню густини послідовності, можна дати визначення густини множини пар натуральних чисел. Нехай мається довільна множина Х упорядкованих пар натуральних чисел. Позначимо через ( N ; X ) число пар з множини Х , кожна компонента яких не перевищує N. Корисно уявити собі пари чисел з множини Х як координати точок на координатній площині, тоді ( N ; X ) є числом точок множини Х, що потрапили в квадрат {( x , y ) | 0 < x N ; 0 < y N }.
Визначення. Число
EMBED Equation.3
називається (верхньою асимптотичною) густиною множини пар Х в множині N2.
Приклад 3. Нехай Х - множина усіх пар натуральних чисел, у яких перший компонент строго більший за другий. Множині Х відповідають точки першої чверті координатної площини, що лежать під бісектрисою y = x . Густина такої множини становить:
EMBED Equation.3
що, узгоджується з нашим інтуїтивним представленням про те, що упорядкованих пар, у яких перший компонент перевершує другу приблизно половина від загальної кількості всіх пар натуральних чисел.
Нехай X - множина всіх упорядкованих пар ( u , v ) натуральних чисел таких, що ( u, v ) = 1, тобто множина усіх пар взаємно простих чисел. Відповідь на питання про частоту появи пари взаємно простих чисел дає теорема, відкрита в 1881 році італійцем Э.Чезаро.
Теорема (Чезаро). Імовірність вибрати з N пар взаємно простих чисел дорівнює 6/ 2 , точніше
EMBED Equation.3
Таким чином, густина взаємно простих чисел у множині N2 виявляється існує і дорівнює 6/ 2 0, 607... Приблизно в 60% випадків ви витягнете з натурального ряду пари взаємно простих. І ще дивно - у теоремі Чезаро виникло число , загадкове і всюдисуще!
Доказ. Строгий доказ теореми Чезаро досить складний і громіздкий. Наведемо замість строгого доказу деякі евристичні міркування, що мають переконують в тому, що ця теорема є правдоподібною.
Забудемо, що існування імовірності (верхньої межі) потрібно копітко доводити. Припустимо відразу, що існує імовірність p того, що випадково обрані натуральні числа а і b взаємно прості.
Нехай d N . Через P { S } позначимо імовірність події S . Міркуємо: Р {( a , b ) = d } = P{d | a}} P{d | b} PEMBED Equation.3
Просумувавши ці імовірності по всіх можливих значеннях d , ми повинні одержати одиницю:
EMBED Equation.3 а сума ряду EMBED Equation.3
відома і дорівнює 2/6 (див., напр., збірник задач Демидовича з матаналізу, розділ "Ряди Фур'є"). Отже,
1=EMBED Equation.3
отже, p = 6/ 2 .
Пункт 4. Алгоритм Евкліда.
Слово "алгоритм" є російською транскрипцією латинізованого імені видатного арабського математика ал-Хорезми Абу Абдули Мухаммеда ібн ал-Маджусі (787 - 850) і означає в сучасному смислі деякі правила, список інструкцій чи команд, виконуючи які, хтось досягне необхідного результату. Алгоритм, що дозволяє за заданими натуральними числами a і b знаходити їхній найбільший спільний дільник, вважається придумав самий впливовий математик усіх часів і народів - Евклід, він викладений у IX книзі його знаменитих "Початків".
Відступ "Панегірик Евкліду"
Про життя Евкліда ми не маємо ніяких достовірних зведень, можливо, що він не був реальною історичною особистістю, а був колективним псевдонімом деякої групи Олександрійських математиків, типу Ніколя Бурбаки. Якщо він жив, то він жив за часів Птолемея Першого (306 - 283), якому, відповідно до переказу, він сказав "До геометрії немає царської дороги". Але Птолемеї свідомо культивували науку і культуру в Олександрії, тому не звертали уваги на такі слова своїх учених.
Найбільш знаменитий твір Евкліда - тринадцять книг його "Начал", але є ще й інші дрібні опуси. Ми не знаємо, яка частина цих праць належить самому Евкліду і які частини складають компіляції, але в цих працях виявляється разюча проникливість і далекоглядність. Це перші математичні праці, що дійшли до нас від древніх греків цілком. В історії Західного світу "Начала", після Біблії, - книга, що найбільше число раз видана і найбільш вивчена. Велика частина нашої шкільної геометрії запозичена буквально з перших шести книг "Начал", традиція Евкліда дотепер тяжіє над нашим елементарним навчанням. Для професійного математика ці книги усе ще мають непереборне зачарування, а їх логічна дедуктивна побудова вплинула на сам спосіб наукового мислення більше, ніж інший здобуток.
Панегірик кінчений.
Нехай дані два числа a і b ; a 0, b 0, вважаємо, що a > b . Символом := у записі алгоритму позначаємо присвоювання. Алгоритм:
1. Ввести a і b .
2. Якщо b = 0 , то Відповідь: а . Кінець .
3. Замінити r := "залишок від ділення а на b ", а := b , b := r .
4. Йти на 2.
рис.3.
Як і чому виконання цього коротенького набору інструкцій приводить до знаходження найбільшого спільного дільника ми з'ясуємо трохи пізніше, зараз же хочеться сказати кілька слів про сам алгоритм. Покрокове виконання алгоритму Евкліда переконують у його простоті без строкатості. Проілюструємо роботу алгоритму на грецький лад мал. 3:
У сучасному буквеному записі, що кочує з одного підручника в іншій, алгоритм Евкліда виглядає так: a > b; a, b Z .
Маємо: b > r 1 > r 2 >... > r n > 0, отже процес обірветься максимум через b кроків. Дуже цікавий і практично важливе питання в тому, коли алгоритм Евкліда працює особливо довго, а коли швидко, ми розглянемо трохи пізніше. Покажемо зараз, що r n = ( a , b ). Переглянемо послідовно рівності зверху вниз: усякий дільник а і b ділиться на r1 , r2 ,..., rn . Якщо ж переглядати цей ланцюжок рівностей від останнього до першого, то видно, що rn | rn -1 , rn | rn -2 , і т.д., тобто rn ділиться на а і b . Тому rn - найбільший спільний дільник чисел а і b .
З його розгляду алгоритму Евкліда зрозуміло, що сукупність дільників а і b збігається із сукупністю дільників ( a , b ). Ще він дає практичний спосіб одержання чисел u і v з Z (чи, якщо завгодно, з теореми пункту 2) таких, що r n = au + bv = ( a, b ).
Дійсно, з ланцюжка рівностей маємо:
r n = r n -2 - r n -1 q n = r n -2 - ( r n -3 - r n -2 q n -1 ) q n = ...
(йдемо по ланцюжку рівностей знизу нагору, виражаючи з кожної наступної рівності залишок і підставляючи його у вираз, що одержаний вже до цього моменту)
... = au + bv = ( a , b ).
Приклад. Нехай а = 525, b = 231. Віддамо ці числа на розтерзання алгоритму Евкліда: (нижче приводиться запис ділення куточком, і кожен раз те, що було в куточку, а саме дільник, дописується до залишку ділення з лівої сторони, а залишок, як новий дільник, береться в куточок)
Запис того самого у вигляді ланцюжка рівностей:
525 = 231 · 2 + 63 231 = 63 · 3 + 42 63 = 42 · 1 + 21 42 = 21 · 2
Таким чином, (525, 231) = 21. Лінійне представлення найбільшого спільного дільника:
21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 = 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) = 525 · 4 - 231 · 9,
і наші горезвісні u і v з Z рівні, відповідно, 4 і - 9.
Пункт 5. Лінійні діофантові рівняння з двома невідомими.
Звичайно, довільне рівняння (але, як правило, усе-таки з цілими коефіцієнтами) одержує титул "діофантове", якщо хочуть підкреслити, що його потрібно вирішити в цілих числах, тобто знайти всь...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора