Как подсчитать количество классов эквивалентности матриц? (см. Детали)
Родилась задача. Может решение уже известно знатокам, или известно, что его нет)).
Рассматриваются все квадратные матрицы размера n x n, состоящие только из нулей и единиц. Из комбинаторики ясно, что всего таких разных матриц 2^(n^2). Теперь нужно подсчитать количество классов эквивалентности. Эквивалентными считаются матрицы, которые можно получить друг из друга перестановкой столбцов и строк.
Для n=2 получилось перебрать варианты, классов оказалось 6. Но как решать в общем виде, идей нет. Перебирать для 3*3 уже руками не получится. Подскажите, в каком направлении двигаться.
Более широким классом эквивалентности будут матрицы с одинаковым детерминантом. При ваших преобразованиях сохраняется модуль детерминанта. Детерминант сохраняется при любых парах преобразований. Отдельно следует рассматривать нулевую матрицу.
Для матрицы два на два из нулей и единиц
D=ab-cd
имеет 3 значения (-1, 0, 1). Изза того что нулевое слагаемое может быть представлено двумя неэквивалентными способами получаем что для каждого значения по два класса эквивалентности.
Полагаю что метод обобщения понятен. Чем больше порядок матрицы тем больше степень произведения слагаемого в детерминанте.
Ваше количество классов эквивалентности определяется, очевидно, количеством подгрупп группы перестановок S(n). В общем виде задача определения этого количества не решена, для n=3 вы подсчитали это вручную. Для n=4 количество подгрупп 22.