Gegeven is een nxm matrix. De rijen en de kolommen van deze matrix bevatten uitsluitend natuurlijke getallen die groter dan 1 zijn.
Op deze matrix kan je twee operaties toegepassen:
1. een hele rij met 2 vermenigvuldigen 2. een hele kolom met 1 verminderen
Deze operaties kunnen in een willekeurige volgorde en een willekeurig aantal keer na elkaar uitgevoerd worden.
Wie kan mij een bewijs geven dat alle getallen in de matrix tot 0 gereduceerd kunnen worden, onafhankelijk van de oorspronkelijke matrix.
Hartelijk dank voor de hulp.
Theo L
Student universiteit - woensdag 8 oktober 2003
Antwoord
Hoi,
Dit is een prachtige vraag om deductief wiskundig te denken. Divide et Impera (verdeel en heers)!
We noemen de bewerking waarbij en de i-de rij met 2 vermenigvuldigen Vi. De bewerking waarbij we 1 aftrekken van alle elementen van de j-de kolom noemen we Aj.
We hebben een nxm matrix: m kolommen van n elementen. Als we de j-de kolom helemaal 0 krijgen, dan hebben opeenvolgende V bewerkingen op eender welke rij of A bewerkingen op andere kolommen dan de j-de geen invloed: de j-de kolom blijft 0. Dit betekent dat we de nxm matrix kolom per kolom kunnen reduceren, bijvoorbeeld te beginnen met de eerste.
We onderzoeken nu hoe we een kolomvector kunnen reduceren tot 0-elementen. Ook hier proberen we het n-dimensionale probleem te herleiden tot een 2-dimensionaal probleem. We nemen een willekeurige 2-kolomvector [a b] met a en b beiden natuurlijk en verschillend van 0. Als a=b, dan kunnen we met a A-bewerkingen deze vector tot 0 reduceren. In het andere geval kunnen we zonder afbreuk te doen aan de algemeenheid veronderstellen dat ab. Met a-1 A-bewerkingen kunnen we deze vector herleiden tot [1 b-a]. Het geval b-a=1 hadden we al. Voor b-a1 bestaat er een grootste k zodat 2kb-a. Als we k keer een V-bewerking toepassen op de rij waarin 1 staat, dan komen we op [2k b-a]. Als b-a=2k, dan kunnen we reduceren tot 0, anders passen we 2k-1 A-bewerkingen toe en krijgen [1 b-a-2k] waarbij 1b-a-2k(b-a)/2b-a.
De kolomvector [1 1] is reduceerbaar tot [0 0]. Als we alle vectoren [1 s] kunnen reduceren voor st, dan kunnen we met bovenstaande procedure dus ook vector [1 t+1] reduceren. Per inductie hebben we dus bewezen dat alle kolomvectoren [1 t] reduceerbaar zijn en daarmee alle kolomvectoren [a b].
Bemerk dat de laatste stap voor de finale reductie tot een 0-vector telkens een vector is met gelijke elementen. Om een n-kolomvector te reduceren, maken we eerst 2 elementen gelijk. Dan passen we dezelfde procedure toe op de elementen die al gelijk zijn en een 3de element. Alle elementen die al gelijk zijn, spelen dan de rol van a, het nieuw toegevoegde element de rol van b. Zo voegen we telkens een element toe en maken uiteindelijk alle elementen gelijk. Daarna passen we zoveel A-bewerkingen toe om de hele n-dimensionale kolomvector in één keer tot 0 te reduceren.
Hiermee is je stelling bewezen en heb je zelfs een constructie om het te doen.
Leuke uitbreiding: hoe doe je het in zo min mogelijk stappen? Wat is de algoritmische complexiteit? Bemerk dat die 2 in de V-bewerkingen niet helemaal willekeurig is. Zie je waar het hapert als we met 3 zouden vermenigvuldigen?
b. Met a-1 A-bewerkingen kunnen we deze vector herleiden tot [1 b-a]. Het geval b-a=1 hadden we al. Voor b-a
1 bestaat er een grootste k zodat 2k
b-a. Als we k keer een V-bewerking toepassen op de rij waarin 1 staat, dan komen we op [2k b-a]. Als b-a=2k, dan kunnen we reduceren tot 0, anders passen we 2k-1 A-bewerkingen toe en krijgen [1 b-a-2k] waarbij 1