Podmacierz
-
mol_ksiazkowy
- Użytkownik
- Posty: 13538
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3436 razy
- Pomógł: 812 razy
Podmacierz
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}\)
-
arek1357
Re: Podmacierz
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ść...
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ść...