szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 3 gru 2016, o 19:13 
Użytkownik

Posty: 5620
Lokalizacja: Kraków
Na ile sposobów można skonstruować macierz n \times n o elementach równych \pm 1 i taką, że iloczyny każdego wiersza jak i kolumny są równe -1 ?
Kiedy jest to możliwe ?
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2016, o 18:45 
Użytkownik

Posty: 306
Lokalizacja: Warszawa
Najpierw prosta obserwacja.
Niech B=[b_{ij}]_{1\leq i,j\leq n} będzie macierzą spełniającą warunki zadania. Zauważmy, że
b_{in}=(-1)\cdot \left(b_{i1}\cdot b_{i2}\cdot ...\cdot b_{in-1}\right)
dla 1\leq i\leq n-1 oraz
b_{nj}=(-1)\cdot \left(b_{1j}\cdot b_{2j}\cdot...\cdot b_{n-1j}\right)
dla 1\leq j\leq n-1. Ponadto
b_{nn}=(-1)\cdot (-1)^{n-1}\cdot \prod_{1\leq i,j\leq n-1}b_{ij}



Niech X_{n-1} będzie zbiorem macierzy (n-1)\times (n-1) o wszystkich wyrazach równych \pm 1. Niech Y_{n} będzie zbiorem macierzy n\times n spełniających tezę zadania. Teraz zadajemy funkcje
f:Y_n\rightarrow X_{n-1} oraz g:X_{n-1}\rightarrow Y_n
Mamy
f(B)=[b_{ij}]_{1\leq i,j\leq n-1}
gdzie B=[b_{ij}]_{1\leq i,j\leq n} oraz
g(A)=[b_{ij}]_{1\leq i,j\leq n}
gdzie
b_{ij}=\begin{cases}a_{ij} &\mbox{ dla }1\leq i,j\leq n-1\\
(-1)\cdot \left(a_{i1}\cdot a_{i2}\cdot ...\cdot a_{in-1}\right) &\mbox{ dla }1\leq i\leq n-1\\
(-1)\cdot \left(a_{1j}\cdot a_{2j}\cdot...\cdot a_{n-1j}\right) &\mbox{ dla }1\leq j\leq n-1\\
(-1)\cdot (-1)^{n-1}\cdot \prod_{1\leq i,j\leq n-1}a_{ij} &\mbox{ dla } i=j=n
\end{cases}
i oczywiście A=[a_{ij}]_{1\leq i,j\leq n-1}.
Na mocy obserwacji widzimy, że f\cdot g=1_{X_{n-1}} oraz g\cdot f=1_{Y_n}. Stąd zbiory Y_n oraz X_{n-1} są równoliczne. Oznacza to, że
|Y_n|=|X_{n-1}|=2^{(n-1)^2}
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2016, o 21:06 
Użytkownik

Posty: 5620
Lokalizacja: Kraków
ale rozwiązanie nie zawsze istnieje; np. gdy n=1 \ m=2...
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2016, o 21:09 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Ja mam łatwiejszy sposób chyba:

Niech będzie macierz spełniająca warunki nasze:


A=\left[\begin{array}{cccc}a_{1,1}&a_{1,2}&...&a_{1,n}\\a_{2,1}&a_{2,2}&...&a_{2,n}\\......&......&....&.....\\a_{n1}&a_{n,2}&...&a_{n,n}\end{array}\right]

Układ równań napiszmy:

Najpierw po wierszach:

a_{1,1} \cdot a_{1,2} \cdot ... \cdot a_{1,n}=-1

a_{2,1} \cdot a_{2,2} \cdot ... \cdot a_{2,n}=-1

...................................................................................

a_{n,1} \cdot a_{n,2} \cdot ... \cdot a_{n,n}=-1

A teraz po kolumnach:

a_{1,1} \cdot a_{2,1} \cdot ... \cdot a_{n,1}=-1

a_{1,2} \cdot a_{2,2} \cdot ... \cdot a_{n,2}=-1

.................................................................................

a_{1,n} \cdot a_{2,n} \cdot ... \cdot a_{n,n}=-1

Z ostatnich \nrównań (kolumnowych) wyliczmy:

a_{1n}, a_{2,n-1}, a_{3,n-2},...,a_{n,1}

I wstawmy je do pierwszych \ n równań nastąpi redukcja ilości zmiennych
o \ n, i otrzymamy:


a_{1,1} \cdot a_{1,2} \cdot ... \cdot a_{1,n-1}=a_{2,n} \cdot a_{3,n} \cdot ... \cdot a_{n,n}

