= Solution
To invert the <Burrows-Wheeler transform>, begin with six empty rows. At every iteration prepend the supplied last-column characters in their fixed row order, then sort the resulting rows in <lexicographic order>. After $k$ iterations the rows contain the length-$k$ prefixes of the sorted <cyclic rotations>. For example, the first two iterations give
$$
\begin{aligned}
T_1&=(\texttt{\char36{}},\texttt{B},\texttt{C},\texttt{E},\texttt{M},\texttt{X}),\\
T_2&=(\texttt{\char36{}M},\texttt{BE},\texttt{CB},\texttt{EX},\texttt{MC},\texttt{X\char36{}}).
\end{aligned}
$$
Each iteration works because sorting the preceding character together with the already reconstructed prefix restores the ordering of the next-longer prefixes. Six iterations give the completed <matrix>
$$
B=\begin{pmatrix}
\char36{}&M&C&B&E&X\\
B&E&X&\char36{}&M&C\\
C&B&E&X&\char36{}&M\\
E&X&\char36{}&M&C&B\\
M&C&B&E&X&\char36{}\\
X&\char36{}&M&C&B&E
\end{pmatrix}.
$$
The original linear string is the unique row ending in the terminator, hence
$$
\boxed{S_2=\texttt{MCBEX\char36{}}}.
$$
As a check, the reconstructed <matrix>'s final column is precisely the supplied <Burrows-Wheeler transform>.
Back to article page
