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

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

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

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

${\ Displaystyle M_ {я, j} = {\ begin {case} 1 & (x_ {i}, y_ {j}) \ in R \\ 0 & (x_ {i}, y_ {j}) \ not \ in R \ end {case}}}$

Для того , чтобы назначить номера строк и столбцов матрицы, множества X и Y индексируются с положительными целыми числами: я в диапазоне от 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)}.

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

${\displaystyle {\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 на диагонали соответствует циклу в соответствующей вершине.
• Biadjacency матрица простого, неориентированный двудольный граф является (0,1) -матрица, и любой (0,1) -матрица возникает таким образом.
• Простые множители списка м бесквадратные , п -гладких чисел может быть описана как м × П ( п ) (0,1) -матрица, где π является функция распределения простых чисел и _IJ равен 1 , если и только если j- е простое число делит i- е число. Это представление полезно в алгоритме разложения на квадратные сита .
• Растровое изображение , содержащее пиксели только в двух цветов может быть представлена в виде (0,1) -матрицы , в которой 0 представляют пиксели одного цвета и 1 представляют пиксели другого цвета.
• Двоичная матрица может использоваться для проверки правил игры в игре го ^[1]

Некоторые свойства [ править ]

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

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

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

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

Решетка [ править ]

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

${\displaystyle m\subset n\quad {\text{when}}\quad \forall i,j\quad m_{ij}=1\implies n_{ij}=1.}$

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

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

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

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

Логические векторы [ править ]

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

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

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

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

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

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

Суммы строк и столбцов [ править ]

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Хогбен, Лесли (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 Mathematics 12: 463–76.
• Райзер, Х. Дж. (1960) "Матрицы из нулей и единиц", Бюллетень Американского математического общества 66: 442–64.
• Д. Р. Фулкерсон (1960) "Матрицы нуля или единицы с нулевым следом", Тихоокеанский математический журнал 10; 831–6
• Д. Р. Фулкерсон и Х. Дж. Райзер (1961) "Ширина и высота (0, 1) -матриц", Canadian Journal of Mathematics 13: 239–55.
• Л. Р. Форд-младший и Д. Р. Фулкерсон (1962) § 2.12 «Матрицы, составленные из нулей и единиц », стр. 79–91 в « Потоки в сетях» , Princeton University Press MR 0159700

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме двоичной матрицы .

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