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

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

• 1 Матричное представление отношения
  • 1.1 Пример
• 2 Другие примеры
• 3 Некоторые свойства
• 4 Решетка
• 5 Логические векторы
• 6 Суммы строк и столбцов
• 7 См. Также
• 8 Примечания
• 9 Ссылки
• 10 Внешние ссылки

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

$M\; i,\; j\; =\; \{1\; (xi,\; yj)\; \in \; R\; 0\; (\; xi,\; yj)\; \notin \; R\; \{\backslash \; displaystyle\; M\_\; \{i,\; j\}\; =\; \{\backslash \; begin\; \{cases\}\; 1\; (x\_\; \{i\},\; y\_\; \{j\})\; \backslash \; in\; R\; \backslash \backslash \; 0\; (x\_\; \{i\},\; y\_\; \{j\})\; \backslash \; not\; \backslash \; in\; R\; \backslash \; end\; \{cases\}\}\}$

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

Пример

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

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

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

$(1\; 1\; 1\; 1\; 0\; 1\; 0\; 1\; 0\; 0\; 1\; 0\; 0\; 0\; 0\; 1)\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 1\; 1\; 1\; \backslash \backslash \; 0\; 1\; 0\; 1\; \backslash \; \backslash \; 0\; 0\; 1\; 0\; \backslash \backslash \; 0\; 0\; 0\; 1\; \backslash \; end\; \{pmatrix\}\}\}$, который включает диагональ единиц, поскольку каждое число делится само себя.

• A матрица перестановок - это (0,1) -матрица, все столбцы и строки которой имеют ровно один ненулевой элемент.
  • A Массив Костаса является частным случаем матрицы перестановок
• Матрица инцидентности в комбинаторике и конечная геометрия имеет матрицы для указания инцидентности между точками (или вершинами) и линиями геометрии, блоками блочного дизайна или краями графа (дискретная математика)
• A проектной матрицей в анализе дисперсия представляет собой (0,1) -матрицу с постоянными суммами строк.
• Логическая матрица может представлять матрицу смежности в теории графов : не- симметричные матрицы соответствуют ориентированным графам, симметричные матрицы - обычным графам, а 1 на диагонали соответствует петле в соответствующей вершине.
• Матрица двойного сопряжения простого неориентированного двудольного графа является (0,1) -матрицей, и любая (0,1) -матрица возникает таким образом.
• Простые множители списка из m бесквадратных, n-гладких чисел могут быть описаны как am × π (n) (0,1) -матрица, где π - простое ко Функция nting и ij равна 1 тогда и только тогда, когда j-е простое число делит i-е число. Это представление полезно в алгоритме факторизации квадратного сита.
• A растровое изображение, содержащее пикселей только двух цветов, может быть представлено как (0,1) -матрица в где 0 представляют пиксели одного цвета, а 1 представляют пиксели другого цвета.
• Двоичная матрица может использоваться для проверки правил игры в игре Go

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

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

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

Количество различных двоичных матриц размером m на n равно 2 и, таким образом, является конечным.

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

$m\; \subset \; n,\; когда\; \forall \; i,\; jmij\; =\; 1\; ⟹\; nij\; =\; 1.\; \{\backslash \; displaystyle\; m\; \backslash \; subset\; n\; \backslash \; quad\; \{\backslash \; text\; \{when\}\}\; \backslash \; quad\; \backslash \; forall\; i,\; j\; \backslash \; quad\; m\_\; \{ij\}\; =\; 1\; \backslash \; подразумевает\; n\_\; \{ij\}\; =\; 1.\}$

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

Каждая логическая матрица a = (a i j) имеет транспонирование a = (a j i). Предположим, что a - логическая матрица без столбцов или строк, равных нулю. Затем произведение матриц с использованием булевой арифметики a a содержит единичную матрицу размера m × m , а произведение a a содержит единицу n × n.

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

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

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

Предположим, $(P\; i),\; i\; =\; 1,\; 2,...\; m\; и\; (Q\; j),\; j\; =\; 1,\; 2,...\; п\; \{\backslash \; displaystyle\; (P\_\; \{i\}),\; \backslash \; quad\; я\; =\; 1,2,...\; м\; \backslash \; \backslash \; \{\backslash \; text\; \{и\}\}\; \backslash \; \backslash \; (Q\_\; \{j\}),\; \backslash \; quad\; j\; =\; 1,2,...n\}$- два логических вектора. Внешнее произведение P и Q приводит к прямоугольному соотношению :

$m\; \times \; nM\; i\; j\; =\; P\; i\; Q\; j.\; \{\backslash \; displaystyle\; M\_\; \{ij\}\; =\; P\_\; \{i\}\; \backslash \; land\; Q\_\; \{j\}.\}$Переупорядочение строк и столбцов такой матрицы может собрать все единицы в прямоугольную часть матрица.

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

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

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

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

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

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

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