Fredholm-alternatíva

A Fredholm-alternatíva a lineáris egyenlőségrendszerek megoldhatóságáról szól, és bizonyítékot szolgáltat arra az esetre, ha az egyenletrendszer megoldhatatlan.

A tétel

Az $Ax=b$ primál rendszernek akkor és csak akkor van megoldása, ha nincs y duális megoldás, $yA=0$ $yb\ne 0$. Azaz a b vektor vagy benne van az A altérben, vagy elválasztható tőle egy y normálisú, az origón átmenő hipersíkkal. Ekkor a hipersík tartalmazza az alteret, de a vektort nem.

A bizonyítás teljes indukcióval működik. Ha az A mátrixnak egy sora van, akkor könnyű a bizonyítás. Ha nullmátrixról van szó, akkor szintén egyszerű. Feltehető tehát, hogy A nem nullmátrix, és legalább két sora van.

Ekkor sor-és oszlopcserékkel elérhető, hogy a_1,1 nem nulla. Az egyenletek nem nulla számmal való szorzása és az egyik egyenlet egy másikhoz való hozzáadása nem változtatja meg sem a primál, sem a duál probléma megoldhatóságát. Így elvégezhető a Gauss-elimináció egy lépése.

Az első egyenletet a_1,1-gyel leosztva feltehető, hogy a mátrix első oszlopában az első elem 1, és a többi nulla. Töröljük el most az első sort. Ennek a mátrixnak kevesebb sora van, ezért alkalmazható rá az indukciós feltevés: $A^1{x}^1=b^1$ vagy duálisa megoldható.

Ha van x¹, akkor az első koordináta választható úgy, hogy az első egyenlet is teljesüljön. Ha az y¹ duális megoldás létezik, akkor elé nullát írva az eredeti egy duál megoldását kapjuk. Tehát a primál vagy a duál feladat megoldható.

Mindkettő nem oldható meg; különben $0=yAx=yb\ne 0$ lenne, ami ellentmondás.

Jellemzés

A tétel fenti alakjában nem látszik, hogy mégis mi áll a megoldhatóság hátterében. Egy nem közvetlen bizonyítás erre is választ ad.

Tétel: A következők ekvivalensek:

1. az $Ax=b$ rendszernek van megoldása
2. az A mátrix rangja nem változik attól, hogy új oszlopként hozzávesszük a b vektort
3. nincs y, amire $yA=0$ $yb\ne 0$

Bizonyítás:

2.→1. Vegyük A rangnyi oszlopát. A kibővített mátrix rangja ugyanekkora, ezért b lineárisan függ ezektől az oszlopoktól, így A oszlopaitól is.

1.→3. Legyen x,y olyan, hogy $Ax=b$ és $yA=0$. Ezekből kapjuk, hogy $yAx=yb=0$.

A nehéz irány a 3.→2.:

Tegyük fel indirekt, hogy a kibővített mátrix rangja nagyobb. Válasszuk ki ennek a lehető legtöbb független sorát, és legyen $[A_1,b_1]$ az általuk alkotott részmátrix. A₁ sorai lineárisan összefüggnek, hiszen A -nak nincs ennyi lineárisan független sora. Van tehát egy y₁ vektor, hogy $y_1{A}_1=0$, de az $[A_1,b_1]$ mátrixszal szorozva az eredmény nem lesz nulla, hiszen $[A_1,b_1]$ sorai lineárisan függetlenek. Ezért $y_1{b}_1$ sem lesz egyenlő nullával. Az y₁ vektort nulla koordinátákkal kiegészítve egy olyan y vektort kapunk, ami ellentmond a 3. feltételnek.

Források

• http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf