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