Преобразование матриц

[deil]

Всем доброго времени суток!

У меня возникла следующая задача:
Есть матрица A размерностью n*n.
Необходимо ее преобразовать в матрицу B размерностью m*m (m < n).
Преобразование при этом должно быть обратимо.

В какую сторону мне копать, то есть какие теоремы необходимо проштудировать?

Заранее спасибо за посильную помощь.

[gris]

Начните с простейшего случая. Придумать обратимое преобразование матриц $2\times 2$ в число. По существу это биективное отображение $R^4$ на $R$.
Ну и аналогично для других размеров.
Существует такое отображение?
Есть ли формула для него?
Надеюсь, с понятием мощности множества Вы знакомы?

[ИСН]

Короче: как без потерь запаковать два числа в одно.
---
Ответ критическим образом зависит от того, зачем Вам это нужно.

[bot]

Какими свойствами, кроме обратимости должно обладать, это преобразование? Если никаких, то требуется лишь бесконечность множества $X$, над которым рассматриваются матрицы. В этом случае декартовы степени $X^{n^2}$ равномощны при любых $n$.
Может быть лучше рассказать о Вашей задаче?

[deil]

Задача заключается в следующем:

Есть наборы коэффициентов, которые представляют собой матрицу A.
Таких наборов может быть большое количество. Их необходимо сравнивать на соответствие друг другу, то есть пробегаемся по наборам и смотрим - попадался нам уже такой или нет.

[ewert]

deil в сообщении #241131 писал(а):

Задача заключается в следующем:

Есть наборы коэффициентов, которые представляют собой матрицу A.
Таких наборов может быть большое количество. Их необходимо сравнивать на соответствие друг другу, то есть пробегаемся по наборам и смотрим - попадался нам уже такой или нет.

Как не крути -- а придётся сравнивать тупым перебором всех элементов матрицы.

Если я правильно понял предыдущие замечания, Вам рекомендуют установить какую-либо биекцию $\mathbb R^{n,n}$ на $\mathbb R$ -- например, перемежая цифры. После чего потребуется сравнивать только по одному числу. Теоретически это возможно, однако практически (с учётом конечности разрядной сетки) будет катастрофически потеряна точность. Конечно, с этим можно справиться, прибегнув к длинной арифметике, но по трудозатратам это к тому же перебору и сведётся.

[gris]

Тогда, мне кажется, это чисто практическая компьютерная задача из области поиска-сортировки. Здесь необходим критерий соответствия двух наборов. Могут ли наборы разного размера соответствовать друг другу.
Идея обратимого отображения здесь, наверное, неэффективна. Просто если определение соответствия (не просто равенства) двух матриц трудоёмко, то можно действительно для предварительного отбора рассчитывать для каждой матрицы некоторый параметр, согласованный с критерием соответствия. Но не обязательно требовать обратимости.

[deil]

Существует ограничение на значения коэффициентов матрицы A, которое, возможно, позволит решить задачу более простым образом:

все коэффициенты - целые числа, и их сумма постоянна и равна Z

[ewert]

deil в сообщении #241137 писал(а):

их сумма постоянна и равна Z

ну, это лишь одна связь, фактически количество элементов всего лишь уменьшено на единичку, не стоит и обращать внимания

[gris]

Если бы они были ещё и натуральными.

А что надо делать? Просто сравнивать матрицы? Тогда поэлементное сравнение даже быстрее - позволяет вываливаться в середине цикла.

Вы скажите, какие две матрицы соответствуют друг другу? Просто равные? Тогда нечего и огород городить.

[deil]

1-ая и основная задача - сравнение. Две матрицы равны, когда все их элементы равны.
2-ая задача - логи появления данных. Т.е. необходимо определять какие данные и в какой момент пришли

[gris]

Ну для проверки равенства целочисленных матриц быстрее поэлементного сравнения вряд ли что найдёте.
Зная особенности матриц, можно было бы поиграть с порядком рассмотрения элементов. То есть подумать над алгоритмом выделения некоторого эффективного необходимого признака равенства. Но это всё просто теоретизирование.
Например, если стоит задача выделения из миллиарда матриц размером тыща на тыщу групп равных матриц.

[Circiter]

А что если нарезать каждую матрицу на блоки и последовательно сужать область поиска проверяя равенство соответствующих блоков? То есть, если два соответствующих блока каких-либо двух матриц неравны, то отбрасываем одну из этих матриц и берем следующую, если же блоки равны --- сравниваем следующую пару блоков, etc...

[deil]

Circiter в сообщении #241164 писал(а):

А что если нарезать каждую матрицу на блоки и последовательно сужать область поиска проверяя равенство соответствующих блоков? То есть, если два соответствующих блока каких-либо двух матриц неравны, то отбрасываем одну из этих матриц и берем следующую, если же блоки равны --- сравниваем следующую пару блоков, etc...

Одна из первых мыслей была именно такой.
Смущает только необходимость ведения логов: слишком большой объем информации придется хранить при условии того, что вариантов возможных значений матрицы не так уж и много (примерно 1000000)