حکم را در حالت کلی برای ماتریسهای $n \times n$ به کمک استقراء ثابت می کنیم:
اولن توجه کنید که چون درایه ها غیر منفی هستند اگر $A$ ماتریسی $ \ (n+1) \times (n+1)$با شرای مساله باشد و ماتریس $A'$ از حذف سطر آخر و ستون آخر ماریس $A$ به دست بیاید باز هم $A'$ ماتریسی با شرایط مساله است.(چرا؟).اگر برای ماتریس $n \times n$ با شرایط مساله حداکثر تعداد $1$ ها را با $ \phi (n)$ نشان دهیم داریم:
$ \phi (1)=0, \phi (2)=1$(چرا؟)
حالا فرض کنید که حکم برای ماتریس مدنظر $n \times n$ دلخواه درست باشد.ماتریس مد نظر $A$ که $(n+1) \times (n+1)$ است را در نظر بگیرید:
$ \forall 1 \leq i,j \leq n+1:$
$ 0= \sum {k=1}^{n+1}a{ik}a_{kj} $
$ =\sum {k=1}^n a{ik}a_{kj}+a_{i(n+1)}a_{(n+1)j} $
$=0+a_{i(n+1)}a_{(n+1)j} $
$=a_{i(n+1)}a_{(n+1)j}$
$ \Rightarrow a_{i(n+1)}=0 \vee a_{(n+1)j}=0$
حالا با توجه به اینکه $a_{(n+1) \times (n+1)}=0$ بدترین حالت این است که $n$ تا از درایه های بالا که همان درایه های سطر و ستون $n+1$ ام اند $1$ باشند.(چرا؟) لذا داریم:
$ \phi(n+1) \leq \phi (n)+n$
$ \Rightarrow \phi (n+1) \leq \phi (2)+2+3+...+n=1+2+3+...+n$
$ \Rightarrow \phi (n) \leq 1+2+...+(n-1)= \frac{1}{2} n(n-1)$
$ \Rightarrow \phi (10) \leq \frac{10.9}{4} =45$
$ \Box $
