Фробениусовы эндоморфизмы множества проекторов

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

фйстД
[7], техническая реализация которого может быть произвольна (веб-сервисы, очереди сообщений и прочее).
В итоге, используя подобный подход, получаем инструментарий для создания оберток, использующий распространенный объектный язык с поддержкой HTML, обертки которого легко встраиваются в инфраструктуру приложений.
Библиографический список
1. Kushmerick, N. Wrapper Induction for Information Extraction // University of Washington, Tech., Department of Computer Science & amp- Engineering — Washington, USA, 1997.
2. Kuhlins, S., Tredwell, R. Toolkits for Generating Wrappers // University of Mannheim, Department
of Information Systems III D-68 131 — Mannheim, Germany, 2009.
3. Sahuguet, A., Azavant, F. Web Ecology — Recycling HTML pages as XML documents using W4 °F, // ACM International Workshop on the Web and Databases (WebDB'99) — Philadelphia, Pennsylvania, USA, 1999.
4. Liu, B. Web. Data. Mining // Department of Computer Science, University of Illinois at Chicago — Chicago, USA, 2007.
5. Chang, C., Mohammed Kayed, M., Ramzy Girgis, M., Shaalan, K. A Survey of Web Information Extraction Systems // IEEE Transactions on Knowledge and Data Engineering (TKDE), TKDE-0475−1104. R3 — Washington, USA, 1997.
6. Gamma, E., Helem R., Johnson R., Vlissides J. Design Patterns: Elements of Reusable Object-Oriented Software // Addison-Wesley Longman Publishing Co., Inc. — Boston, USA, 2007 — ISBN 0−201−63 361−2.
ФРОБЕНИУСОВЫ ЭНДОМОРФИЗМЫ МНОЖЕСТВА ПРОЕКТОРОВ
А.М. ВЕТОШКИН, доц. каф. ПМ и МММГУЛ, канд. техн. наук
Обозначим Mmn — множество прямоугольных матриц размера m * n, с элементами из поля R или C- Mn — множество квадратных матриц порядка n.
Пусть P — квадратная матрица с комплексными элементами. Она называется проектором, если P = P2. Если P — эрмитова матрица, то P называют ортопроектором [2].
Фробениусовым эндоморфизмом для некоторого свойства Р [1] называется отображение TM --M такое, что из того, что мат-
nn
рица A обладает свойством P следует, что и матрица T (A) обладает свойством P.
Рассматривается свойство P — свойство матрицы быть проектором. В данной работе построено семейство отображений матриц, близких по свойствам к отображению сопряжения комплексных матриц TA-A*. (Сопряжение, как известно, сохраняет свойство матрицы быть проектором).
Пусть подпространства L и M пересекаются по нулевому вектору, и L + M = Cn. (Говорят, что L и M дополнительные подпространства). Обозначим матрицу, проектирующую на подпространство L вдоль подпространства M, как P (L, M).
vetkin@mgul. ac. ru
Для подпространства, натянутого на столбцы матрицы A (Im (A) — образа A), будем использовать такое обозначение: {A}. Если L = {A} иM = {B}, вместо P (L, M), или P ({A}, {B}) пишем просто P (A, B).
Пусть A и B — дополнительные подпространства, тогда
P*(A, B) = P (A1, B1). (1)
В связи с проектором P (A, B) часто возникают подпространства AMI1 и A1& lt-M.
Назовем их соответственно первым и вторым подпространством, связанным с проектором P (A, B).
У ортопроектора первое подпространство совпадает с его образом, а второе подпространство с его ядром. У произвольного проектора P и у сопряженного ему P* как первые, так и вторые подпространства совпадают, что следует из (1). В данной работе построено семейство отображений, элементы которого, подобно сопряжению *, являются инволюциями множества проекторов и сохраняют первое и второе подпространства.
В разделе 4, среди всех таких инволюций выделена одна, которая обозначена #
116
ЛЕСНОЙ ВЕСТНИК 6/2012
и обладает особыми свойствами, в частности (#*)4 = i, где i тождественное отображение матриц из M. (В данном случае * и # отображения проекторов).
Каноническая форма проектора относительно унитарного подобия В работе [4] Дьековичем предложена теорема о канонической форме проектора относительно унитарного подобия. Приведем формулировку этой теоремы из [3].
Теорема 1
Пусть P е Mn — проектор. Тогда существует унитарное подобие, приводящее P к блочно-диагональной форме
Qi
diag
& quot-1 Х1 & quot-1 xk
0 0 ,…, 0 0
, Im A j. (2)
Здесь x, & gt-… >- x, & gt- 0, I, O — единичная и нулевая матрицы соответствующего порядка и числа х1 … x k, m, s однозначно определяются проектором P.
В данной работе чаще будем использовать не Q1 из (2), а унитарно-подобную ей матрицу
& quot- h D 0 0
Q = 0 0k 0 0
0 0 1m 0
0 0 0 0,
D = diag{x1 … xk}, |x1| & gt-… >- |xJ & gt- °. (3)
Далее считаем, в отличие от теоремы 1, что диагональные элементы D, могут быть и отрицательными. (Изменение знака диагонального элемента D компенсируется очевидным изменением матрицы W, задающей унитарное подобие). Считаем, что одинаковые элементы диагонали D расположены рядом друг с другом- если есть элементы с одной абсолютной величиной, но разными знаками, то они располагаются также друг за другом.
В теореме 1 ничего не говорится о единственности унитарного подобия, приводящего к каноническому виду. Пусть существуют унитарные матрицы W и W2 такие, что P = WQW? = W2QW2*,
откуда следует, что W2*W1Q = QW2*W1. Обозначим F = W2*W1.
ДфЭст
Какой должна быть унитарная матрица F, чтобы для матрицы Q из (3) выполнялось?
FQ = QF. (4) Разобьем матрицу F на блоки в соответствии с блочной структурой матрицы Q
F = {F,}
i=1,2,3,4 j=1,2,3,4.
Из равенства (4) следует
F11 F11D F3 0
F21 F21D F23 0
F31 F31D F33 0
_ F41 F41D F43 0
Fu + DF2l f2 + DF22 F13 + DF F + DF 23 24
0 0 0 0
F31 F 1 32 F 33 F34
0 0 0 0
Откуда получаем
F = 0 °F = 0 °F = 0 °F = 0 °F = 0
21 ' 23 ' 34 ' 41 ' 43 '
F = F D — DF F = - DF F = F D
12 11 22 14 24 32 31
Поэтому унитарная матрица F имеет такой вид
& quot- F11 F11D — DF22 F13 -DF24
F = 0 F22 0 F24
F31 F31D F 33 0
0 F42 0 F 44
Будем последовательно рассматривать блоки матрицы R = F*F = I.
Выпишем блоки R и R
R11 = F11*F11 + F31*F31= l R12 = F11*(F11D1- DF22)+ F331*F31D = 0. (5)
Отсюда следует, учитывая то, что матрица D не особенная
F11*DF22 = D, detF11 + 0 detF22 + 0. (6) Так как R41 = - F2*DFX1 = 0, учитывая
(6) и то, что D не особенная, получим
R
44
F24 = 0.
Блок
F *D2 °F + F *F + F *F = F *F -24 24 24 24 44 44 44 44
(7)
I,
поэтому
F44 — унитарная матрица. (8)
Блок R42, учитывая (7), будет таким:
r42= f44*f42= 0, поэтому
F42 = 0. (9)
ЛЕСНОЙ ВЕСТНИК 6/2012
117
фйстД
Так как R31 = тывая (6), получим
F *F + F *f
1^ 11 33 31
0, учи-
F * = - F *F F 1 (10)
13 33 31 11
Подставив выражение для F из (10) в
R33 = F13*F13 + F33*F33 = I, получим
F *(F F 1 F * F * + I) F = I
33 31 11 11 31 33
и следовательно
detF33 ф 0. (11)
Еще раз подставив (10) в R32, получим R32 = F3*F31FnlDF22 = 0. Учитывая (6) и (11), а затем и (10), получим
F31 = 0, Fl3 = 0. (12)
Учитывая, что F = 0 в (5), получим F11, F22 — унитарные матрицы,
F12 = F11D — DF22 = 0. (13)
Из (7−9, 12, 13) следует, что унитарная
матрица F удовлетворяет условию FQ = QF, где матрицу Q определяет (3), тогда и только тогда, когда F имеет вид
F = diagF F2, F4, F4} и FD = DF2. (14)
При выводе (14) мы использовали только то свойство матрицы D, что она невырожденная.
Из (14) имеем
F2 = D1F1D и F2* = DF1*D1- F2F2*=
= D1F1D2F1*D1 = I. Следовательно,
F1D2 = D2F1, Fp2 = D2F2. (15)
Матрицу D2 можно рассматривать, как блочно-диагональную, каждый диагональный блок которой является скалярной матрицей. Как и при выводе (14), возьмем такое же блочное разбиение матрицы F и F как и у матрицы D2. Подстановка блочных разбиений матриц F1, F2 и D2 в (15) дает, что матрицы F1 и F2 блочно-диагональные.
Каждый скалярный блок матрицы D2 — diag{x2I } соответствует двум соседним скалярным блокам матрицы D — diag{xI, -xIq}. Возьмем диагональный блок f. (1)(f. (2) матрицы F1(F2), соответствующий диагональному блоку diag{x2I } матрицы D2. Рассмотрим блочное разбиение унитарных матриц f. (1) и f. (2)
f (i) J11 f (i) 12
f (i) 21 f (i) J22 _
i = 1,2-
(16)
с диагональными блоками f11(i), f, 2(i) порядков p и q, соответственно.
Равенство F1D = DF2 будет выполняться тогда и только тогда, когда для всех значений x в матрице D выполняется
f^^glx^ XIq} = diag{XIp, -XIq} fx (2). (17)
Подставив (16) в (17) получим
fx (2) = sps, S = diag{Ip, -Iq}. (18)
Из (7−9, 12, 13, 18) следует Теорема 2
Унитарная матрица F коммутирует с матрицей Q, имеющей вид (3), тогда и только тогда, когда Fудовлетворяет следующим условиям
F = diag{F1, F2, F4, F4} и F1D = DF2
Унитарные матрицы F F F F имеют порядки k, k, m, s соответственно. Одинаковые элементы диагонали D расположены рядом друг с другом- элементы с одной абсолютной величиной, но разными знаками, располагаются в соседних диагональных блоках.
Матрицы F1 и F2 — блочно-диагональные с равными размерами соответствующих блоков, причем каждый их диагональный блок имеет тот же порядок, что и соответствующий блок диагональных элементов матрицы D, имеющих одинаковый модуль.
При этом
F = SFS,
(19)
где S диагональная матрица с элементами 1 или -1, причем -1 соответствует тем позициям диагонали матрицы D, где стоят отрицательные числа.
Таким образом, матрица трансформации, определяющая каноническую форму проектора относительно унитарного подобия в виде
(3), определена с точностью до произвольного унитарного множителя F, задаваемого теоремой 2. Заметим, что если диагональ матрицы D состоит из чисел одного знака, то F2 = F1.
Рассмотрим представление проектора P = WQW, где Q имеет вид (3). Разобьем матрицу W на следующие блоки W = [W1:W. :W3:W4], W"W9 eMk, W3 е M, W4 е M, W*W. = I, W*W. = 0, i фj.
4 n, S гг 5 г j ч '- J
Скелетное разложение проектора P можно получить так
'-w-+dw2*
P = W • QW* = [W: w2: W3: W4]
0
W *
0
118
ЛЕСНОЙ ВЕСТНИК 6/2012
= [W: W3 ]
W1* + DW2* W *
(20)
Откуда следует
ImP = {[W1: W3]}, kerP = {[W-WDPWJ}, (21) (ImP)1 = {[W2: W4]}, (kerP)1 = {[W+W2D: W3]}.
Поэтому первое подпространство проектора P равно
ImP n (kerP)1 = { W3}, второе подпространство проектора P равно
kerP n (ImP)1 = { W4}.
(22)
Семейство отображений сохраняющих свойство матрицы быть проектором
Рассмотрим каноническую форму проектора P определяемую (3)
P = W
& quot- Ik D0 0& quot-
0 0 о 0
0 о 3 0
0 о о 0, _
= diag{x1, … xk},
W *
& quot- g1& quot- 1 1
1 bo 1 _ gk (х1,. 1
(23)
где х. Ф 0, W — унитарная матрица. Выбор вектора-столбца х = (х …, xk) T определяет диагональную матрицу D = diag{x} и проектор P. Рассмотрим результат отображения вектора х.
G (х) =
Если g. Ф 0, то следующая матрица PG, результат отображения P, также будет проектором
Dg (х) 0 0
0k 0 0
0 Im 0
0 0 0^
DG (x) = dkgg …, gk}. (24)
При этом — (24) каноническая форма проектора PG относительно унитарного подобия задаваемого матрицей W. Для ортопроекторов следует положить, что PG = P.
Скелетное разложение проектора PG, аналогично (20), будет
PG = W
Ik
0
0
0
W *
PG = [W: W3 ]
W* + DW W *
ДфЭст
Поэтому при отображении P^PG образ, первое подпространство, второе подпространство проектора P сохраняются.
Пусть у — значение одной из координат вектора х. Аналогично (16−18), этому значению соответствует скалярный блок матрицы D — diag{y/^} порядкар. Определим последовательные координаты вектора G (в количестве р штук), соответствующие координатам вектора z со значением у как вектор gpy. Аналогично вектор gpy определим как последовательные координаты вектора G (в количестве q штук), соответствующие координатам вектора х со значением -у.
Определение отображения проектора (24) будет корректным, если все представления проектора P в (23) с различными матрицами W будут отображаться в один и тот же проектор PG. Из теоремы 2 следует, что это будет при выполнении аналога равенства (17) для проектора PG
Л (1) diag
gp
g
q- у.
= diag
gP
g
q- у.
f (2) у
Здесь обозначение diag используется для задания диагональной матрицы, диагональ которой определяется компонентами вектора аргумента
diag (v) = diag (v1, …, v)
Учитывая (18) получим
fy1 diag
gp-у
gq,-у
S = diag
gp-у
gq,-у
Или
diag
gP, у
— g,
q,-у
diag
gP, у gq,-у
/У'-. (25)
Равенство (25) должно выполняться для произвольной унитарной матрицы /у (1), откуда следует, что все координаты векторов
gp^ и -^,-у равны друг дру^.
Таким образом, для того чтобы отображение G в (24) корректно определяло отображение проекторов необходимо, чтобы выполнялись следующие условия
х = У ^ g = g (26)
х+х1 = 0 ^ g+gj = а (27)
Есть три простых способа задать G так, чтобы выполнялись условия (26), (27).
ЛЕСНОЙ ВЕСТНИК 6/2012
119
фйстД
Первый способ. G (x) = S (x)x. Каждая компонента вектора x умножается на одно и то же ненулевое число — S (x). Для такого способа определения G (x), очевидно, выполняются свойства (26) и (27).
Интерес представляет случай, когда по аналогии с (P*)* = P выполняется
(PG)G = P, (28)
что эквивалентно G (G (x)) = x. Последнему функциональному уравнению удовлетворяет известное преобразование инверсии
G (x) = kx / Zx, (29)
i=1
для которого выполняются также (26) и (27). Здесь k — коэффициент инверсии. (Если k & lt- 0, то G (x) — антиинверсия). Если A — некоторая положительно определенная матрица, то можно записать более общее выражение чем (29)
G (x) = kx/(xTAx).
Второй способ. Отображение G (x) является линейным — G (x) = G (x). Причем G = = diag{…, yi, … }, каждый квадратный диагональный блок у. порядка г. соответствует группе координат вектора x с одинаковой абсолютной величиной.
Чтобы выполнялись условия (26) и (27), все столбцы следующей матрицы Г. порядка rj должны быть собственными векторами матрицы у.
Г
i
1 1
-1 1
1
1
-1 -1 ••• 1
В матрице Г. элементы ниже главной диагонали -1, остальные элементы 1.
Матрицу у с такими собственными векторами можно задать таким выражением
Y. = …, Ur}ГГ1,
где u произвольные ненулевые числа.
чтобы дополнительно выполнялось (28), числа и, определяющие матрицу у. должны равняться или 1, или -1. (Отметим, что все матрицы у. = rdiag{±1, …, ±1}Г. _1 имеют целочисленные элементы).
Третий способ. Обозначим через R0 — множество действительных чисел без нуля.
Пусть g функция, определенная на множестве R0 и принимающая значения из множества R0. Тогда отображение
G (x) = (жх …, g (xk))T, (30)
очевидно, удовлетворяет (26). чтобы выполнялось (27), необходимо, чтобы функция g была нечетной
Таким образом, каждая нечетная функция g: R0^R0 определяет фробениусов эндоморфизм множества проекторов. Композиция двух таких эндоморфизмов, определяемых нечетными функциями g1 и g2, очевидно, является фробениусовым эндоморфизмом, определяемым суперпозицией этих функций
— g1(g2(x)).
Отображение, задаваемое (30) будет удовлетворять (28), если функция g является обратной сама себе. Самыми простыми инво-лютивными нечетными функциями g: R0^R0 являются следующие функции: x, -x, 1/x, -1/ x. (Заметим, что последние две функции задают инверсию и антиинверсию в одномерном пространстве).
Фробениусов эндоморфизм, задаваемый последней функцией, обладает особыми свойствами, поэтому введем для него такое обозначение
P# = P, g (x) = -1/x.
Свойства инволюции, задаваемой функцией g (x) = -1/х
Перечислим некоторые свойства операции #.
— Проекторы P и P# имеют общие образ, первое подпространство, второе подпространство.
— Для любого проектора P выполняется (P#)# = P
— Если P ортопроектор, то P# = P.
Вернемся к последнему выражению
для P в (20). Представим P как сумму двух проекторов
P = W3W3* + W1(W1* + DW2*) = ^ + t. (31)
Первый проектор s = W3W3* является ортопроектором, второй — t = W1(W1* + DW2*), так сказать, строго косой проектор. Оба проектора имеют каноническую форму, получаемую с помощью подобия, определяемого унитарной матрицей W. При этом
P# = W3W3* + W1(W1* + DgW2*) = s + t#. (32)
120
ЛЕСНОЙ ВЕСТНИК 6/2012
Как легко убедиться из (31) и (32) следует
^ = P ({W3}) = W3W3* = P#P*. (33)
Следующая теорема показывает что, операция # особым образом взаимодействует с операцией сопряжения.
Теорема 3
Пусть P произвольный проектор, тогда в последовательности P = P P = P # P = P * P = P # P = P * (34) члены, начиная с девятого, повторяются, то есть PQ = P —
Пусть у проектора P каноническая форма (23). Операции # ничего не меняет в этой форме кроме матрицы D. Операция же * отражает матрицу D относительно главной диагонали. чтобы в дальнейшем применять операцию #, надо «вернуть» матрицу D на место. Это можно сделать, подправив унитарную матрицу W, задающую подобие.
Рассмотрим следующее подобие
с -s" «1 0» «c s» «1 -x»
s с x 0 -s c 0 0
s2 + с2 = 1, s + cx = 0. (35)
Величины s и c можно определить через x так
s = Г~Т, c = г~^ • (36)
V1 + x V1 + x
Аналогично можно «транспонировать» матрицу
& quot- I 0″
D 0
«c -s» «I 0» «c s» «I -D»
s c D 0 — s c 0 0
s2 + c2 = I, s + cD = 0,
где s, c и D диагональные матрицы, причем D = diag{x1, …, xk},
si =
1
+ x
, 2
-1
c i =
1
+ x
2
x
Каждая матрица P. в последовательности (34) имеет такое же представление, как (23), и определяется матрицей, задающей унитарное подобие W., и диагональной матрицей d, стоящей на месте D в (23). Будем
ДфЭст
последовательно рассматривать матрицы P. и определяющие их величины W. и d.
Pi = P, W = W, di = diag{., x…} (37)
P2 = Pi#, W2 = W, d2 = diag{., -1/x…}. (38) После выполнения следующей операции мы скомпенсируем транспонирование с помощью унитарного множителя
Hi = diag{hP mx где
h =
cs -s c
s + c (-1/x) = 0.
Поэтому
P3 = P2*, W3 = WHV d3 = diag{., 1/x…}. (39) Далее
P4 = P*, W4 = W#p d4 = diag{., -x…}. (40) Аналогично тому, как мы получали (39)
H2 = diag{h2, Im+s }, h2 =
c s -s'- C
sl + c,(-x!)= 0,
ИР5 = P4*, W5 = WH1H2, d5 = diag{., x…}. (41) Матрица d5 в (41) равна матрице d1 из (37), поэтому, повторив последовательность действий задаваемых (37−41) получим Pq = P8*, Wq = WHH2HH2, dQ = diag{., x…}. (42)
h1h2
Так как 0I
-I
¦ то H1H2 H1H2 =
Поэтому
PQ = WH1H2H1H2 diag& lt-
Ik d1
0k 0k
12k 0
0 / ,
,, 0s (X
xH 2 H1H 2 H1W * = p.
Доказательство теоремы 3 завершено.
Замечание 1
Можно доказать, что из инволютивных функций только функция g (x) = -1/x порождает отображение, которое взаимодействует с операцией * по схеме теоремы 3.
Замечание 2
В (21) для произвольного проектора P мы получили
kerP = {[W1 — W2D-u. W4]},
(kerP)1 = {[W1 + WD: W3]}.
Для P#, аналогичным образом получим kerP# = {[W1 + W2D: W4]},
(kerP#)1 = {[W1 —2D-1: W3]}.
ЛЕСНОЙ ВЕСТНИК 6/2012
121

ПоказатьСвернуть
Заполнить форму текущей работой