Będziemy zaznaczać liczby w kilku krokach. W kroku 1. w każdym wierszu zaznaczamy najmniejszą liczbę. Jeśli wówczas w każdej kolumnie jest zaznaczona dokładnie jedna liczba, to kończymy. W przeciwnym razie, w kolejnym kroku w każdej kolumnie, w której znajdują się co najmniej dwie zaznaczone liczby, odznaczamy je wszystkie (czyli usuwamy zaznaczenie) oprócz największej. W ten sposób powstały wiersze, w których nie zaznaczono żadnej liczby – nazwijmy je wierszami wolnymi. Następnie zaznaczamy w każdym wolnym wierszu najmniejszą liczbę spośród tych, które nigdy wcześniej nie były zaznaczane ani odznaczane. W następnym kroku znowu patrzymy na kolumny, w których są zaznaczone co najmniej dwie liczby, i powtarzamy opisane rozumowanie, aż uzyskamy odpowiednie zaznaczenie lub nie będzie można wykonać kolejnego kroku.

Każdy wiersz może stać się wolny co najwyżej  razy, więc wykonamy co najwyżej  kroków. Po ostatnim kroku w każdej kolumnie będzie zaznaczony dokładnie jeden element.

Dla ustalenia uwagi przyjmijmy, że w tej procedurze zaznaczono elementy z przekątnej (możemy tak założyć, ewentualnie przestawiając kolumny). Spójrzmy na -ty wiersz. Jeśli  dla pewnego  to znaczy, że w pewnym kroku liczba  była odznaczona, a zatem