Хотя мы уже выходим за пределы чисто математической тематики, и может быть пороты за оффтопик, но замечу, что это не столько математический (и даже не чисто алгоритмический) вопрос, сколько вопрос организации ЭВМ. Есть последовательный доступ к памяти, есть произвольный. Если "полностью произвольный", то есть доступ к любому элементу за одинаковое время, то транспонирование сводится к переобозначению индексов. А при "полностью последовательном", наподобие магнитных лент, требуется сложная схема перестановки, нечто подобное ленточной сортировке (ну и в порядке побаловаться экзотикой - были ещё магнитные барабаны, там шло непрерывное вращение, и для максимально быстрого доступа надо было следующий требуемый элемент, или команду программы, размещать не сразу за предыдущим, а так, чтобы за время обработки предыдущего барабан провернулся к требуемому месту). И для перемножения двух матриц было выгодно потратить время на их реорганизацию, получая нечто вроде "краковского умножения", а потом читать строки (или столбцы, как организовано, скорее столбцы, учитывая, что в ту эпоху был особо популярен Фортран) последовательно, поскольку даже для тех ЭВМ вычислительные операции требовали меньшего времени, чем механическое позиционирование носителя. С появлением дисков проблема ушла, но вернулась с возникновением конвейерной обработки и кэшей памяти. При правильной организации одна из строк находилась в кэше, а вычисления шли с максимальной скоростью. И несмотря на то, что приходится тратить время на транспонирование, в целом получается быстрее. Особенно актуально становится при многопроцессорной обработке, скажем, CUDA. Для квадратной алгоритм тривиален,
Для прямоугольной либо переписыванием в дополнительную память, либо, при нехватке, вспоминаем, что в памяти всё равно одномерный массив, перебираем его индексы, начиная с произвольного, находим в какое место транспонированной переставится данный элемент исходной матрицы, потом, запомнив, что было на этом месте, помещаем исходный элемент на него и ищем, куда надо поместить запомненный и так, пока не замкнётся цикл; затем берём следующий элемент, не участвовавший в перестановках (проще всего использовать битовый массив; но есть и схемы без дополнительной памяти, но с усложнением алгоритма) и опять переставляем по кругу, пока не исчерпаются не участвовавшие в перестановках элементы.
