Максимальный в строке A должен быть меньше, чем в строке A + 1, чтобы эти две строки считались отсортированными?
Одинаковыми могут быть.
Отсортиированная матриица -- значит каждый столбик -- отсортированный массив, и каждая строчка -- отсортированный массив