Логическая матрица

, Логическая матрица двоичная матрица , матрица отношений , булева матрица или (0, 1)-матрица — это матрица с элементами из логической области $B = {0, 1}.$ Такая матрица может использоваться для представления бинарного отношения между парой конечных множеств . Это важный инструмент в комбинаторной математике и теоретической информатике .

Матричное представление отношения

Если R — бинарное отношение между конечными индексированными множествами X и Y (поэтому $R \subseteq X \times Y$ ), то R может быть представлено логической матрицей M, индексы строк и столбцов которой индексируют элементы X и Y соответственно, такие, что записи M определяются формулой

m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}

Чтобы обозначить номера строк и столбцов матрицы, множества X и Y индексируются положительными целыми числами : i варьируется от 1 до ( размера) X , а j варьируется от 1 до мощности Y. мощности Более подробную информацию можно найти в статье об индексированных наборах .

Пример

Бинарное отношение R на множестве ${1, 2, 3, 4}$ определяется так, что aRb выполняется тогда и только тогда, когда a делит b поровну, без остатка. Например, 2 R 4 выполняется, потому что 2 делит 4, не оставляя остатка, но 3 R 4 не выполняется, потому что, когда 3 делит 4, остается остаток от 1. Следующий набор представляет собой набор пар, для которых соотношение R. выполняется .

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

Соответствующее представление в виде логической матрицы имеет вид

{\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},

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

Другие примеры

Матрица перестановок — это (0, 1)-матрица, все столбцы и строки которой содержат ровно один ненулевой элемент.
- Массив Костаса — это частный случай матрицы перестановок.
Матрица инцидентности в комбинаторике и конечной геометрии имеет матрицы, обозначающие инцидентность между точками (или вершинами) и линиями геометрии, блоками блочной конструкции или ребрами графа .
Матрица плана в дисперсионном анализе представляет собой (0, 1)-матрицу с постоянными суммами строк.
Логическая матрица может представлять собой матрицу смежности в теории графов : несимметричные матрицы соответствуют ориентированным графам , симметричные матрицы — обычным графам , а 1 на диагонали соответствует петле в соответствующей вершине.
Матрица двусмежности простого неориентированного двудольного графа представляет собой (0, 1)-матрицу, и любая (0, 1)-матрица возникает таким образом.
Простые факторы списка m от квадратов свободных n -гладких чисел можно описать как матрицу m × π( n ) (0, 1), где π — функция подсчета простых чисел , а a _ij равен 1, если и только если j -е простое число делит i -е число. Это представление полезно в алгоритме факторизации квадратичного сита .
Растровое изображение, содержащее пиксели только двух цветов, можно представить в виде (0, 1)-матрицы, в которой нули представляют пиксели одного цвета, а единицы — пиксели другого цвета.
Бинарную матрицу можно использовать для проверки правил игры в игре Го . ^[1]
Четырехзначная логика из двух битов, преобразованная логическими матрицами 2х2, образует систему переходов .
Рекуррентный график и его варианты представляют собой матрицы, показывающие, какие пары точек находятся ближе определенного порога близости в фазовом пространстве .

Некоторые свойства

Матричное представление отношения равенства на конечном множестве — это единичная матрица I , то есть матрица, все элементы которой на диагонали равны 1, а все остальные равны 0. В более общем смысле, если отношение R удовлетворяет $I \subseteq R,$ то R — рефлексивное отношение .

Если булева область рассматривается как полукольцо , где сложение соответствует логическому ИЛИ , а умножение — логическому И , то матричное представление композиции двух отношений равно матричному произведению матричных представлений этих отношений. Этот продукт можно вычислить за ожидаемое время O( n ²). ^[2]

Часто операции над двоичными матрицами определяются в терминах модульной арифметики по модулю 2, то есть элементы рассматриваются как элементы поля Галуа. ${\mathbf {GF}}(2)=\mathbb {Z} _{2}$ . Они возникают в самых разных представлениях и имеют ряд более ограниченных специальных форм. Они применяются, например, в XOR-выполнимости .

Число различных mxn матриц размером двоичных равно 2 ^минута, и поэтому является конечным.

Решетка

Пусть n и m заданы, и пусть U обозначает множество всех логических матриц размера m × n . Тогда U имеет частичный порядок , определяемый формулой

\forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.

Фактически, U образует булеву алгебру операций и & или с покомпонентным применением между двумя матрицами. Дополнение логической матрицы получается путем замены всех нулей и единиц на противоположные.

Каждая логическая матрица $A = (A ij)$ имеет транспонирование $A Т = (А джи).$ Предположим, что A — логическая матрица, в которой нет столбцов или строк с тождественным нулем. Тогда матричное произведение, используя булеву арифметику, $A^{\operatorname {T} }A$ содержит m × m единичную матрицу размера и произведение $AA^{\operatorname {T} }$ содержит тождество n × n .

Как математическая структура, булева алгебра U образует решетку, упорядоченную по включению ; кроме того, это мультипликативная решетка из-за умножения матриц.

Каждая логическая матрица в U соответствует бинарному отношению. Эти перечисленные операции над U и упорядочение соответствуют исчислению отношений , где умножение матриц представляет собой композицию отношений . ^[3]

Логические векторы

Групповые структуры
	Закрытие	Ассоциативный	Личность	Отмена	коммутативный
Частичная магма	Ненужный	Ненужный	Ненужный	Ненужный	Ненужный
Полугруппоид	Ненужный	Необходимый	Ненужный	Ненужный	Ненужный
Малая категория	Ненужный	Необходимый	Необходимый	Ненужный	Ненужный
группоид	Ненужный	Необходимый	Необходимый	Необходимый	Ненужный
Коммутативный группоид	Ненужный	Необходимый	Необходимый	Необходимый	Необходимый
Магма	Необходимый	Ненужный	Ненужный	Ненужный	Ненужный
Коммутативная магма	Необходимый	Ненужный	Ненужный	Ненужный	Необходимый
Квазигруппа	Необходимый	Ненужный	Ненужный	Необходимый	Ненужный
Коммутативная квазигруппа	Необходимый	Ненужный	Ненужный	Необходимый	Необходимый
Ассоциативная квазигруппа	Необходимый	Необходимый	Ненужный	Необходимый	Ненужный
Коммутативно-ассоциативная квазигруппа	Необходимый	Необходимый	Ненужный	Необходимый	Необходимый
Единая магма	Необходимый	Ненужный	Необходимый	Ненужный	Ненужный
Коммутативная унитарная магма	Необходимый	Ненужный	Необходимый	Ненужный	Необходимый
Петля	Необходимый	Ненужный	Необходимый	Необходимый	Ненужный
Коммутативный цикл	Необходимый	Ненужный	Необходимый	Необходимый	Необходимый
Полугруппа	Необходимый	Необходимый	Ненужный	Ненужный	Ненужный
Коммутативная полугруппа	Необходимый	Необходимый	Ненужный	Ненужный	Необходимый
Моноид	Необходимый	Необходимый	Необходимый	Ненужный	Ненужный
Коммутативный моноид	Необходимый	Необходимый	Необходимый	Ненужный	Необходимый
Группа	Необходимый	Необходимый	Необходимый	Необходимый	Ненужный
Абелева группа	Необходимый	Необходимый	Необходимый	Необходимый	Необходимый

Если m или n равно единице, то логическая матрица m × n ( m _ij ) представляет собой логический вектор или битовую строку . Если m = 1, вектор является вектором-строкой, а если n = 1, это вектор-столбец. В любом случае индекс, равный 1, исключается из обозначения вектора.

Предполагать $(P_{i}),\,i=1,2,\ldots ,m$ и $(Q_{j}),\,j=1,2,\ldots ,n$ два логических вектора. Внешнее произведение P . и Q приводит к m × n прямоугольному отношению

m_{ij}=P_{i}\land Q_{j}.

Перестановка строк и столбцов такой матрицы позволяет собрать их все в прямоугольную часть матрицы. ^[4]

Пусть h — вектор всех единиц. Тогда если v — произвольный логический вектор, то соотношение R = vh ^Т имеет постоянные строки, определяемые v . В исчислении отношений такой R называется вектором. ^[4] Частным примером является универсальное отношение $hh^{\operatorname {T} }$ .

Для данного отношения R максимальное прямоугольное отношение, содержащееся в , называется концептом в R. R Отношения можно изучать путем разложения на понятия, а затем отмечая индуцированную решетку понятий .

