Matriser og likningssystemer

Lineære likningssystemer og Gauss-eliminasjon

En lineær likning i variablene $x_1,x_2,\dots ,x_n$ har formen $a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=b$ — ingen produkter av variabler, ingen kvadrater, bare en sum av konstant ganger variabel. Et likningssystem er flere slike likninger samtidig, og løsningsmengden er punktene som tilfredsstiller alle på én gang.

gauss-eliminasjon er den systematiske metoden for å finne løsningsmengden. Skriv systemet som en ƒutvidet matrise — koeffisientene til venstre, høyresiden til høyre, adskilt med en loddrett strek — og bruk radoperasjoner (bytt to rader, skaler en rad, legg et multiplum av én rad til en annen) til matrisen står på trappeform. Hver rad i trappeform har sin ledende ener lenger til høyre enn raden over.

De ledende enerne kalles pivoter og frie variabler. En kolonne uten pivot gir en fri variabel — du kan velge verdien fritt, og resten av løsningen uttrykkes i termer av den. Antall pivoter er det samme som rangen til matrisen, og rangen avgjør alt om hvor mange løsninger systemet har.

Se det i praksis: systemet $x+2y-z=3$, $2x+3y+z=10$, $-x-y+2z=-2$ har utvidet matrise $\left(\begin{array}{cccc}1& 2& -1& 3\\ 2& 3& 1& 10\\ -1& -1& 2& -2\end{array}\right)$. Trekk to ganger første rad fra andre rad, og legg første rad til tredje: $\left(\begin{array}{cccc}1& 2& -1& 3\\ 0& -1& 3& 4\\ 0& 1& 1& 1\end{array}\right)$. Legg deretter andre rad til tredje: $\left(\begin{array}{cccc}1& 2& -1& 3\\ 0& -1& 3& 4\\ 0& 0& 4& 5\end{array}\right)$. Nå står matrisen på trappeform med tre pivoter i tre kolonner, så systemet har entydig løsning — du finner $z=5/4$ direkte fra siste rad, og resten ved baklengs innsetting.

Tre typer løsninger — og hva rangen forteller

antall løsninger et system kan ha, er alltid ett av tre: entydig løsning, uendelig mange løsninger, eller ingen løsning i det hele tatt.

Entydig løsning oppstår når rangen til koeffisientmatrisen er lik antall ukjente — hver kolonne får en pivot, ingen frie variabler, én kombinasjon av verdier virker. Geometrisk er løsningsmengden ett enkelt punkt, dimensjon 0.

Er det færre pivoter enn ukjente, blir minst én variabel fri, og løsningsmengden får dimensjon lik antall frie variabler. Med én fri variabel $t$ skriver du løsningen som en partikulærløsning pluss $t$ ganger en retningsvektor. Et konkret eksempel: et system med tre ukjente og rang 2 kan ha generell løsning $(x,y,z)=(-\frac{2}{3}t,\frac{1}{3}t,t)$ — en hel linje av løsninger, dimensjon 1, parametrisert av $t$.

Ingen løsning oppstår når trappeformen inneholder en rad som sier $0=c$ for en konstant $c\ne 0$ — en selvmotsigelse. Det skjer når rangen til den utvidede matrisen er større enn rangen til koeffisientmatrisen alene: høyresiden peker i en retning venstresiden ikke kan nå. Det er nettopp dette ƒrank-kriteriet formaliserer.

Homogene og inhomogene systemer

Et system er inhomogent når minst ett tall på høyresiden er ulik null, og homogent når hele høyresiden er nullvektoren. Denne forskjellen avgjør hvilke av de tre løsningstypene som i det hele tatt er mulige.

homogent og inhomogent system: et homogent system har alltid minst én løsning, nemlig $\vec{x}=\vec{0}$ — den trivielle løsningen. Sett alle ukjente til null, og alle likningene blir $0=0$. Spørsmålet for et homogent system er derfor aldri om det finnes en løsning, bare om den trivielle løsningen er den eneste. Er rangen lik antall ukjente, er den det; er rangen mindre, finnes uendelig mange ikke-trivielle løsninger i tillegg.

Et inhomogent system mangler denne garantien — det kan fint ha ingen løsning, som eksempelet over viser. Klassifiseringen går altså i to steg: sjekk først om høyresiden er null, og bruk deretter rangen til å avgjøre entydig, uendelig mange, eller — kun for inhomogene systemer — ingen løsning.

