Matematyka.pl

Udowodnić, że permanent macierzy kwadratowej \(\displaystyle{ n \times n}\) zero-jedynkowej jest równy zero wtedy, i tylko wtedy, gdy ma ona podmacierz zerową \(\displaystyle{ m \times k}\) przy czym \(\displaystyle{ m+k=n+1}\)

Może niezbyt zgrabnie:

Wystarczy tak przetasować wiersze i kolumny macierzy wyjściowej, żeby podmacierz zaczynała się od początku, a potem rozwijać permanent wzdłuż pierwszego wiersza , do \(\displaystyle{ m}\) tej kolumny ze zrozumiałych względów wszystko się wyzeruje, a od \(\displaystyle{ m+1}\) kolumny do \(\displaystyle{ n}\) tej kolumny też się wyzeruje bo permutacje nie zmieszczą się (żadna z nich) w prostokącie: \(\displaystyle{ k \times (n-m)}\) każda taka permutacja musi wskoczyć do początkowej macierzy zerowej choć raz ponieważ jakby było inaczej to powinno być:

\(\displaystyle{ n-m \ge k}\)

\(\displaystyle{ n \ge m+k=n+1}\)

Czyli sprzeczność...