Введение

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

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

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

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

Матричным представлением отношения равенства на конечном множестве является тождественная матрица I, то есть матрица, у которой все элементы на главной диагонали равны 1, а остальные – 0. В более общем случае, если отношение R удовлетворяет условию I ⊆ R, то R является рефлексивным отношением. Если булева область рассматривается как полукольцо, где сложение соответствует логическому ИЛИ, а умножение – логическому И, то матричное представление композиции двух отношений равно матричному произведению матричных представлений этих отношений. Это произведение можно вычислить за ожидаемое время O(n²). Часто операции над двоичными матрицами определяются в терминах модульной арифметики по модулю 2, то есть элементы рассматриваются как элементы поля Галуа. Они возникают в различных представлениях и имеют ряд более узких специальных форм. Они применяются, например, в задаче выполнимости XOR. Количество различных двоичных матриц размера m на n равно 2^(mn), и, следовательно, конечно.

Решетка

Пусть n и m заданы, а U обозначает множество всех логических матриц размера m × n. Тогда U имеет частичный порядок, определяемый Далее, U образует булеву алгебру с операциями «И» и «ИЛИ» между двумя матрицами, применяемыми покомпонентно. Дополнение логической матрицы получается заменой всех нулей на единицы и наоборот. Каждая логическая матрица A = (Aij) имеет транспонированную матрицу AT = (Aji). Предположим, что A — логическая матрица, не содержащая ни одной строки или столбца, состоящего только из нулей. Тогда, при использовании булевой арифметики, произведение матрицы содержит единичную матрицу размера m × m, а произведение содержит единичную матрицу размера n × n. Как математическая структура, булева алгебра U образует решетку, упорядоченную по включению; дополнительно, она является мультипликативной решеткой благодаря умножению матриц. Каждая логическая матрица в U соответствует бинарному отношению. Перечисленные операции над U и порядок соответствуют исчислению отношений, где умножение матриц представляет собой композицию отношений.

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

Если m или n равно 1, то логическая матрица m × n (mij) является логическим вектором или битовой строкой. Если m = 1, вектор является строковым вектором, а если n = 1, то столбцовым вектором. В любом случае индекс, равный 1, опускается из обозначения вектора. Пусть P и Q – два логических вектора. Внешнее произведение P и Q дает прямоугольное отношение m × n. Перестановка строк и столбцов такой матрицы может собрать все единицы в прямоугольную часть матрицы. Пусть h – вектор, состоящий из одних единиц. Тогда, если v – произвольный логический вектор, отношение R = v hᵀ имеет постоянные строки, определяемые вектором v. В исчислении отношений такое R называется вектором. Ранней задачей в этой области было "найти необходимые и достаточные условия для существования инцидентной структуры с заданными степенями точек и блоков; или, на языке матриц, для существования (0, 1)-матрицы размера v × b с заданными суммами строк и столбцов". Эта задача решена теоремой Гейла — Райзера.