Sammenlign to systemer med akkurat samme koeffisientmatrise: $x+y=0$, $2x+2y=0$ (homogent) mot $x+y=1$, $2x+2y=3$ (inhomogent). Det homogene har uendelig mange løsninger — hele linjen $y=-x$ — fordi rangen er 1 og det er to ukjente. Det inhomogene har ingen løsning i det hele tatt: ganger du første likning med 2, får du $2x+2y=2$, som strider mot $2x+2y=3$. Samme venstreside, helt forskjellig løsningsmengde — det er høyresiden, ikke koeffisientene alene, som avgjør type løsning for et inhomogent system.

Matriseregning og to veier til invers matrise

matrisemultiplikasjon av $A$ (størrelse $m\times n$) og $B$ (størrelse $n\times p$) gir en $m\times p$-matrise der hvert element er et skalarprodukt: ƒmatrisemultiplikasjon. Legg merke til at $AB$ og $BA$ generelt er forskjellige matriser — matrisemultiplikasjon er ikke kommutativ, selv når begge produktene er definert.

Å finne den inverse matrisen $A^{-1}$ — matrisen som oppfyller $A{A}^{-1}=A^{-1}A=I$ — kan gjøres på to måter. Den ene bruker Gauss-eliminasjon direkte: sett opp $A$ og identitetsmatrisen $I$ side om side som $[A\mid I]$, og radreduser hele blokken til venstre halvdel blir $I$. Da har høyre halvdel blitt $A^{-1}$ — dette er matriseinvers via gauss-eliminasjon, og metoden virker for alle inverterbare $n\times n$-matriser, ikke bare $2\times 2$.

Den andre veien går via determinanten. For en $2\times 2$-matrise $A=\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)$ finnes en eksplisitt snarvei, ƒ2×2-invers (eksplisitt formel): bytt om diagonalelementene, skift fortegn på de to andre, og skaler med $1/\det A$. Formelen krasjer akkurat når $\det A=0$ — samme betingelse som når matrisen mangler invers i utgangspunktet.

Et lite eksempel: for $A=\left(\begin{array}{cc}2& 1\\ 1& 1\end{array}\right)$ er $\det A=2\cdot 1-1\cdot 1=1$, og den eksplisitte formelen gir $A^{-1}=\left(\begin{array}{cc}1& -1\\ -1& 2\end{array}\right)$. Radreduserer du $[A\mid I]$ i stedet, lander du på nøyaktig samme høyre halvdel — de to metodene må stemme overens, siden begge finner den ene matrisen som oppfyller $A{A}^{-1}=I$.

Determinanter: kofaktorer, adjungert matrise og Cramers regel

determinanten til en kvadratisk matrise er et enkelt tall som blant annet forteller om matrisen er inverterbar ($\det A\ne 0$) og hvordan matrisen skalerer volum. For $2\times 2$ er formelen ƒ2×2-determinant; for $3\times 3$ gir Sarrus' regel ƒ3×3-determinant (sarrus) — summer produktene langs de tre "ned"-diagonalene, trekk fra produktene langs de tre "opp"-diagonalene.

For større matriser bruker du kofaktor-utvikling. En kofaktor $C_{ij}$ er determinanten til matrisen du får ved å stryke rad $i$ og kolonne $j$ fra $A$, med fortegn $(-1{)}^{i+j}$ foran — fortegnene følger et sjakkbrett-mønster, $+,-,+,-,\dots$, som starter med $+$ øverst til venstre. Determinanten regnes ut ved å utvikle langs en hvilken som helst rad eller kolonne og summere element ganger tilhørende kofaktor.

Setter du alle kofaktorene inn i en matrise og transponerer den, får du den adjungert matrisen $\mathrm{adj}(A)$. Den henger sammen med inversen gjennom ƒinvers via adjungert, og med løsningen av likningssystemer gjennom cramers regel: løsningen $x_i$ til $A\vec{x}=\vec{b}$ kan skrives som en kvotient av to determinanter, $x_i=\det (A_i)/\det (A)$, der $A_i$ er $A$ med kolonne $i$ byttet ut med $\vec{b}$.

Determinanten har også en volumtolkning: $|\det A|$ er volumet av parallellepipedet utspent av radene (eller kolonnene) til $A$. Fortegnet forteller om transformasjonen bevarer eller snur orienteringen.

Et regneeksempel med kofaktor-utvikling: $A=\left(\begin{array}{ccc}1& 2& 0\\ 0& 1& 3\\ 2& 0& 1\end{array}\right)$. Utvikler du langs første rad, blir $\det A=1\cdot (1\cdot 1-3\cdot 0)-2\cdot (0\cdot 1-3\cdot 2)+0\cdot (\dots )=1\cdot 1-2\cdot (-6)=1+12=13$. Skal du løse $A\vec{x}=\vec{b}$ for en gitt $\vec{b}$, sier Cramers regel at $x_1=\det (A_1)/13$, der $A_1$ er $A$ med første kolonne byttet ut med $\vec{b}$ — samme struktur som formelen over, bare med tall satt inn. Cramers regel er elegant for hånd-regning på små systemer, men i praksis vokser antall determinanter du må regne ut raskt med $n$, så for store systemer er Gauss-eliminasjon fortsatt den effektive metoden — Cramer gir deg innsikt, ikke fart.

To korte, nyttige bevis følger direkte av dette. For to inverterbare matriser $A,B$ er $(AB{)}^{-1}=B^{-1}{A}^{-1}$ — sjekk at $(B^{-1}{A}^{-1})(AB)=B^{-1}(A^{-1}A)B=B^{-1}IB=I$, og tilsvarende fra venstre. Kombinert med ƒmultiplikasjon av determinanter følger $\det (A^{-1})=1/\det (A)$, siden $\det (A)\det (A^{-1})=\det (A{A}^{-1})=\det (I)=1$. Samme regel gir, ved induksjon på $n$, at $\det (A^n)=(\det A{)}^n$: sant for $n=1$, og hvis det holder for $n-1$ er $\det (A^n)=\det (A\cdot A^{n-1})=\det (A)\det (A^{n-1})=\det (A)\cdot (\det A{)}^{n-1}=(\det A{)}^n$.

Egenverdier og egenvektorer

En egenvektor til en kvadratisk matrise $A$ er en vektor $\vec{v}$ ulik null som $A$ bare skalerer, ikke dreier: $A\vec{v}=\lambda \vec{v}$ for et tall $\lambda$, egenverdien. Retningen til $\vec{v}$ er altså bevart under transformasjonen — bare lengden, og eventuelt fortegnet, endres.

Egenverdiene finner du fra ƒkarakteristisk polynom: $\det (A-\lambda I)=0$ er en polynomlikning i $\lambda$ av grad $n$ for en $n\times n$-matrise, og har derfor $n$ røtter talt med multiplisitet — noen kan være komplekse, noen kan falle sammen. For hver egenverdi $\lambda$ løser du det homogene systemet $(A-\lambda I)\vec{v}=0$ for å finne egenvektorene; løsningsmengden, inkludert nullvektoren, kalles eigenspacen til $\lambda$, og er alltid minst én-dimensjonal siden $A-\lambda I$ har rang mindre enn $n$ når $\lambda$ er en egenverdi.

Tre eksempler viser bredden i hva grad-$n$-polynomet kan gi. Matrisen $\left(\begin{array}{cc}2& 1\\ 1& 2\end{array}\right)$ har karakteristisk polynom $(2-\lambda {)}^2-1=0$, altså to reelle, distinkte egenverdier $\lambda =1$ og $\lambda =3$, med egenvektorer $(1,-1)$ og $(1,1)$. En rotasjonsmatrise som $\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)$ har derimot ${\lambda }^2+1=0$, med røttene $\lambda =\pm i$ — komplekse egenverdier, fordi en rotasjon på $90°$ ikke lar noen reell retning stå i fred. Og $\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$ har $\lambda =2$ som en dobbel rot av $(2-\lambda {)}^2=0$ — én egenverdi med multiplisitet 2, men bare én uavhengig egenvektor $(1,0)$, siden $A-2I$ har rang 1. Denne siste typen matrise mangler nok egenvektorer til å diagonaliseres.

Diagonalisering og en anvendelse: rever og kaniner

