1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n J
Изтегляне 5.91 Mb.
|
Твърдение: Ако A е ортогонална матрица, то A-1 също е ортогонална матрица. Доказателство: Имаме A-1.(A-1)t = At.(A-1)t = (A-1.A)t = Et = E A-1 е ортогонална матрица.
Доказателство: Имаме (A.B).(A.B)t = A.B.Bt.At = A.E.At = A.At = E A.B е ортогонална матрица.
Доказателство: Нека A = (ij) nxn. А.At = E i1.j1 + i2.j2 + … + in.jn = ij за всеки i, j { 1, 2, …, n }. Ако a1 = (11, 12, …, 1n), a2 = (21, 22, …, 2n), …, an = (n1, n2, …, nn) са векторите-редове на матрицата A, тези равенства показват, че (ai, aj) = ij за всеки i, j { 1, 2, …, n }, т.е. системата вектори a1, a2, …, an е ортонормирана. Аналогично като използваме, че A.At = E At.(At)t = E, получаваме, че векторите-стълбове на A са ортонормирана система вектори. Твърдение: Ако А е ортогонална матрица, то detA = 1. Доказателство: A.At = E detA.detAt = detE (detA)2 = 1 detA = 1.
Нека E = (e1, e2, …, en) е един базис на V и F = (f1, f2, …, fn) е друг базис на V. Нека T = (ij) nxn e матрицата на прехода от E към F, т.е. fi = 1i.e1 + 2i.e2 + … + ni.en = Разглеждаме (fi, fj) = i, j { 1, 2, …, n}. Нека базисът Е е ортонормиран (ek, em) = km за всеки k, m { 1, 2, …, n}. Тогава (fi, fj) =
i, j { 1, 2, …, n}  Tt.T = E T е ортогонална матрица. И така матрицата на прехода между два ортонормирани базиса е ортогонална.
за i, j { 1, 2, …, n } (fi, fj) = ij F е система от n на брой ненулеви ортогонални вектори с дължина 1 F е ортонормиран базис. И така всяка ортогонална матрица е матрица на прехода от един ортонормиран базис към друг ортонормиран базис. Нека V е крайномерно евклидово пространство и Hom (V). Казваме, че е симетричен линеен оператор, ако за всеки два вектора x, y V имаме ( (x), y) = (x, (y)). Ясно е, че ако e1, e2, …, en е базис на V достатъчно е ( (ei), ej) = (ei, (ej)) за всеки i, j { 1, 2, …, n} поради линейността на и линейността на скаларното произведение по двата си аргумента.
dimV = n . Нека e1, e2, …, en е ортонормиран базис на V. Нека Hom (V) и има матрица A спрямо този базис. Тогава е симетричен линеен оператор А е симетрична матрица. Доказателство: Нека A = (ij) nxn. Тогава (ei) = 1i.e1 + 2i.e2 + … + ni.en. Операторът е симетричен ( (ei), ej) = (ei, (ej)) за всеки i, j { 1, 2, …, n} A е симетрична матрица. Твърдение: Ако А е реална симетрична матрица (A nxn, At = A), то всички характеристични корени на A са реални числа. Доказателство: Нека характеристичните корени на А са 1, 2, …, n, i , и нека е кой да е от тях. Нека A = (ij), ij и ij = ji за всяко i, j { 1, 2, …, n }. Разглеждаме системата: (11 - ).x1 + 12.x2 + … + 1n.xn = 0 21.x1 + (22 - ).x2 + … + 2n.xn = 0 (*) …
n1.x1 + n2.x2 + … + (nn - ).xn = 0 Детерминантата на (*) e fA () = 0 (*) има ненулево решение (1, 2, …, n) (0, 0, …, 0), i за всяко i = 1, 2, …, n, тъй като коефициентите на (*) са комплексни. За всяко i = 1, 2, …, n имаме: i1.1 + i2.2 + … + (ii - ).i + … + in.n = 0 i1.1 + i2.2 + …+ in.n = .i. Умножаваме двете страни по  = . . Последното равенство сумираме по
i = 1, 2, …, n и получаваме: Нека v = i, j { 1, 2, …, n}, а в предпоследното равенство разменихме индексите, което е позволено, тъй като те се менят в еднакви множества. Получихме, че dimV = n и е симетричен линеен оператор на V. Тогава всичките n характеристични корени на са реални числа, т.е. има n (не непременно различни) собствени стойности. Доказателство: Нека e1, e2, …, en е ортонормиран базис на V и А е матрицата на спрямо този базис. Съгласно по-предното твърдение А е симетрична матрица. Oт предното твърдение всичките характеристични корени 1, 2, …, n на A са реални всичките са собствени стойности на оператора . Твърдение: Нека V е крайномерно евклидово пространство, dimV = n и е симетричен линеен оператор на V. Ако x, y са собствени вектори, отговарящи на различни собствени стойности , на , то x и y са ортогонални. Доказателство: Имаме (x) = .x, (y) = .y. e симетричен оператор ( (x), y) = (x, (y)) (.x, y) = (x, .y) .(x, y) = .(x, y) ( – ). (x, y) = 0 и тъй като (x, y) = 0, т.е. x и y са ортогонални вектори. Теорема: Нека V е крайномерно (ненулево) евклидово пространство и е симетричен линеен оператор на V. Тогава съществува ортонормиран базис f1, f2, …, fn на V в който матрицата на е диагонална, т.е. от вида  .
Доказателство: Нека n = dimV, n , n 1. Провеждаме индукция по n. База: При n = 1 в кой да е базис матрицата на e ()1x1, т.е. тя е диагонална. Стъпка: Нека твърдението е вярно за n-1 (n 2). Нека 1 е собствена стойност на и е1 е собствен вектор, отговарящ на тази собствена стойност. Нека f1 = (f1) = ( Нека U = ℓ (f1). Тогава U V и dimU = 1. Разглеждаме ортогоналното допълнение U. Имаме U V и V = U U dimU + dimU = dimV dimU = n – 1. Ще покажем, че U е -инвариантно подпространство на V. Действително, за всяко x U имаме ( e симетричен) ( (x), f1) = (x, (f1)) = (x, 1.f1) = 1.(x, f1) = 0 (x) U. Разглеждаме като линеен оператор на евклидовото пространство U (разглеждаме ограничението на върху U). Очевидно e симетричен оператор в U. По индукционното предположение твърдението е вярно за оператора : U U, т.е. съществува ортонормиран базис f2, f3, …, fn на U, в който операторът има матрица Разглеждаме векторите f1, f2, …, fn. Имаме f2, …, fn U f2, …, fn са ортогонални на f1 f1, f2, …, fn са ортонормирана система от n вектора с дължина 1 те образуват ортонормиран базис на V. За всяко i = 1, 2, …, n имаме (fi) = i.fi матрицата на в този базис е точно Следствие: За всяка симетрична матрица A nxn съществува ортогонална матрица T nxn, такава че T-1.A.T = , където 1, …, n са точно характеристичните корени на A.
Доказателство: Нека V е крайномерно евклидово пространство с размерност n (например V = n). Нека E = (e1, e2, …, en) е ортонормиран базис на V. Тогава съществува единствен линеен оператор Hom (V), такъв че в базиса E матрицата на e A. Тъй като A е симетрична матрица и базисът E е ортонормиран, e симетричен линеен оператор на V. От теоремата съществува ортонормиран базис F = (f1, f2, …, fn) на V, спрямо който матрицата на e D = E към базиса F. Тогава от по-горе Т е ортогонална матрица и от формулата за смяна на базиса имаме, че D = T-1.A.T. Тъй като матриците A и D са подобни, те имат едни и същи характеристични корени, т.е. характеристичните корени 1, …, n на D са точно характеристичните корени на A.
1, 2, …, n L, такива че f (x) = a0.(x - 1).(x - 2). ….(x - n). В означенията на следствието, нека M е сечението на всички подполета на полето L, които съдържат F и 1, 2, …, n L. Ясно е, че M е подполе на L и M е най-малкото такова подполе, което съдържа F и 1, 2, …, n. M се нарича поле на разлагане на f над полето F. Може да се покаже, че всеки две полета на разлагане на полином над едно и също поле са изоморфни, т.е. неформално, полето на разлагане е независимо от разширението, което съдържа корените на полинома. Нека f F[x], f (x) = a0.xn + a1.xn-1 + … + an-1.x + an, n , a0 F*. В подходящо разширение L F имаме: f (x) = a0.(x - 1).(x - 2). ….(x - n). Като приравним коефициентите пред xn-1, xn-2, …, x1, x0 в равенството получаваме формулите на Виет: 1 + … + n = 1.2 + … + n-1.n = … 1.2. ….k + … + n-k+1.n-k+2. ….n = (-1)k. … 1.2. ….n = (-1)n. Тук лявата страна на k-тата формула (1 k n) съдържа сумата от всевъзможните произведения на k елемента от 1, 2, …, n, т.е. съдържа Нека A е комутативен пръстен с единица. Нека f = f (x1, x2, …, xn) A[x1, …, xn]. Казваме, че f е симетричен полином, ако 1, 2, …, n. Следните симетрични полиноми 1 = x1 + x2 + … + xn 2 = x1.x2 + x1.x3 + … + xn-1.xn … n = x1.x2. ….xn се наричат елементарни симетрични полиноми. Теорема: Нека А е област, f = f (x1, x2, …, xn) A[x1, x2, …, xn] е симетричен полином. Тогава съществува единствен полином g на n променливи с коефициенти от А, такъв че g (1, 2, …, n) = f (x1, x2, …, xn).
1, 2, …, n са корените на f (x), i K F. Aко h (x1, x2, …, xn) е симетричен полином с коефициенти от полето F, то h (1, 2, …, n) F. Доказателство: Нека f (x) = a0.xn + a1.xn-1 + … + an, ai F, а0 F*. От теоремата съществува полином g на n променливи с коефициенти от полето F, такъв че h (x1, x2, …, xn) = g (1, 2, …, n). За k = 1, 2, …, n имаме: k (1, 2, …, n) = (-1)k. h (1, 2, …, n) = g ( Казваме, че едно поле F е алгебрически затворено, ако всеки полином f F[x], deg f 1 има поне един корен в F. Eквивалентна дефиниция е: За всеки полином f F[x], deg f (x) = n 1, съществуват 1, 2, …, n F, такива че f (x) = a0.(x - 1).(x - 2). ….(x - n), където a0 F* е старшият коефициент на f. Действително, ако 1 F е корен на f (x), то f (x) = (x - 1).g (x), g (x) F[x]. По същия начин, ако 2 F е корен на g (x), то g (x) = (x - 2).h (x), h (x) F[x] и f (x) = (x - 1).(x - 2).h (x) …и т.н. след точно n стъпки f ще се разложи в линейни множители. Теорема: Полето е алгебрически затворено. Доказателство: Ще отбележим, че няма чисто алгебрично доказателство на тази теорема, т.е. което не използва поне малка част от анализа – например всеки полином f (x) [x] e непрекъсната функция от в . Стъпка 1: Ако f (x) [x], deg f е нечетно число, f (x) има поне един реален корен. Действително, нека n = deg f , n 1, a0 0 е старшият коефициент на f. Използваме, че n е нечетно число: Ако a0 > 0, то Ако a0 < 0, то И в двата случая съществуват a, b , a < b, такива че f (a).f (b) < 0. Тогава от теоремата на Болцано-Коши, тъй като f (x) е непрекъсната функция, съществува c [a, b], такова че f (c) = 0. Стъпка 2: Ако f (x) [x] и deg f 1, то f (x) има поне един корен в . Нека n = deg f, n 1, n = 2k.m, k 0, m 1, m е нечетно. Провеждаме индукция по k. База: k = 0. Тогава n = m е нечетно и от стъпка 1 f има дори реален корен. Стъпка: Нека твърдението е изпълнено за k – 1, k 1. Нека 1, 2, …, n са корените на f (x), i K – поле на разлагане на f (x) над . Нека r . Означаваме ij = i.j + r.(i + j) за всеки i, j, 1 i < j n. Естествено, ij K. Броят на ij е n1 = g (x) = bt = (-1)t.t (…, ij, …). При произволна пермутация 1, 2, …, n имаме, че ij = i.j + r.(i + j) преминава в
g (x) [x], deg g = 2k-1.m, където m е нечетно. По индукционното предположение полиномът g (x) има комплексен корен. Тъй като K, това означава, че за всяко r съществуват индекси i, j, 1 i < j n, такива че ij = i.j + r.(i + j) . Но двойките i, j, 1 i < j n са краен брой, реалните числа са безброй много съществуват реални числа r1, r2, r1 r2, такива че i.j + r1.(i + j) = c , i.j + r2.(i + j) = d за една и съща двойка i, j, 1 i < j n. В такъв случай, i + j = Така i, j са корените на полинома x2 – a.x + b = 0, т.е. i, j = И така i, j , т.е. f наистина има комплексен корен. Стъпка 3: Ако f (x) [x], deg f 1, то f (x) има поне един корен в . Нека f (x) = a0.xn + a1.xn-1 + … + an, ai , a0 *, n 1. Нека За всяко имаме: = Разглеждаме h (x) = f (x). h (x) = c0.x2.n + c1.x2.n-1 + … + c2.n-1.x + c2.n, ct . За всяко t = 0, 1, 2, …, 2.n, ct = f () = 0 е корен на f или f ( 1, 2, …, n , такива че f (x) = a0.(x - 1).(x - 2). ….(x - n), където a0 * е старшият коефициент на f. Така неразложими над полиноми с коефициенти от са само полиномите от степен 1. Каталог: fmi fmi -> Софтуерни технологии fmi -> Лекции и семинарни занятия по аналитична геометрия fmi -> 3d-алгоритъм на Chaikin fmi -> Лекции по увод в програмирането fmi -> Лекции и семинарни занятия по линейна алгебра fmi -> Конкурентно Програмиране fmi -> Лекции по компютърни мрежи и комуникации fmi -> Ще предпочетеш да наблюдаваш света отстрани или ще се присъединиш към най-голяма студентска организация? fmi -> Лекции по обектно-ориентирано програмиране Изтегляне 5.91 Mb. Сподели с приятели:
|
.
,
за i, j { 1, 2, …, n }.
ji = ij за всеки i, j { 1, 2, …, n }
и получаваме: i1.1.
= .
.
= 
= v. Използвали сме ij , ij = ji за всеки
.
.e1. Тогава
.
,
,
,
.
събираеми.
= f (x1, x2, …, xn) (равенство на полиноми) за произволна пермутация i1, i2, …, in на числата
, …, (-1)n.
, 
.
, 
.
= 2k-1.m, където m и m е нечетно. Разглеждаме полиномът 
, g (x) K[x]. Нека g (x) = 
, засега е ясно, че bt K. За всяко t = 1, 2, …, n1 имаме:
на
.
+ r.(
. С други думи, произволна пермутация на 1, 2, …, n води до пермутация на ij. Но t (…, ij, …) е симетричен полином на ij, така че той не се променя при пермутация на ij. И така bt = (-1)t.t (…, ij, …) е симетричен полином с реални коефициенти на 1, 2, …, n и от следствието по-горе bt за всяко t = 1, 2, …, n1. Така имаме:
= a , i.j = 
= b .
, тъй като е затворено относно коренуване (което се вижда лесно с формулата на Моавър).
(x) = 
.xn + 
.xn-1 + … + 
.x + 
[x].
) = 
. Действително,
= 
. Имаме
= 
= ct (в предпоследното равенство сменихме ролите на индексите, което е позволено, тъй като те участват симетрично). Получихме, че 
) = 0 
= 0