2024-10-09

Matriser

Matrismultiplikation fortsättning

Se även: 2024-10-07#Multiplikation

Matrismultiplikation är ej kommutativt.

Sats

Givet att:
$A : m \times n -matris$
$B : n \times r -matris$
$C : r \times s -matris$
$m, n, r, s \in Z_{+}$

Då gäller: $(A B) C = A (B C)$

D.v.s. att den associativa lagen gäller.

Inte från föreläsningen

Produkten av två matriser $A$ och $B$ där $A$ är av typen $m \times n$ och $B$ av typen $n \times p$ är produkten $A B$ av typen $m \times p$ .

Från detta kan vi även få att:

Givet $S : en talföljd som tillåts ha upprepande tal från Z_{+}$ och:

$A_{1} : S_{1} \times S_{2} -matris$
$A_{2} : S_{2} \times S_{3} -matris$
$⋮$
$A_{n} : S_{n} \times S_{n + 1} -matris$

Är produkten $B = \prod_{i = 1}^{n} A_{i}$ alltid definierad och av typen $S_{1} \times S_{n + 1}$ .

Grannmatriser

Grannmatrisen $A$ till grafen $G = (V, E)$ är definierad som:

A = (\begin{matrix} a_{11} & \dots & a_{1 n} \\ ⋮ & ⋮ \\ a_{n 1} & \dots & a_{n n} \end{matrix}) (n \times n -matris)

där $a_{i j} = {\begin{cases} 1, om det finns en riktad kant från nod i till nod j, d.v.s. (i, j) \in E \\ 0, annars, (i, j) \in E \end{cases}$

För oriktad graf: $a_{i j} = {\begin{cases} 1, om det finns en kant från nod i till nod j, d.v.s. (i, j) \in E \\ 0, annars, (i, j) \in E \end{cases}$

En grannmatris för en oriktad graf är alltid symmetrisk.

Symmetri

En matris är symmetrisk om $A_{i j} = A_{j i}$ för alla element i matrisen.

En symmetrisk matris är alltid en kvadratisk matris.

Talteori

Delbarhet

Låt $a, b \in Z$

Vi säger att " $a$ delar $b$ " eller " $a$ är en delare till $b$ " om det finns $m \in Z$ så att $a m = b$

Notation: $a ∣ b$ , $a ∤ b$ ( $a$ delar ej $b$ )

Delbarhet är en relation på $Z$ .

Sats 5.4

$a ∣ 0 \forall a \in Z$
$a ∣ a \forall a \in Z$ (reflexiv)
$(a ∣ b \land b ∣ c) ⟹ a ∣ c \forall a, b, c \in Z$ (transitiv)
$0 ∤ a om a \neq 0$
För $a, b, c \in Z$ gäller:

(a ∣ b \land a ∣ c) ⟺ a ∣ m b + n c \forall m, n \in Z

Sats 5.7

Om $a ∣ b$ och $b ∣ a$ , då gäller $a = b \lor a = - b$

Division med rest

Tag $a, b \in Z_{+}$ . För tillräckligt stort $m \in Z$ gäller

a - (m + 1) b < 0 (Notera: om b>a, gäller det för m=0)

Välj nu $q \in Z$ som det unika elementet i $Z$ så:
$a - (q + 1) b < 0$
$a - q b \geq 0$

Då gäller att

a - (q + 1) b < 0 ⟺ a - q b < b ⟺ a - q b \leq b - 1

D.v.s. $a - q b \geq 0$ , $a - q b \leq b - 1$

Definiera $r = a - q b$
$⟹ a = q b + r$ och $0 \leq r \leq b - 1$

Valet av $q, r$ så att $0 \leq r \leq b - 1$ gäller är unikt (kan bara göras på ett sätt).

Sats 5.9 (Divisionsalgoritmen)

För varje par av positiva heltal $a, b$ , finns två unika heltal $q$ (kvoten) och $r$ (resten) så att:

a = q b + r, 0 \leq r \leq b - 1

Gemensamma delare

Definiera $a, b \in Z$ , inte bägge 0.

En gemensam delare till $a, b$ är ett tal $d \in Z$ så att

d ∣ a \land d ∣ b

Största gemensamma delare

En gemensam delare uppfyller $d \leq m a x {a, - a, b, - b}$
$⟹ det finns en största gemensamma delare till a, b$

Notation: $d = s g d (a, b)$ (Alltid positiv)

Euklides algoritm

För godtyckliga $a, b$ , hur hittar vi $s g d (a, b)$ ?

Sats 5.14

$\forall a \in Z_{+} : s g d (a, 0) = a$
$\forall a, b, n \in Z : s g d (a + n b, b) = s g d (a, b)$

$a, b \in Z_{+}$ , $a \geq b$
Upprepad division med rest (divisionsalgoritmen) ger:

$a = b q_{1} + r_{1}, 0 \leq r_{1} \leq b - 1$
$b = r_{1} q_{2} + r_{2}, 0 \leq r_{2} \leq r_{1} - 1$
$r_{1} = r_{2} q_{3} + r_{3}, 0 \leq r_{3} \leq r_{2} - 1$
$⋮$
$r_{n - 2} = r_{n - 1} q_{n} + r_{n}, 0 \leq r_{n} \leq r_{n - 1} - 1$
$r_{n - 1} = r_{n} q_{n + 1} + 0$

Slutar när resten $r_{n + 1} = 0$ .

För något $n, r_{n}$
Då gäller att $s g d (a, b) = r_{n}$

Exempel 1

$a = 16, b = 12$

$16 = 12 \cdot q_{1} + r_{1} = 12 \cdot 1 + 4$
$12 = 4 \cdot q_{2} + r_{2} = 4 \cdot 3 + 0$

$s g d (a, b) = r_{n} = r_{1} = 4$

Exempel 2

$a = 6, b = 4$

$6 = 4 \cdot q_{1} + r_{1} = 4 \cdot 1 + 2$ <- SGD=2
$4 = 2 \cdot q_{2} + r_{2} = 2 \cdot 2 + 0$ <- Stopp när rest är 0

$s g d (a, b) = r_{1} = 2$

Exempel 3

$a = 876, b = 204$

$876 = 204 \cdot q_{1} + r_{1} = 204 \cdot 4 + 60$
$204 = 60 \cdot q_{2} + r_{2} = 60 \cdot 3 + 24$
$60 = 24 \cdot q_{3} + r_{3} = 24 \cdot 2 + 12$ <- SGD=12
$24 = 12 \cdot q_{4} + r_{4} = 12 \cdot 2 + 0$ <- Stopp när rest är 0