En matrise $A$ er diagonaliserbar matrise hvis du kan skrive $A=PD{P}^{-1}$ (ƒdiagonaliserbarhet) med $D$ diagonal og $P$ invertibel — kolonnene i $P$ er egenvektorer, diagonalen i $D$ de tilhørende egenverdiene. Det er alltid mulig når $A$ har $n$ lineært uavhengige egenvektorer, garantert blant annet av spektralsetningen når $A$ er symmetrisk: da finnes en ortogonal $P$ slik at ƒspektral dekomposisjon, og alle egenverdiene er reelle. Determinanten kan da leses rett av egenverdiene: ƒdeterminant via egenverdier.

Diagonalisering er ikke bare pen algebra — den gjør det billig å regne ut høye potenser av $A$, fordi $D^n$ bare er å opphøye hvert diagonalelement: ƒmatrisepotens via diagonalisering. Det er nøyaktig verktøyet en markov-kjede trenger.

Tenk deg en øy med kaniner og rever. La $x_n$ og $y_n$ være bestandene år $n$, og anta at neste års bestand er en lineær funksjon av dagens, ƒmarkov-overgangslikning, med overgangsmatrisen $M=\left(\begin{array}{cc}0& 1/2\\ 1& 1/2\end{array}\right)$. Egenverdiene til $M$ er ${\lambda }_1=1$ og ${\lambda }_2=-1/2$ — røttene til $\det (M-\lambda I)={\lambda }^2-\frac{1}{2}\lambda -\frac{1}{2}=0$ — med egenvektorer $(1,2)$ og $(1,-1)$. Diagonaliseringen $M=PD{P}^{-1}$ gjør at du kan skrive løsningen i lukket form uten å multiplisere matrisen med seg selv $n$ ganger.

Skriv startbestanden som en kombinasjon av egenvektorene: $(x_0,y_0)=c_1(1,2)+c_2(1,-1)$. Siden ${\lambda }_1=1$ lar $(1,2)$-komponenten stå urørt for hvert steg, mens ${\lambda }_2=-1/2$ krymper $(1,-1)$-komponenten med faktor $-1/2$ per steg, blir tilstanden etter $n$ steg $c_1(1,2)+c_2(-\frac{1}{2}{)}^n(1,-1)$ — altså $x_n=c_1+c_2(-\frac{1}{2}{)}^n$ og $y_n=2c_1-c_2(-\frac{1}{2}{)}^n$.

Med startbestand $(x_0,y_0)=(300,0)$ gir dette $c_1=100$ og $c_2=200$, og løsningen blir $x_n=100+200(-\frac{1}{2}{)}^n$ og $y_n=200-200(-\frac{1}{2}{)}^n$. Siden $(-\frac{1}{2}{)}^n\to 0$ når $n\to \infty$, stabiliserer bestanden seg mot $(100,200)$ uansett hvor den startet — det er egenverdien ${\lambda }_1=1$ som styrer langtidsoppførselen, mens ${\lambda }_2=-1/2$ bare bidrar med en avtakende, alternerende korreksjon som dør ut. Generelt: er en tilstandsvektor selv en egenvektor med egenverdi $0$, betyr det at den bestanden forsvinner allerede ved neste steg, siden $M\vec{v}=0\cdot \vec{v}=\vec{0}$.

Transponering og et signaturbevis

Til slutt et lite, men nyttig faktum: transponert matrisen $A^T$ har akkurat de samme egenverdiene som $A$ selv, selv om egenvektorene som regel er forskjellige. Beviset er kort: determinanten til en matrise er lik determinanten til dens transponerte, så $\det (A-\lambda I)=\det ((A-\lambda I{)}^T)=\det (A^T-\lambda I)$. De to sidene har samme karakteristiske polynom, altså samme røtter.

Det samme sjakkbrett-mønsteret fra kofaktor-utviklingen dukker opp igjen her: fortegnene $(-1{)}^{i+j}$ er symmetriske i $i$ og $j$, så de endres ikke når du transponerer — en av grunnene til at determinant, rang og karakteristisk polynom alle er transponerings-invariante egenskaper, selv om selve matrisen ser helt annerledes ut.

Dette er ikke bare en kuriositet. I anvendelser som Markov-kjeder dukker både $M$ og $M^T$ opp — noen ganger beskriver den ene overgangen mellom tilstander og den andre en tilhørende dualitet — og at de to alltid deler spekter av egenverdier betyr at langtidsoppførselen du regner ut med den ene, sier noe pålitelig om den andre også.