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\neq 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\neq 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\neq 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