Рассмотрим таблицу группоподобных структур, где «ненужные» можно обозначить 0, а «обязательные» обозначить 1, образуя логическую матрицу. $R.$ Для расчета элементов $RR^{\operatorname {T} }$ , необходимо использовать скалярное произведение пар логических векторов в строках этой матрицы. Если этот внутренний продукт равен 0, то строки ортогональны. Фактически малая категория ортогональна квазигруппе , а группоид ортогонален магме . Следовательно, в $RR^{\operatorname {T} }$ и оно не может быть универсальным отношением .

Суммы строк и столбцов

Сложение всех чисел в логической матрице можно выполнить двумя способами: сначала суммировать строки или сначала суммировать столбцы. При добавлении сумм строк эта сумма такая же, как и при добавлении сумм столбцов. В геометрии инцидентности матрица интерпретируется как матрица инцидентности , строки которой соответствуют «точкам», а столбцы — «блокам» (обобщающим линиям, состоящим из точек). Сумма строк называется степенью точки , а сумма столбца — степенью блока . Сумма степеней точки равна сумме степеней блока. ^[5]

Первой проблемой в этой области было «найти необходимые и достаточные условия для существования структуры инцидентности с заданными степенями точек и степеней блоков; или, на матричном языке, для существования (0, 1)-матрицы типа v × b с заданными суммами строк и столбцов». ^[5] Эта проблема решается теоремой Гейла–Райзера .

См. также

Примечания

^ Петерсен, Кьельд (8 февраля 2013 г.). «Бинматрица» . Проверено 11 августа 2017 г.
^ Патрик Э. О'Нил; Элизабет Дж. О'Нил (1973). «Алгоритм быстрого ожидаемого времени для умножения булевых матриц и транзитивного замыкания». Информация и контроль . 22 (2): 132–138. дои : 10.1016/s0019-9958(73)90228-3 . — Алгоритм основан на идемпотентности сложения , ср. стр.134 (внизу).
^ Ирвинг Копиловиш (декабрь 1948 г.). «Матричное развитие исчисления отношений», Журнал символической логики 13 (4): 193–203 Jstor link
^ Jump up to: ^а ^б Гюнтер Шмидт (2013). «6: Отношения и векторы». Реляционная математика . Издательство Кембриджского университета. п. 91. дои : 10.1017/CBO9780511778810 . ISBN 9780511778810 .
^ Jump up to: ^а ^б Например, см. Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1999). Теория дизайна (2-е изд.). Издательство Кембриджского университета . п. 18. ISBN 978-0-521-44432-3 .

Ссылки

Ричард А. Бруальди (2006), Комбинаторные матричные классы. Энциклопедия математики и ее приложений, 108. Издательство Кембриджского университета, Кембридж, 2006. ISBN 978-0-521-86565-4
Ричард А. Бруальди и Герберт Дж. Райзер (1991), Комбинаторная теория матриц . Энциклопедия математики и ее приложений, 39. Издательство Кембриджского университета, Кембридж, 1991. ISBN 0-521-32265-0
Хогбен, Лесли (2006), Справочник по линейной алгебре (дискретная математика и ее приложения) , Бока-Ратон: Chapman & Hall/CRC, ISBN 978-1-58488-510-8 , § 31.3, Двоичные матрицы
Ким, Ки Ханг (1982), Теория и приложения булевых матриц , ISBN 978-0-8247-1788-9
Х. Дж. Райзер (1957), «Комбинаторные свойства матриц нулей и единиц», Canadian Journal of Mathematics 9: 371–7.
Х. Дж. Райзер (1960), «Следы матриц нулей и единиц», Canadian Journal of Mathematics 12: 463–76.
Х. Дж. Райзер (1960), «Матрицы нулей и единиц», Бюллетень Американского математического общества 66: 442–64.
Д. Р. Фулкерсон (1960) «Матрицы ноль-единица с нулевым следом», Pacific Journal of Mathematics 10; 831–6
Д. Р. Фулкерсон и Х. Дж. Райзер (1961), «Ширина и высота (0, 1)-матриц», Canadian Journal of Mathematics 13: 239–55.
Л.Р. Форд-младший и Д.Р. Фулкерсон (1962) § 2.12 «Матрицы, состоящие из 0 и 1», страницы с 79 по 91 в книге « Потоки в сетях» , Princeton University Press , MR 0159700

