操作を逆順に見る。単位行列の行や列を入れ換えていくと、次のことがわかる:
- 行と列の間にによる一対一対応があるという性質は交換で保たれる。（→ 置換行列）
- 任意の二行の交換はある二列の交換と同一操作であり、任意の二列の交換はある二行の交換と同一操作である。
逆に、初期配置からを共通に含む行と列を1対1に対応させることができれば、この対応を1つの置換と考えることができ、互換を繰り返すことによって単位置換（＝単位行列）に戻せる。また、あらゆる置換は高々個の互換の積で表せるので、回以下という制限は問題にならない。結局、やることは次のようにまとまる:
- の二部グラフをつくり、なら行に対応する頂点から列に対応する頂点に辺を張る。
- の最大二部マッチングを求める。が完全マッチングでなければ実行不能である。
- を一つの置換とみなして巡回置換に分解し、さらに互換に分解する。互換に従って行の交換を行う。
