close

Вход

Забыли?

вход по аккаунту

- Саратовский государственный университет

код для вставкиСкачать
О. О. Щекатурова, В. А. Ярошевич. О свойствах булевых матриц
5. Kilp M., Knauer U., Mikhalev A. V. Monoids, acts
гонах над полугруппами // Мат. заметки. 2010. Т. 87,
and cathegories. Berlin; N. Y., 2000. 529 с.
№ 6. С. 855–866.
6. Максимовский М. Ю. О биполигонах и мультиполи-
7. Курош А. Г. Теория групп. М. : Наука, 1967. 648 с.
Congruences of Acts over Groups
A. R. Khaliullina
National Research University of Electronic Technology (MIET), Russia, 124498, Moscow, Zelenograd, pass. 4806, 5,
[email protected]
A complete description of the congruences of acts over groups is obtained.
Key words: act, congruence, group.
References
1. Kudriavtsev V. B., Podkolzin A. S., Ushchumlich Sh.
Vvedenie
v
teoriiu
abstraktnykh
avtomatov
[Introdunction in abstract automata theory]. Moscow,
MGU, 1985, 176 p. (in Russian).
2. Lallement G. Semigroups and combinatorial
applications. New York, Wiley, 1979, 376 p.
3. Avdeev A. Yu., Kozhuhov I. B. Acts over completely
0-simple semigroups. Acta Cybernet, 2000, vol. 14, no. 4.
pp. 523–531.
4. Ohemke R. H. Congruences and semisiplicity for Rees
matrix semigroups. Pacif. J. Math., 1974, vol. 54, no. 2.
pp. 143–164.
5. Kilp M., Knauer U., Mikhalev A. V. Monoids, acts
and cathegories. Berlin, New York, 2000. 529 p.
6. Maksimovskii M. Yu. Bipolygons and multipolygons
over semigroups. Math. Notes, 2010, vol. 87, no. 5–6,
pp. 834–843.
7. Kurosh A. G. Teoriia grupp [Group theory]. Moscow,
Nauka, 1967, 648 p. (in Russian).
УДК 512.554+512.643
О СВОЙСТВАХ БУЛЕВЫХ МАТРИЦ
О. О. Щекатурова1 , В. А. Ярошевич2
1
Аспирант кафедры геометрии, Саратовский государственный университет им. Н. Г. Чернышевского, [email protected]
2
Кандидат физико-математических наук, доцент кафедры высшей математики № 1, Национальный исследовательский
университет «МИЭТ», Москва, [email protected]
Рассматривается частичная полугруппа булевых матриц конечных размеров относительно операций конъюнктного и дизъюнктного умножений. Получена оценка соотношения числа векторов в строчном и столбцовых базисах. Найдены предминимальный, а также предпредминимальный и предмаксимальный в обобщённом смысле D-классы. Исследуются свойства
вторичных идемпотентов. Предложена гипотеза рекурсивного построения приведённых матриц.
Ключевые слова: булева матрица, конъюнктное произведение, дизъюнктное произведение, строчная оболочка, столбцовая оболочка, строчный ранг, столбцовый ранг, приведённая матрица, классы Грина, первичный идемпотент, вторичный
идемпотент.
ВВЕДЕНИЕ
Назовём ∪ — объединением, ∩ — пересечением, а ′ — дополнением. Обозначим
hMm×n , ∪, ∩,′ , 0, 1i алгебру булевых m × n матриц с элементами из некоторой булевой алгебры
hB, ∪, ∩,′ , 0, 1i. Операции ∩, ∪ и ′ определяются для матриц поэлементно. Матрицы 0 и 1, образованные целиком из нулей и единиц соответственно, дают нуль и единицу такой вторичной булевой
алгебры. Для краткости вместо Mn×n будем писать Mn . Пусть символ M обозначает множество
S
всех матриц конечных размеров, то есть M = m,n∈N Mm×n . В дальнейшем, если специально не
оговорено, мы полагаем, что исходная булева алгебра двухэлементна, то есть B = {0, 1}.
© Щекатурова О. О., Ярошевич В. А., 2013
137
Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 4, ч. 2
Sm
Матрицу C = A ⊓ B ∈ Mm×p с элементами cij = k=1 (aik ∩ bkj ) назовём конъюнктным произведением матриц согласованных размеров A ∈ Mm×n и B ∈ Mn×p . Дизъюнктное произведение
A ⊔ B, определяется дуальным образом: A ⊔ B = (A′ ⊓ B ′ )′ . Введём частичный порядок на множестве
булевых векторов длины n: будем писать (a1 , . . . , an ) 6 (b1 , . . . , bn ), если ak 6 bk при k = 1, 2, . . . , n.
Обозначим i-ю строку матрицы A через Ai∗ , аналогично j-й столбец через A∗j . Рассмотрим линейную оболочку строк матрицы:
R(A) = L(A1∗ , A2∗ , . . . , An∗ ) = {(λ1 ∩ A1∗ ) ∪ (λ2 ∩ A2∗ ) ∪ . . . ∪ (λn ∩ An∗ )},
где λk ∈ B, k = 1, 2, . . . , n. Аналогично определим линейную оболочку C(A) столбцов матрицы. В
работе [1, теорема 1.2.3] доказано, что |R(A)| = |C(A)|.
В множестве R(A) (C(A)) можно выделить набор ненулевых векторов, которые нельзя выразить в
виде линейной комбинации других векторов из R(A) (C(A)). Такие вектора образуют базис линейной
оболочки R(A) (C(A)). В случае двухэлементной булевой алгебры базис определяется однозначно [1,
теорема 1.1.1]. Количество векторов в базисе оболочки R(A) (C(A)) называется строчным (столбцовым) рангом и обозначается ρr A (ρc A). Назовём матрицу A размера m × n приведённой, если
ρc A = m и ρr A = n.
1. РАНГИ
Теорема 1 (Батлер [2, теорема 5]). Пусть A ∈ Mn , тогда (i) ρr A = 1 ⇔ ρc A = 1,
(ii) ρr A = 2 ⇔ ρc A = 2, (iii) ρr A = 3 ⇒ 3 6 ρc A 6 4.
Возникает вопрос: в каком диапазоне может изменяться ρc A при фиксированном ρr A? Для ответа
рассмотрим в булевом кубе Bm из векторов длины m максимальные антицепи. Среди них выберем
антицепи, которые содержат наибольшее количество векторов. В полученном множестве антицепей
выберем ту антицепь A, вектора которой содержат больше единиц. Векторы антицепи имеют длину
m и состоят из ⌊m/2⌋ нулей и m − ⌊m/2⌋ единиц. Заменим любой вектор из A на любые два, ему
e будем рассматривать как вектор-столбцы и
предшествующие. Векторы в полученном множестве A
e В результате получится приведённая матрица A, ранги
объединим их в матрицу размера m × |A|.
которой дают ответ на поставленный вопрос:
e =
ρc A = |A|
ρr A = m,
⌊m/2⌋
Cm
m!
−1+2=
+1
⌊m/2⌋! · (m − ⌊m/2⌋)!
m→∞
∼
r
2 2m
·√ .
π
m
Рассмотрим некоторые примеры приведённых матриц размера m × n, которые будут использованы
в дальнейшем.
0
1
bm =
E
..
.
1
1
m = n,
bm )| = m + 1;
|R(E
0
1
Em =
Qm =
1
0
m = n,
|R(Em )| = 2m ;
1
Em−1
1 1
···
n = 2m − 2,
|R(A)| = 2m − 1.
Em−1
1
0 0 ···
0
2. КЛАССЫ ГРИНА
В этой работе символы D и J будут обозначать отношения Грина на полугруппе Mn (см. [3,
гл. 2]). В силу конечности полугруппы Mn справедливо равенство D = J . В связи с этим будем
в дальнейшем говорить только о D-классах. D-класс, содержащий матрицу A, будем обозначать
DA . Так как D = J , то множество всех D-классов можно упорядочить в смысле естественно
возникающего частичного порядка на множестве главных идеалов: DA 6 DB ⇔ ∃ X, Y : A = XBY.
138
Научный отдел
О. О. Щекатурова, В. А. Ярошевич. О свойствах булевых матриц
Считаем, что DA < DB ⇔ DA 6 DB и DA 6= DB . Несложно проверить, что фактор-множество
множества Mn по отношению D не является решёткой при n > 2.
Наряду с рассмотрением множества Mn всех (не только приведённых) квадратных матриц,
естественным будет рассмотрение множества матриц M(6n)×(6n) произвольного размера p × q, где
max{p, q} 6 n. Множество таких матриц образует частичную полугруппу. Как отмечено в [4], на этой
частичной полугруппе можно рассматривать отношения Грина
же, как на обычной полугруппе.
à так !
1 1
Теорема 2. Обозначим: D1 = D(0), D2 = D(1), D3 = D
. Тогда для любого D-класса D,
1 0
отличного от D1 , D2 и D3 , справедливо соотношение D1 < D2 < D3 < D.
Доказательство. Для любых двух D-классов D′ и D′′ имеет место эквивалентность:
(D′ 6 D′′ ) ⇔ (∀ A′ ∈ D′ , ∀ A′′ ∈ D′′ , ∃ X, Y : A′ = XA′′ Y ).
Очевидно, что в последнем выражении в качестве A′ и A′′ достаточно рассматривать не все матрицы
из D′ и D′′ , а лишь приведённые. Дальнейшие рассуждения будем проводить, выбирая в качестве
представителей D-классов только приведённые матрицы.
В силу теоремы 1 приведённая матрица размера m × n, где m, n 6 2, может иметь размер либо
1 × 1, либо 2 × 2. Несложно проверить, что с точностью до перестановки строк и столбцов существует
всего 4 приведённые матрицы таких размеров:
!
!
Ã
Ã
1 0
1 1
∈
/ D1 ∪ D2 ∪ D3 .
∈ D3 ,
(0) ∈ D1 , (1) ∈ D2 ,
0 1
1 0
Все остальные приведённые матрицы ввиду теоремы 1 имеют
размер
! Ã ! m × n такой, что m, n > 3.
Ã
1
1 1
. Это доказывает неравенства
Очевидно, что (0) = (0)(1)(0) и (1) = (1 1)
1
1 0
D1 6 D2 6 D3 . Рассмотрим соотношение D3 6 D. Пусть A — любая Ã
приведённая
матрица, не
!
1 0
принадлежащая множеству D1 ∪ D2 ∪ D3 . Такая матрица A есть либо
, либо A должна
0 1
иметь
размер m × n, где m, n > 3. Нужно
матрицы
! X и Y , для которых
!Ã
Ã
! Ã что !найдутся
!
à показать,
Ã
1 0
1 0
1 1
1 1
1 1
. Пусть теперь A имеет
=
= XAY. В первом случае имеем:
0 1
0 1
1 0
1 0
1 0
ij
размер m × n, где m, n > 3. Рассмотрим матрицу Em
, которая отличается от единичной матрицы Em
ij
лишь тем, что eii = ejj = 0 и eij = eji = 1. Очевидно, что умножение A слева на Em
равносильно
ij
перестановке i-ой и j-ой строк матрицы A. Аналогично, умножение A справа на Em равносильно
перестановке i-го и j-го столбцов матрицы A.
В приведённой матрице A все строки попарно различные, то есть любые две строки отличаются
хотя бы в одной позиции. Во всякой приведённой матрице A, где количество строк и столбцов не
меньше 3, найдутся две строки с номерами k и l, а также два столбца с номерами s и t такие, что
матрица A представима в виде A(u) , u = 1, 2, . . . , 6:




...................
...................




· · · 1 · · · 0 · · ·
· · · 1 · · · 1 · · ·




(2)



A(1) = 
. . . . . . . . . . . . . . . . . . . или A = . . . . . . . . . . . . . . . . . . . ,




· · · 0 · · · 1 · · ·
· · · 1 · · · 0 · · ·
...................
...................
kl (1)
A(3) = Em
A ,
kl (2)
A(4) = Em
A ,
st
A(5) = A(2) Em
,
kl (2) st
A(6) = Em
A Em .
Отметим, что матрица A может иметь одновременно несколько представлений в виде A(u) ,
u = 1, 2, . . . , 6, но нам достаточно любого из них. Далее матрицу A(u) , u = 1, 2, . . . , 6 можно приМатематика
139
Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 4, ч. 2
(u)
вести к виду A2 , u = 1, 2:
(1)
A2


1 0 ···


= 0 1 · · ·
.........
или
(2)
A2
Это можно осуществить с помощью преобразований
(1)
1s 2t
1k 2l
Em ),
Em )A(1) (Em
A2 = (Em
(1)
1l 2k
(3)
1s 2t
A2 = (Em Em )A (Em Em ),
(2)
1k 2l
1t 2s
A2 = (Em
Em )A(5) (Em
Em ),


1 1 ···


= 1 0 · · · .
.........
(2)
1s 2t
1k 2l
Em ),
Em )A(2) (Em
A2 = (Em
(2)
1l 2k
(4)
1s 2t
A2 = (Em Em )A (Em Em ),
(2)
1l 2k
1t 2s
A2 = (Em
Em )A(6) (Em
Em ).
Обозначая произведения матриц в скобках справа и слева от A(u) , u = 1, 2, . . . , 6 соответственно
(u)
(u)
(u)
и Y1 , получаем, что A2 = X1 A(u) Y1 . Пусть
(u)
X1
Ã
1 0
X2 =
0 1
0···
0···
!
0
,
0
(1)
Y2
Ã
1 1
=
1 0
0 ···
0 ···
!⊤
0
,
0
(2)
Y2
Ã
1
=
0
0 0
1 0
···
···
!⊤
0
.
0
Ã
!
Ã
!
1 1
1 1
(1) (1)
(2)
(2) (2)
Если A2 =
то
= X2 A2 Y2 . Иначе, если A2 = A2 , то
= X2 A2 Y2 . В
1 0
1 0
!
Ã
1 1
= (X2 X1 )A(Y1 Y2 ) = XAY ,
итоге, опуская верхний индекс в обозначениях матриц, запишем
1 0
где X и Y равны соответствующим выражениям в скобках слева и справа от A.
Для завершения доказательства покажем, что D1 6= D2 6= D3 6= D. Этим будет установлено,
что D1 < D2 < D3 < D. Действительно, приведённые матрицы в указанных четырёх D-классах
невозможно перевести друг в друга, меняя местами строки и столбцы.
¤
Теорема 3. Пусть m > 3. Для любого D-класса D, отличного от DQm и DEm , с приведённой
матрицей размера p × q, где p 6 m, справедливо неравенство D < DQm < DEm .
Доказательство. Неравенство DQm < DEm верно, так как Qm = Em · Em · Qm и DQm 6= DEm .
Пусть теперь D — некоторый D-класс, отличный от DQm и DEm , c приведённой матрицей A размера
p × q, где p 6 m. Докажем, что A = XQm Y для некоторых матриц X и Y .
Обозначим через A1 матрицу A вместе с дописанными к ней снизу m − p нулевыми строками.
Очевидно, A1 = X1 A, где X1 — матрица размера m × p, у которой единицы стоят только на главной
диагонали и остальные элементы равны нулю.
Пусть ek — вектор-столбец, содержащий только одну единицу в позиции с номером k. В линейной
оболочке столбцов матрицы Qm , очевидно, отсутствует только один вектор-столбец em . Следовательно, C(Qm ) = {0, 1}m \{em }. Возможны два случая:
(i) em 6∈ C(A1 ) или, что то же самое, C(A1 ) ⊆ C(Qm ). Умножая справа матрицу Qm на некоторый
вектор-столбец u, мы получим один из векторов w линейной оболочки C(Qm ). Причём w равен
объединению в точности тех столбцов матрицы Qm , на позициях которых стоят единицы вектора
u. Ясно, что, вычисляя последовательно столбцы Y∗j , j = 1, . . . , q матрицы Y и требуя выполнения
(A1 )∗j = Qm Y∗j , получим всю матрицу Y . В итоге получится, что
(1)
A2 ,
A = Ep
0p×(m−p) A1 = Ep
0p×(m−p) Qm Y.
(ii) em ∈ C(A1 ). Так как DA1 < DEm , то в A1 не могут быть представлены все вектор-столбцы ei ,
i = 1, 2, . . . , m длины m. Найдётся номер k такой, что столбец ek не входит в A1 . Рассмотрим матрицу
km
A2 = Em
A1 . Для неё выполняется C(A2 ) ⊆ C(Qm ) и аналогично случаю (i) найдётся матрица Y
km 2
km
такая, что A2 = Qm Y . Так как (Em
) = Em , то A1 = Em
Qm Y . В итоге получаем:
³
´
km
Qm Y.
¤
A = Ep 0p×(m−p) A1 = Ep 0p×(m−p) Em
140
Научный отдел
О. О. Щекатурова, В. А. Ярошевич. О свойствах булевых матриц
Ã
!
1 1
На основании теорем 2 и 3 назовём класс D(1) предминимальным, а класс D
— пред1 0
предминимальным, класс DQm назовём предмаксимальным в обобщённом смысле. Действительно,
всякий D-класс с приведённой матрицей A размера p × q, min{p, q} 6 m меньше либо равен DQm
.
или DQ⊤
m
3. ИДЕМПОТЕНТЫ
Поплавский [4, теорема 4.1] доказал, что матрицы A ⊔ A′⊤ , A′⊤ ⊔ A, A⊤ ⊔ A′ , A′ ⊔ A⊤ являются идемпотентами в полугруппе hM, ⊓i с операцией конъюнктного произведения ⊓. Обозначим
i(A) = A ⊔ A′⊤ , то есть мы будем рассматривать лишь идемпотенты, полученные по первой формуле.
Для других формул теория не будет иметь принципиальных отличий. Утверждение Поплавского о
том, что i(i(A)) = i(A), позволяет естественным образом ввести понятия первичного идемпотента,
то есть идемпотента X, для которого X 6= i(X), и вторичного идемпотента, то есть идемпотента X,
для которого X = i(X).
Следующие утверждения очевидны, поэтому их доказательства мы не приводим.
Лемма 4. Перестановка двух столбцов матрицы A не меняет значения i(A). Перестановка
двух строк с номерами s и t матрицы A приводит к перестановке строк с номерами s и t, а
также столбцов с номерами s и t матрицы i(A).
Tn
Лемма 5. Пусть A — матрица размера m × n, тогда i(A) = k=1 i(A∗k ).
Заметим, что матрице A размера m × n соответствует идемпотент i(A) размера m × m. Интересен
вопрос: для каких матриц A и B справедливо равенство i(A) = i(B)?
Теорема 6. Если для двух матриц A ∈ Mm×n и B ∈ Mm×p с элементами из произвольной
булевой алгебры B имеет место равенство C(A) ∪ 1n×1 = C(B) ∪ 1n×1 , где 1n×1 обозначает
вектор-столбец длины n, состоящий из единиц, то i(A) = i(B).
Доказательство. Случай C(A) = C(B) был разобран в [4, теорема 4.4]. Рассмотрим случай
C(A) = C(B) ∪ 1n×1 . Ясно, что столбцовый базис матрицы A отличается от столбцового базиса
eиB
e матрицы, образованные векматрицы B присутствием единичного столбца. Обозначим через A
e и i(B) = i(B).
e Так
торами столбцовых базисов матриц A и B соответственно. Очевидно i(A) = i(A)
как перестановка столбцов любой матрицы C не влияет на значение i(C), то можно считать, что
e и Y = i(B).
e Для элемента матрицы X справедливо
e= B
e 1n×1 . Обозначим X = i(A)
A
ei∗
xij = B
ej∗ )′⊤
(B
=
1 ⊔
0
Ã
n
\
k=1
ebik ∪ eb′
jk
!
∩ (0 ∪ 1) =
n
\
k=1
ebik ∪ eb′ = yij .
jk
e = i(B).
e Окончательно i(A) = i(B). Аналогично рассматриваются
Следовательно, X = Y или i(A)
случаи C(A) ∪ 1n×1 = C(B) и C(A) ∪ 1n×1 = C(B) ∪ 1n×1 .
¤
Справедливо ли утверждение теоремы в обратную сторону, пока неизвестно.
4. РЕКУРСИВНОЕ ПОСТРОЕНИЕ ПРИВЕДЁННЫХ МАТРИЦ
Компьютерные вычисления показывают, что все приведённые матрицы размера 4 × 4 можно получить, используя все приведённые матрицы размера 3×3 за счёт дописывания специально подобранного
столбца и строки. На этом основании мы выдвигаем гипотезу.
Гипотеза. Всякую приведённую матрицу размера (n+1)×(n+1) можно получить из некоторой
приведённой матрицы размера n × n дописыванием специально подобранного столбца и строки.
Пусть A — приведённая матрица. Ниже показаны два частных случая рекурсивного построения
приведённых матриц:
B=
Математика
A
01×n
1n×1
,
1
|R(B)| = |R(A)| + 1;
B=
A
01×n
0n×1
,
1
|R(B)| = 2|R(A)|.
141
Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 4, ч. 2
Библиографический список
1. Kim Ki Hang Boolean Matrix Theory and Applications.
N. Y. : Marcel Dekker, 1982. 288 p.
2. Butler K. Binary relations // Recent Trends in Graph
Theory. 1971. Vol. 186. P. 25–47.
3. Клиффорд А., Престон Г. Алгебраическая теория
полугрупп : в 2 т. Т. 1. М. : Мир, 1972. 286 с.
4. Поплавский В. Б. О приложениях ассоциативности дуальных произведений алгебры булевых матриц // Фундаментальная и прикладная математика.
2012. № 4. C. 181–192.
On the Properties of Boolean Matrices
O. O. Shchekaturova1 , V. A. Yaroshevich2
1
Saratov State University, Russia, 410012, Saratov, Astrakhanskaya st., 83, [email protected]
2
National Research University of Electronic Technology (MIET), Russia, 124498, Moscow, Zelenograd, pass. 4806, 5,
[email protected]
We consider the partial semigroup of Boolean matrices of various finite sizes under the operations of conjunctive and disjoint
multiplication. We estimate the possible number of vectors in the row basis and column basis. The subminimal, subsubminimal
and submaximal in general sense D-classes are found. The properties of secondary idempotents are investigated. A conjecture of
recursive construction of the reduced matrices is suggested.
Key words: Boolean matrix, conjunctive product, disjoint product, row span, column span, row rank, column rank, reduced matrix,
Green’s classes, primary idempotent, secondary idempotent.
References
1. Kim Ki Hang Boolean Matrix Theory and
Applications. New York, Marcel Dekker, 1982, 288 p.
2. Butler K. Binary relations. Recent Trends in Graph
Theory, 1971, vol. 186, pp. 25–47.
3. Clifford A. H., Preston G. B. The Algebraic Theory
142
of Semigroups, Vol. 1. Mathematical Surveys and
Monogrphs, Providence, R.I., AMS, 1961.
4. Poplavski V. B. On Applications of Associativity of
Dual Compositions in the Algebra of Boolean Matrices.
Journal of Math. Sciences, 2013, vol. 191, 5, pp. 718–725.
Научный отдел
1/--страниц
Пожаловаться на содержимое документа