Внешние ссылки

«Логическая матрица» , Энциклопедия математики , EMS Press , 2001 [1994]

[1] Петерсен, Кьельд (8 февраля 2013 г.). «Бинматрица» . Проверено 11 августа 2017 г.

[2] Патрик Э. О'Нил; Элизабет Дж. О'Нил (1973). «Алгоритм быстрого ожидаемого времени для умножения булевых матриц и транзитивного замыкания». Информация и контроль . 22 (2): 132–138. дои : 10.1016/s0019-9958(73)90228-3 . — Алгоритм основан на идемпотентности сложения , ср. стр.134 (внизу).

[3] Ирвинг Копиловиш (декабрь 1948 г.). «Матричное развитие исчисления отношений», Журнал символической логики 13 (4): 193–203 Jstor link

[GS-4] Jump up to: ^а ^б Гюнтер Шмидт (2013). «6: Отношения и векторы». Реляционная математика . Издательство Кембриджского университета. п. 91. дои : 10.1017/CBO9780511778810 . ISBN 9780511778810 .

[BJL-5] Jump up to: ^а ^б Например, см. Бет, Томас; Юнгникель, Дитер ; Ленц, Ханфрид (1999). Теория дизайна (2-е изд.). Издательство Кембриджского университета . п. 18. ISBN 978-0-521-44432-3 .

[1]

[2]

[3]

[4]

[5]

v т и Матричные классы
Явно ограниченные записи	Чередование Антидиагональ антиэрмитовский Антисимметричный наконечник стрелы Группа двуугольный Бисимметричный Блок-диагональ Блокировать Блок трехдиагональный логическое значение Коши Центросимметричный Конференция Комплекс Адамара Сопозитивный Диагональная доминанта Диагональ Дискретное преобразование Фурье элементарный Эквивалент Фробениус Обобщенная перестановка Адамар Приобретение эрмитовский Хессенберг Пустой Целое число Логический Матричный блок Мецлер Мур Неотрицательный Пятиугольный перестановка Персимметричный Полиномиальный кватернионный Подпись косо-эрмитовский Кососимметричный Горизонт Редкий Сильвестр Симметричный Тёплиц Треугольный Трехдиагональный Вандермонде Уолш С
Постоянный	Обмен Гильберт Личность Лемер Из них Паскаль Паули Редхеффер Сдвиг Ноль
Условия на собственные значения или собственные векторы	Компаньон Конвергентный Дефектный Определенный Диагонализуемый Гурвиц Положительно-определенный Стилтьес
Выполнение условий на изделия или инверсы	Конгруэнтный Идемпотент или проекция Обратимый Инволютивный Нильпотентный Нормальный Ортогональный Унимодульный Одномогущий Унитарный Полностью унимодульный Взвешивание
С конкретными приложениями	Адъюгат знак чередования Дополненный Безу Карлеман Картан циркулирующий Кофактор коммутация Путаница Коксетер Расстояние Дублирование и устранение Евклидово расстояние Фундаментальное (линейное дифференциальное уравнение) Генератор Грамм Гессен Домохозяин якобиан Момент Расплачиваться Выбирать случайный Вращение Зейферт сдвиг Сходство симплектический Полностью позитивный Трансформация
Используется в статистике	Центрирование Корреляция Ковариация Дизайн Двойной стохастический Информация о Фишере Имеет Точность Стохастический Переход
Используется в теории графов	Смежность Бисмежность Степень Эдмондс Заболеваемость лапласиан Соседство Зайделя Все
Используется в науке и технике	Кабиббо – Кобаяши – Маскава Плотность Фундаментальный (компьютерное зрение) Нечеткая ассоциативность Гамма Гелл-Манн гамильтониан Нерегулярный Перекрывать С Государственный переход Замена З (химия)
Связанные термины	Джордан в нормальной форме Линейная независимость Матричная экспонента Матричное представление конических сечений Идеальная матрица Псевдообратный Форма эшелона строк Вронскиан
Математический портал Список матриц Категория:Матрицы