a_{2,1} \cdot a_{2,2} \cdot ... \cdot a_{2,n-2} \cdot a_{2,n}= a_{1,n-1} \cdot a_{3,n-1} \cdot  ... \cdot a_{n,n-1}

...........................................................................................................................

a_{n,2} \cdot a_{n,3} \cdot ...  \cdot a_{n,n}= a_{1,1} \cdot a_{2,1} \cdot  ... \cdot a_{n-1,1}

I teraz widzimy, że mamy układ \ n równań o \ n-1 zmiennych

Zauważmy, że zmienne po lewych stronach tych równań i po prawych są takie same,

A ponieważ zmienne po lewej stronie tworzą kolejki , kolejek jest \n a zmiennych w kolejce jest n-1 to możemy wyrzucić jedno równanie bo całkowicie jego zmienne pokrywają się z pozostałymi równaniami.

Zostanie nam więc \ n-1 równań, oraz zmiennych niezależnych:

n^2-n-(n-1) - w nawiasie mamy te ostatnio odrzucone

czyli:

n^2-n-(n-1)-n^2-2n+1=(n-1)^2

Czyli zmiennych niezależnych jest:

(n-1)^2

A co za tym idzie rozwiązań równania jest:

2^{(n-1)^2}

Bo pod każdą zmienną można podstawić:

\pm 1

Ja to najpierw robiłem na małych przykładach i z obserwacji mi to wyszło...

Oczywiście robiłem to dla macierzy:

n \times n




Cytuj:
ale rozwiązanie nie zawsze istnieje; np. gdy n=1 \ m=2...


Do jakiego wątku to ostatnie było zdanie?
Góra
Mężczyzna Offline
PostNapisane: 4 gru 2016, o 23:01 
Użytkownik

Posty: 306
Lokalizacja: Warszawa
mol_ksiazkowy napisał(a):
Na ile sposobów można skonstruować macierz n \times n o elementach równych \pm 1 i taką, że iloczyny każdego wiersza jak i kolumny są równe -1 ?
Kiedy jest to możliwe ?


Treści zadania sugeruje, że chodzi o macierze kwadratowe.

mol_ksiazkowy napisał(a):
ale rozwiązanie nie zawsze istnieje; np. gdy n=1 \ m=2...


Teraz po prostu mamy nowe zadanie:
Dla jakich n i m istnieją macierze n\times m o wyrazach \pm 1 takie, że iloczyn wyrazów w każdym wierszu i w każdej kolumnie wynosi (-1)? Ile jest takich macierzy, jeśli ich zbiór jest niepusty?

Łatwo pokazać, że warunek konieczny to:
n\equiv m\,(\mathrm{mod}\,2)
Jest to też warunek dostateczny.
Nie sprawdziłem co prawda tego jakoś bardzo dokładnie, ale na pierwszy rzut moje rozwiązanie działa też dla macierzy prostokątnych n\times m dokładnie przy założeniu, że
(-1)^{n-1}=(-1)^{m-1}
czyli przy warunku 2|n-m .
Z tego wynika, że takich macierzy jest 2^{(n-1)(m-1)}

W dodatku wydaje mi się i miło mi to przyznać, że dosyć żmudne, ale proste w swoim pomyśle, rozwiązanie podane przez arek1357 jest po pierwsze poprawne, a po drugie też się uogólnia na przypadek macierzy prostokątnych. Właściwie to w moim odczuciu podane przeze mnie rozwiązanie to trochę estetyczniej zapisane rozwiązanie arek1357. Mam nadzieję arek1357, że się z powodu tego komentarza nie obrazisz:).
Swoją drogą nie wiem jak deklinować loginy niektórych użytkowników forum. Przepraszam.
Góra
Mężczyzna Offline
PostNapisane: 5 gru 2016, o 08:49 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Czemu mam się obrazić jasne jest że Twoje rozwiązanie jest bardziej zwięzłe i bardziej naukowe, ale może moje bardziej czytelne dla początkujących jak pisałem sprawdzałem to najpierw dla macierzy
2 \times 2, 3 \times 3, 4 \times 4 i fajnie się zapisywało i postanowiłem to indukcyjnie uogólnić...

Podbijam temat i dla macierzy n \times n - dokładam jeszcze iloczyny po przekątnych równe:

-1

Ile wtedy wyjdzie wyników.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Iloczyny w macierzach  beavisboss  7
 Możliwe iloczyny.  eloziom  1
 działania na macierzach i wyznacznikach  nwa2pac  0
 Sumy i iloczyny zbiorów  Ewa 20  0
 Macierze: działania na macierzach  Rainny  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl