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

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

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

Если р это бинарное отношение между конечным индексированные наборы Икс и Y (так р ⊆ Икс×Y), тогда р может быть представлена ​​логической матрицей M чьи индексы строк и столбцов индексируют элементы Икс и Y, соответственно, такие, что записи M определяются:

${displaystyle M_{i,j}={egin{cases}1&(x_{i},y_{j})in R�&(x_{i},y_{j})ot in Rend{cases}}}$

Для обозначения номеров строк и столбцов матрицы наборы Икс и 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)}.

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

${displaystyle {egin{pmatrix}1&1&1&1�&1&0&1�&0&1&0�&0&0&1end{pmatrix}}}$ который включает диагональ единиц, поскольку каждое число делится само.

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

• А матрица перестановок представляет собой (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]

Часто операции с двоичными матрицами определяются в терминах модульная арифметика mod 2, то есть элементы рассматриваются как элементы Поле Галуа GF(2) = ℤ₂. Они возникают во множестве представлений и имеют ряд более узких специальных форм. Они применяются, например, в XOR-выполнимость.

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

Решетка

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

${displaystyle msubset nquad { ext{when}}quad forall i,jquad m_{ij}=1implies n_{ij}=1.}$

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

Каждая логическая матрица a = (a _{я j} ) имеет транспонировать а^Т = (а _{j i} ). Предполагать а логическая матрица без столбцов или строк, тождественно нулевых. Тогда матричное произведение, используя булеву арифметику, a^Т а содержит м × м единичная матрица, а произведение a a^Т содержит п × п личность.

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

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

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

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

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

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

${displaystyle M_{ij}=P_{i}land Q_{j}.}$ Переупорядочивание строк и столбцов такой матрицы может собрать все единицы в прямоугольную часть матрицы.^[4]

Позволять час быть вектором всех единиц. Тогда если v - произвольный логический вектор, соотношение р = v h^Т имеет постоянные строки, определяемые v. в исчисление отношений такой р называется вектор.^[4] Частным случаем является универсальное отношение ч ч^Т.

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

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

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

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

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

Смотрите также

• Список матриц
• Бинаторикс (бинарный тор Де Брёйна)
• Битовый массив
• Матрица Редхеффера

Примечания

1. Петерсен, Кьельд (8 февраля 2013 г.). «Бинматрица». Получено 11 августа, 2017.
2. Патрик Э. О'Нил; Элизабет Дж. О'Нил (1973). "Быстрый алгоритм ожидаемого времени для умножения логических матриц и транзитивного замыкания". Информация и контроль. 22 (2): 132–138. Дои:10.1016 / с0019-9958 (73) 90228-3. - Алгоритм полагается на сложение идемпотент, ср. с.134 (внизу).
3. Ирвинг Копиловиш (Декабрь 1948 г.). «Матричное развитие исчисления отношений», Журнал символической логики 13(4): 193–203 Ссылка Jstor
4. Гюнтер Шмидт (2013). «6: Отношения и векторы». Реляционная математика. Издательство Кембриджского университета. п. 91. Дои:10.1017 / CBO9780511778810. ISBN  9780511778810.
5. Бет, Томас; Юнгникель, Дитер; Ленц, Ханфрид (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]