Заметил интересную вещь:
Когда матрица квадратная - все неизменяющиеся элементы на главной диагонали; когда матрица не является квадратной неизменяющиеся элементы гарантированно в начале и в конце + возможно такое соотношение размера матрицы, при котором существует диагональ
Если элементы главной диагонали смещаются вниз вправо строго на одну ячейку, то для такой диагонали необходимо найти это смещение
Но я так и не придумал способа лучше найти это смещение, как проход по матрице. При удачном исходе даже при огромных размерах ответ получается мгновенно, но это при удачном
Решение не универсально
А то, о чем вы говорите потребует огромные затраты памяти (матрица размером до 10⁹х10⁹)