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 ${\displaystyle Ax=b}$ primál rendszernek akkor és csak akkor van megoldása, ha nincs y duális megoldás, ${\displaystyle yA=0}$ ${\displaystyle 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: ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle yA=0}$ ${\displaystyle 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 ${\displaystyle Ax=b}$ és ${\displaystyle yA=0}$. Ezekből kapjuk, hogy ${\displaystyle 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 ${\displaystyle [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 ${\displaystyle y_{1}A_{1}=0}$, de az ${\displaystyle [A_{1},b_{1}]}$ mátrixszal szorozva az eredmény nem lesz nulla, hiszen ${\displaystyle [A_{1},b_{1}]}$ sorai lineárisan függetlenek. Ezért ${\displaystyle 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