i≤k<ji\le k<ji≤k<j で、aija_{ij}aij と ajia_{ji}aji がともに零なら、列 iii と jjj の交換で、既存の kkk 個に加えて位置 jjj に対角零が生じ、 kkk の最大性に反する。従って aij+aji≥1a_{ij}+a_{ji}\ge1aij+aji≥1。k(n−k)k(n-k)k(n−k) 個の組について足し合わせると Y≥k(n−k)Y\ge k(n-k)Y≥k(n−k)。