Логическая матрица - Logical matrix
А логическая матрица, двоичная матрица, матрица отношений, Логическая матрица, или же (0,1) матрица это матрица с записями из Логический домен B = {0, 1}. Такую матрицу можно использовать для представления бинарное отношение между парой конечные множества.
Матричное представление отношения
Если р это бинарное отношение между конечным индексированные наборы Икс и Y (так р ⊆ Икс×Y), тогда р может быть представлена логической матрицей M чьи индексы строк и столбцов индексируют элементы Икс и Y, соответственно, такие, что записи M определяются:
Для обозначения номеров строк и столбцов матрицы наборы Икс и Y проиндексированы положительными целыми числами: я колеблется от 1 до мощность (размер Икс и j колеблется от 1 до мощности Y. См. Запись на индексированные наборы для более подробной информации.
Пример
Бинарное отношение р на съемочной площадке {1, 2, 3, 4} определяется так, что aRb выполняется тогда и только тогда, когда а разделяет б равномерно, без остатка. Например, 2р4 выполняется, потому что 2 делит 4, не оставляя остатка, но 3р4 не выполняется, потому что, когда 3 делит 4, остается 1. Следующий набор - это набор пар, для которых соотношение р держит.
- {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.
Соответствующее представление в виде логической матрицы:
- который включает диагональ единиц, поскольку каждое число делится само.
Другие примеры
- А матрица перестановок представляет собой (0,1) -матрицу, все столбцы и строки которой имеют ровно один ненулевой элемент.
- А Массив Костаса является частным случаем перестановочной матрицы
- An матрица инцидентности в комбинаторика и конечная геометрия имеет те, которые указывают инцидент между точками (или вершинами) и линиями геометрии, блоки блочная конструкция, или края граф (дискретная математика)
- А матрица дизайна в дисперсионный анализ является (0,1) -матрицей с постоянными строчными суммами.
- Логическая матрица может представлять собой матрица смежности в теория графов: несимметричные матрицы соответствуют ориентированные графы, симметричные матрицы к обычным графики, а 1 на диагонали соответствует петля в соответствующей вершине.
- В матрица двойственности простой, неориентированной двудольный граф является (0,1) -матрицей, и любая (0,1) -матрица возникает таким образом.
- Основные факторы списка м без квадратов, п-гладкий числа можно описать как м× π (п) (0,1) -матрица, где π - функция подсчета простых чисел и аij равно 1 тогда и только тогда, когда j-е простое число делит яй номер. Это представление полезно в квадратное сито алгоритм факторинга.
- А растровое изображение содержащий пиксели только два цвета могут быть представлены в виде (0,1) -матрицы, в которой нули представляют пиксели одного цвета, а единицы представляют пиксели другого цвета.
- Двоичная матрица может использоваться для проверки правил игры в игре Идти [1]
Некоторые свойства
Матричное представление отношение равенства на конечном множестве - это единичная матрица I, то есть матрица, все элементы которой на диагонали равны 1, а все остальные - 0. В более общем случае, если соотношение р удовлетворяет I ⊂ р, то R является рефлексивное отношение.
Если логический домен рассматривается как полукольцо, где сложение соответствует логическое ИЛИ и умножение на логическое И, матричное представление сочинение двух отношений равно матричный продукт матричных представлений этих отношений. Это произведение может быть вычислено в ожидал время O (п2).[2]
Часто операции с двоичными матрицами определяются в терминах модульная арифметика mod 2, то есть элементы рассматриваются как элементы Поле Галуа GF(2) = ℤ2. Они возникают во множестве представлений и имеют ряд более узких специальных форм. Они применяются, например, в XOR-выполнимость.
Количество различных м-к-п двоичные матрицы равны 2млн, и поэтому конечен.
Решетка
Позволять п и м быть дано и пусть U обозначают набор всех логических м × п матрицы. потом U имеет частичный заказ данный
Фактически, U образует Булева алгебра с операциями и & или же между двумя матрицами, нанесенными покомпонентно. Дополнение логической матрицы получается заменой всех нулей и единиц их противоположными.
Каждая логическая матрица a = (a я j ) имеет транспонировать аТ = (а j i ). Предполагать а логическая матрица без столбцов или строк, тождественно нулевых. Тогда матричное произведение, используя булеву арифметику, aТ а содержит м × м единичная матрица, а произведение a aТ содержит п × п личность.
Как математическая структура, булева алгебра U образует решетка заказан включение; Кроме того, это мультипликативная решетка за счет матричного умножения.
Каждая логическая матрица в U соответствует бинарному отношению. Эти перечисленные операции на U, и упорядочение соответствуют исчисление отношений, где умножение матриц представляет состав отношений.[3]
Логические векторы
Групповые структуры | |||||
---|---|---|---|---|---|
Тотальностьα | Ассоциативность | Личность | Обратимость | Коммутативность | |
Полугрупоидный | Ненужный | Необходимый | Ненужный | Ненужный | Ненужный |
Малая категория | Ненужный | Необходимый | Необходимый | Ненужный | Ненужный |
Группоид | Ненужный | Необходимый | Необходимый | Необходимый | Ненужный |
Магма | Необходимый | Ненужный | Ненужный | Ненужный | Ненужный |
Квазигруппа | Необходимый | Ненужный | Ненужный | Необходимый | Ненужный |
Единичная магма | Необходимый | Ненужный | Необходимый | Ненужный | Ненужный |
Петля | Необходимый | Ненужный | Необходимый | Необходимый | Ненужный |
Полугруппа | Необходимый | Необходимый | Ненужный | Ненужный | Ненужный |
Обратная полугруппа | Необходимый | Необходимый | Ненужный | Необходимый | Ненужный |
Моноид | Необходимый | Необходимый | Необходимый | Ненужный | Ненужный |
Коммутативный моноид | Необходимый | Необходимый | Необходимый | Ненужный | Необходимый |
Группа | Необходимый | Необходимый | Необходимый | Необходимый | Ненужный |
Абелева группа | Необходимый | Необходимый | Необходимый | Необходимый | Необходимый |
^ α Закрытие, который используется во многих источниках, является аксиомой, эквивалентной совокупности, хотя и по-другому. |
Если м или же п равно единице, то м × п логическая матрица (Mя j) - логический вектор. Если м = 1 вектор является вектор-строкой, и если п = 1 это вектор-столбец. В любом случае индекс, равный единице, исключается из обозначения вектора.
Предполагать два логических вектора. В внешний продукт из п и Q приводит к м × п прямоугольное отношение:
- Переупорядочивание строк и столбцов такой матрицы может собрать все единицы в прямоугольную часть матрицы.[4]
Позволять час быть вектором всех единиц. Тогда если v - произвольный логический вектор, соотношение р = v hТ имеет постоянные строки, определяемые v. в исчисление отношений такой р называется вектор.[4] Частным случаем является универсальное отношение ч чТ.
Для данного отношения р, максимальное прямоугольное отношение, содержащееся в р называется концепция в R. Отношения можно изучить, разложив на понятия, а затем отмечая индуцированная решетка понятий.
Рассмотрим таблицу группоподобных структур, где «ненужные» могут быть обозначены 0, а «требуемые» обозначены 1, образуя логическую матрицу. р. Для расчета элементов R RТ необходимо использовать внутреннее логическое произведение пар логических векторов в строках этой матрицы. Если этот внутренний продукт равен 0, то строки ортогональны. Фактически, полугруппа ортогональна петле, малая категория ортогональна квазигруппе, а группоид ортогонален магме. Следовательно, в R RТ и это не может быть универсальное отношение.
Суммы строк и столбцов
Сложение всех единиц в логической матрице можно выполнить двумя способами: сначала суммировать строки или сначала суммировать столбцы. Когда суммируются строчные суммы, сумма такая же, как и при добавлении сумм по столбцам. В геометрия падения, матрица интерпретируется как матрица инцидентности где строки соответствуют «точкам», а столбцы - «блокам» (обобщающие линии, составленные из точек). Строка-сумма называется ее балльная степень а сумма столбца - это степень блока. Предложение 1.6 в Теория дизайна[5] говорит, что сумма степеней точки равна сумме степеней блока.
Первой проблемой в этой области было «найти необходимые и достаточные условия для существования структура заболеваемости с заданными степенями точки и степенями блока (или, на языке матриц, для существования (0,1) -матрицы типа v × б с заданными суммами по строкам и столбцам ".[5] Такая структура представляет собой блочная конструкция.
Смотрите также
- Список матриц
- Бинаторикс (бинарный тор Де Брёйна)
- Битовый массив
- Матрица Редхеффера
Примечания
- ^ Петерсен, Кьельд (8 февраля 2013 г.). «Бинматрица». Получено 11 августа, 2017.
- ^ Патрик Э. О'Нил; Элизабет Дж. О'Нил (1973). "Быстрый алгоритм ожидаемого времени для умножения логических матриц и транзитивного замыкания". Информация и контроль. 22 (2): 132–138. Дои:10.1016 / с0019-9958 (73) 90228-3. - Алгоритм полагается на сложение идемпотент, ср. с.134 (внизу).
- ^ Ирвинг Копиловиш (Декабрь 1948 г.). «Матричное развитие исчисления отношений», Журнал символической логики 13(4): 193–203 Ссылка Jstor
- ^ а б Гюнтер Шмидт (2013). «6: Отношения и векторы». Реляционная математика. Издательство Кембриджского университета. п. 91. Дои:10.1017 / CBO9780511778810. ISBN 9780511778810.
- ^ а б Бет, Томас; Юнгникель, Дитер; Ленц, Ханфрид (1986). Теория дизайна. Издательство Кембриджского университета. п. 18.. 2-е изд. (1999) ISBN 978-0-521-44432-3
Рекомендации
- Хогбен, Лесли (2006), Справочник по линейной алгебре (дискретная математика и ее приложения), Бока-Ратон: Chapman & Hall / CRC, ISBN 978-1-58488-510-8, § 31.3, Двоичные матрицы
- Ким, Ки Ханг (1982), Теория логических матриц и приложения, ISBN 978-0-8247-1788-9
- Х. Дж. Райзер (1957) «Комбинаторные свойства матриц нулей и единиц», Канадский математический журнал 9: 371–7.
- Райзер, Х.Дж. (1960) "Следы матриц нулей и единиц", Канадский математический журнал 12: 463–76.
- Райзер, Х.Дж. (1960) "Матрицы нулей и единиц", Бюллетень Американского математического общества 66: 442–64.
- Д. Р. Фулкерсон (1960) «Матрицы нуля или единицы с нулевым следом», Тихоокеанский математический журнал 10; 831–6
- Д. Р. Фулкерсон и Х. Дж. Райзер (1961) "Ширина и высота (0, 1) -матриц", Канадский математический журнал 13: 239–55.
- Л. Р. Форд-младший И Д. Р. Фулкерсон (1962) § 2.12 «Матрицы, составленные из нулей и единиц», стр. 79–91 в Потоки в сетях, Princeton University Press МИСТЕР0159700
внешняя ссылка
- «Логическая матрица», Энциклопедия математики, EMS Press, 2001 [1994]