Каюсь, ошибся. Копирование действительно всегда будет O(NxM). А вот транспонировать действительно в зависимости от внутренней структуры матрицы можно и за O(1).
Ну транспонировать (поменять строки со столбцами) - дело нехитрое. А вот если напр матрица с масштабами по осям - придется инвертировать Гауссом. В общем случае затратами на копирование разумно пренебречь.