Matrix transposition in time $O(N\log\min(m,k))$ on a multitape Turing machine

Theorem IntMul.TM.transpose. There exist a deterministic multitape Turing machine $M$ and a real constant $c > 0$ (chosen after $M$; independent of everything below) such that for all $m, k, \ell \in \mathbb N$ with $m \ge 1$, $k \ge 1$, $\ell \ge 1$ and every $m \times k$ matrix $A = (A_{i,j})_{0 \le i < m,\ 0 \le j < k}$ whose entries are bit strings all of length exactly $\ell$, the following holds. (Here $k$ is a matrix dimension, unrelated to the machine's number of tapes.)

Define, for any $m' \times k'$ matrix $B$ of bit strings, the word over $\{0,1,\#\}$

i.e. row-major: entries within a row joined by a single $\#$, rows joined by a double $\#\#$, nothing at the ends. Let $N = |\mathrm{enc}_{m,k}(A)| = mk\ell + mk + m - 2$. Then there is $t \in \mathbb N$ with

such that $M$, started on the word $\mathrm{enc}_{m,k}(A)$, is after exactly $t$ steps in $q_{\mathrm{halt}}$ with output tape $\triangleright\, \mathrm{enc}_{k,m}(A^{\mathsf T})\, \square\square\cdots$, where $A^{\mathsf T}$ is the $k \times m$ matrix with $(A^{\mathsf T})_{j,i} = A_{i,j}$ (so the output lists the columns of $A$ as rows, again single $\#$ within and $\#\#$ between). $\lceil \log_2 \cdot \rceil$ is the integer ceiling-log with $\lceil \log_2 1 \rceil = 0$.

Started on a word $w$ over $\{0,1,\#\}$ means: state $q_{\mathrm{start}}$, tape $0$ holds $\triangleright\, w\, \square\square\cdots$ (letters as $\mathtt 0/\mathtt 1/\#$), every other tape holds $\triangleright\square\square\cdots$, all heads at cell $0$. Machine model. A machine $M$ has a finite alphabet containing pairwise distinct symbols $\square$ (blank), $\triangleright$ (start marker), $\mathtt 0, \mathtt 1, \#$ plus possibly further symbols; a finite state set with $q_{\mathrm{start}} \ne q_{\mathrm{halt}}$; a fixed number $k_M \ge 2$ of tapes with cells $0,1,2,\dots$ (tape $0$ = read-only input tape, tape $1$ = output tape, others work tapes); a transition function acting simultaneously on all tapes (write one symbol and move $\leftarrow,-,\rightarrow$ per tape), which never erases or writes $\triangleright$ except by rewriting it in place, never moves left from $\triangleright$, and leaves the configuration fixed in $q_{\mathrm{halt}}$. "Halts with output $v$ at step $t$" means: after exactly $t$ steps from the initial configuration the state is $q_{\mathrm{halt}}$ and the entire output tape is $\triangleright\, v\, \square\square\cdots$ (cells $1..|v|$ hold $v$, every later cell blank); work tapes, input tape and head positions are unconstrained. Since $q_{\mathrm{halt}}$ is a fixed point, "for some $t \le T$" is the same as "halts within $T$ steps".

Quantifiers and edge cases. Empty matrices ($m = 0$ or $k = 0$) and empty entries ($\ell = 0$) are excluded by hypothesis. With $\ell \ge 1$ the input word determines $m$, $k$ and $A$ (entries are nonempty, so $\#\#$ occurs exactly at row boundaries), so the required output is a well-defined function of the input. Degenerate shapes: $m = k = 1$ requires output = input within $c(\ell+1)$ steps; $m = 1$ (a single row $e_0\#\cdots\#e_{k-1}$) requires output $e_0\#\#e_1\#\#\cdots\#\#e_{k-1}$ within $c(N+1)$ steps, and symmetrically for $k = 1$. The machine is not told $m, k, \ell$. The log factor uses $\min(m,k)$; one constant $c$ serves all $m, k, \ell$ (no threshold). Words not of this form are unconstrained.