Не умаляя общности, будем считать, что $$$n \le m$$$.

Ответ на задачу — «Yes» тогда и только тогда, когда в некоторой строке матрицы $$$a_{i,j}$$$ существует возрастающая последовательность длины хотя бы $$$m - n + 1$$$. Докажем это. Если в строке $$$i$$$ существует такая последовательность с индексами $$$j_1, j_2, \ldots, j_{m - n + 1}$$$ (то есть, $$$a_{i,j_1}, a_{i,j_2}, \ldots$$$ образуют возрастающую последовательность), то мы можем удалить все строки, кроме $$$i$$$-й, и все столбцы, кроме $$$j_k$$$-х, и оставшаяся матрица будет удовлетворять условию. Если же последовательности не существует, то мы не сможем добиться желаемого. Какие бы столбцы и строки мы ни удаляли, в результате у нас останется некоторая подматрица исходной матрицы с хотя бы одной строкой и хотя бы $$$m - n + 1$$$ столбцами. Раз мы предположили, что возрастающей последовательности длины $$$m - n + 1$$$ нет ни в какой строке матрицы, то строки полученной подматрицы не отсортированы, а значит, добиться ответа «Yes» нельзя вне зависимости от наших действий.

Остаётся найти НВП в каждой строке матрицы и проверить, что хотя бы в какой-то строке она имеет длину хотя бы $$$m - n + 1$$$. Поиск НВП — стандартная задача, решить её можно при помощи дерева отрезков, дерева Фенвика или динамического программирования за $$$\mathcal O(m \log m)$$$ для каждой строки.

Итого решение можно реализовать за $$$\mathcal O(nm \log \max(n, m))$$$