Matematica Discreta - 21

Alla fine il misfatto è compiuto!

Più concentrato del Coccolino, più determinato di Van Damme quando uccidono suo fratello in [film a caso], più fortunato di David e Kathleen Long (come, "chi sono?"), più ladro di Lupin III, ho preso la seconda di due metà del voto in MATEMATICA DISCRETA!

medaglia

Con questo voto si conclude un capitolo della mia vita. Ora posso dire di sapere la matematica, non posso dire di essere Lord Hardy-Littlewood*, ma almeno quando mi danno il resto al supermercato capisco se è giusto.

Per uno come me, che alle medie era appassionato di matematica (più semplice) e poi al liceo Classico è stato assassinato (matematicamente parlando) è una soddisfazione immensa. Il voto - 21 - non rende la grandezza del traguardo per me. Avevo sempre pensato di non meritare il 18, nemmeno studiando dieci anni, e invece sono qui - come sempre dopo un voto sotto il 30 - a pensare che sarei riuscito a fare meglio, se solo...

Stavolta la dea Namagiri mi ha sbirciato e forse suggerito qualche mezza risposta.

* Nowadays, there are only three really great English mathematicians: Hardy,
Littlewood, and Hardy–Littlewood. (Cit. Harald Bohr. No, non Niels, l'altro.)

Da funzione a matrice

Può capitare che abbia un'applicazione lineare. Ecco i passaggi per trasformarla in una matrice, tramite un esempio.

f:R3→R3
e1=(1,0,0)
f(e1) = e1
f(e2) = e1 + e2
f(e3) = e1 - 2e2

Per prima cosa scrivo una matrice in cui ogni regola sta in una colonna:

[11101-2000]

Se devo trovare f(v) per un v qualsiasi, devo solo moltiplicare il vettore di dimensione tre per questa matrice. Per esempio, v = (-2, 7, 9)

[11101-2000]·[-279]=[14-110]

Compito di algebra lineare 25/05/2015 / 5

Esercizio 5

Ricordiamo che ℤ7 è il campo delle classi resto modulo 7. Si risolva il seguente sistema di equazioni lineari a coefficienti in ℤ7 in tre incognite nel campo ℤ7:

{x+y+z=04x+z=1y+2z=-2

Utilizzare il metodo di eliminazione di Gauss o di Cramer (in ogni caso dettagliando ciascun passaggio)

Soluzione

Portare il sistema a matrice:

[ 1110 4011 012-2 ]

R2 ↔ R3

[ 1110 012-2 4011]

R3 → R3 - 4R1

[ 1110 012-2 0-4-31]

R3 → R3 + 4R2

[ 1110 012-2 005-7]

R3 → R3 / 5R3

[ 1110 012-2 001-7/5]

z = -7/5 (immediato)

y = -2z+2 = 24/5

x = -y -z = (-24+7)/5 = -17/5

Compito di algebra lineare del 25 Maggio 2015 / 2

Esercizio 2

Sia φ:ℝ3→ℝ3 la funzione definita dalla legge

[xyz][x+2y-z2x+3z3x+2y+2z]

Si verifichi che φ è un endomorfismo lineare del ℝ-spazio vettoriale ℝ3. Si calcoli dim(ker φ) e si fornisca una base di ker φ alfine di descrivere ker φ esplicitamente. Si dica se φ è o no biiettiva e perché.

Soluzione

Perché φ sia un endomorfismo lineare bisogna che φ(v+w) = φ(v) + φ(w) e che, dato un α∈ℝ, φ(αv) = αφ(v). La seconda condizione implica anche che φ(0)=0.

dim(ker φ) = dim(ℝ3) - dim(ℝ3) = 0

base(ker φ) = (1,0,0), (0,1,0), (0,0,1)

Dal momento che la terza riga è la somma delle altre due, la funzione non è invertibile, quindi non è biiettiva.

Compito di algebra lineare del 25 Maggio 2015 / 1

Esercizio 1

Sia f: ℝ4 → ℝ la funzione lineare definita dalla legge f(x1, x2, x3, x4) = x1 + x2 + x3 + x4. Si dimostri che ker f è un sottospazio vettoriale. Si calcoli dim(ker(f)) e si dia una base di ker f.

ker f è l'insieme dei vettori tali che f(x1, x2, x3, x4) = 0. Il nucleo di un'applicazione lineare è sempre un sottospazio vettoriale.

dim(ker f) è data dalla dimensione dello spazio del dominio meno quella del codominio, quindi dim(ℝ4) - dim(ℝ) = 3.

Una base di ker f è data da tre vettori linearmente indipendenti, per esempio V1=(1, 1, 0, 0), v2 = (0, 0, 1, 0), v3 = (0, 0, 0, 1)

 

Compito di algebra lineare del 14 gennaio 2016 / 2

Esercizio 2

Si considerino le matrici A, B, C

A=[112-1] B=[224k-3] C=[012k-21]

  1. si stabilisca per quale valore di k∈ℝ le matrici A, B, C sono linearmente dipendenti nello spazio vettoriale delle matrici 2x2
  2. Per il valore trovato in (1) esprimere B come combinazione lineare di A e C
  3. Per il valore trovato in (1) determinare la dimensione del sottospazio vettoriale generato da A, B, C

Le tre matrici sono linearmente dipendenti se xA+yB+zC = 0 per x, y, z diversi da zero.

La soluzione è il risultato del sistema

1) a+2b=0

2) a+2b+c = 0

3) 2a+4b+2kc-2c = 0

4) -a+bk-3b+c = 0

5) da 1) e 2) si ottiene che c = 0

6) da 4) si ottiene che a = b(k-3) e da 1) si ottiene che a = -2b, quindi (k-3) = -2 e k = 1

⇒ k = 1

Noto questo, si possono scrivere le matrici con questa forma:

A=[112-1] B'=[224-2] C'=[0101]

B'=[224-2]=2A

Dal momento che A e C sono linearmente indipendenti (il det. della prima è -3, quello della seconda è 0), la dimensione del sottospazio è 2.

Compito di algebra lineare del 14 gennaio 2016 / 1

Esercizio 1

  1. Si verifichi se l'insieme {(3,0,-1), (2,-2,0), (-1,1,1)} è una base dello spazio vettoriale ℝ3 sul campo ℝ
  2. Sia P il vettore di coordiate (1,1,1) rispetto alla base canonica. Si determinino le coordinate di P rispetto alla base del punto a

Soluzione

L'insieme è una base di ℝ3 sul campo ℝ se, dati tre vettori corrispondenti c1 = (3,0,-1), c2 = (2,-2,0), c3 = (-1,1,1), i tre vettori sono linearmente indipendenti.

Sono linearmente dipendenti se esistono tre scalari non nulli s1, s2 , s3 tali che s1c1+s2c2+s3c3 = 0.

Se esistono, gli scalari sono il risultato di questo sistema:

a) 3s1+2s2-s3=0

b) -2s2+s3=0

c) -s1+s3=0

d) per c) si ha che s1=s3

e) per b) si ha che s3= 2s2

f) sostituendo in a) s1 e s3 si ottiene che l'unica soluzione è che tutti s1, s2 , s3 siano zero.

⇒ 1. i vettori sono linearmente indipendenti

Punto chiave: è una base se i vettori sono linearmente indipendenti, cioè se non ci sono scalari <> 0 per cui la somma dei vettori sia zero

La matrice della trasformazione lineare rispetto alle basi suddette è la seguente:

[32-10-21-101]

quindi per trovare le coordinate di P rispetto ad a bisogna risolvere il seguente sistema:

[32-10-21-101][xyz]=[111]

quindi applico Gauss a:

[32-110-211-1011]

Sommo 1/3 della prima riga alla terza:

[32-110-2110232343]

Sommo 1/3 della seconda riga alla terza:

[32-110-21100153]

Ottengo che:

z = 5/3 (immediato)

-2y+z=1y=z-12=53-12=23·12=13

3x + 2y - z = 1 ⇒ 3x = -2 · 1/3 + 5/3 + 1 ⇒ 3x = 2 ⇒ x = 2/3

Punto chiave: la matrice di trasformazione lineare è data dalle tre coordinate in "verticale" in una matrice, affiancate dalle coordinate del punto

 

Nella selva dei nomi dell'algebra / 2

Segue il primo articolo.

Spazio vettoriale

Uno spazio vettoriale è la combinazione di un gruppo abeliano e di un campo.
Il gruppo abeliano rappresenta un insieme di vettori, in cui sono presenti la somma e l'elemento neutro, mentre il campo rappresenta i coefficienti, con somma, prodotto, zero e uno.

Il campo di coefficienti (che chiameremo K) è assimilabile all'insieme dei numeri reali ℝ (ma "funziona" anche con i razionali ℚ) in cui le operazioni sono somma e prodotto, e gli elementi neutri sono zero e uno, a patto che dall'insieme sia escluso lo zero, perché 1/0 non è un'operazione possibile.

Il gruppo abeliano dei vettori (che chiameremo V) è assimilabile all'insieme ℝ con l'operazione di somma e l'elemento neutro zero.

Inoltre è definito un "prodotto esterno", cioè un'operazione per cui VxK→V.

Rispetto al prodotto tra due numeri, il prodotto esterno di uno spazio vettoriale

  • è associativo
  • è distributivo rispetto alla somma
  • ha un elemento di identità ∈ K tale che Vx1V=V
  • non è commutativo

Sottospazio vettoriale

Un sottospazio vettoriale è uno spazio vettoriale sottoinsieme di un altro spazio vettoriale chiuso per il prodotto scalare (cioè se faccio il prodotto scalare in un sottospazio vettoriale, il risultato è incluso nel sottospazio).

Vettori linearmente indipendenti

Due vettori si dicono linearmente dipendenti se esiste un coefficiente a per cui av1 = v2.

L'insieme dei vli determina una base (vedi oltre).

Due segmenti di retta possono definire un piano? Sì, a patto che non siano segmenti della stessa retta! E tre segmenti possono definire uno spazio tridimensionale? Sì, a patto che siano linearmente indipendenti, cioè che tutti e tre i segmenti facciano parte di rette diverse. Se due segmenti fanno parte della stessa retta e il terzo di un'altra, si definisce comunque solo un piano, e se tutte e tre fanno parte della stessa retta... si definisce solo la retta!

Funzione lineare

Siano U, V spazi vettoriali sul campo K

Una funzione lineare f è tale se:

  1. f(x+y) = f(x)+f(y)
  2. f(αx) = αf(x) con α∈K e x ∈U

Rango

Il rango è il numero di righe o colonne tra loro linearmente indipendenti.

Immagine

Data una funzione lineare f:V→W, l'immagine di f è l'insieme di elementi w tali che f(v) = w.
Intuitivamente (non è la definizione "da libro"!!!) è simile al codominio di una funzione.

Kernel

Sia f:U→V una funzione lineare.

Il kernel di f (denotato anche come kerf) è l'insieme di vettori la cui immagine è il vettore nullo.

La dimensione del kernel si può calcolare come dimensione del sottospazio meno la dimensione dell'immagine.

Nella selva dei nomi dell'algebra / 1

Semigruppo

Un insieme S con un'operazione · che si rappresenta con (S, ·). (insieme + operazione = semigruppo)

L'operazione · è detta binaria su S, perché S · S → S

L'operazione · è associativa, cioè (a·b)·c = a·(b·c)

Esempi: la somma in ℕ, il prodotto in ℕ

Monoide

Un monoide è un semigruppo in cui è definito anche un elemento neutro appartenente all'insieme.

Esempi: la somma nei numeri naturali (zero compreso) (ℕ, +, 0), il prodotto nei numeri interi e lo zero (ℤ, ·, 1)

Relazione

Una relazione è un sottoinsieme del prodotto cartesiano tra due insiemi.

Esempi: A = {a, b}, B = {1, 2}, R1 = {(a, 1), (b, 1)} ⊆ A x B

Funzione

Una funzione è una relazione in cui è definita un'associazione tra gli elementi del primo e quelli del secondo insieme.

I due insiemi non sono equivalenti, infatti si scrive A → B, perché a ogni elemento A è associato un solo elemento di B, mentre non è vero il contrario.

Per esempio, y = x2 per x = -2 o x = +2, y è sempre +4 (quindi y può essere "raggiunto" in due modi diversi), mentre invertendo la funzione, √4 dà luogo a due possibili risultati (±2). La funzione y = sin(x) dà un risultato compreso tra -1 e 1 in modo periodico, quindi f(x) = 0 per kπ, con k ∈ ℕ. La sua inversa, arcsin(x), è una funzione solo se è definita in un intervallo (per esempio, ±π).

Iniettività e suriettività sono già state trattate in precedenza.

Semigruppo delle funzioni

Il carattere ∘ rappresenta la composizione di funzioni. In pratica, scrivere fg(x) è come scrivere f(g(x)).

La composizione è associativa, quindi f∘(gh) = (fg)∘h.

Attenzione! La composizione NON è commutativa, quindi fg è diverso da gf!

Monoide delle funzioni

Un monoide di una funzione è definito da una funzione, un'operazione associativa e un elemento neutro.

Per esempio, (f(x) = x2, ∘, f(x) = x+0)

Sottosemigruppo

Un ssg è un sottoinsieme A di un semigruppo B in cui l'operazione ♦ è la stessa e a ♦ b ∈ A

Sottomonoide

Un sm è un sottosemigruppo di un monoide in cui l'elemento neutro appartiene al sottomonoide.

Morfismi

Si dice omomorfismo tra due monoidi (M, +M, 1M) e (N, +N, 1N) una funzione f per cui f(x+My) = f(x)+Nf(y).
È il caso del logaritmo in base e, per cui loge(x*y) = loge(x)+loge(y).

Si dice endomorfismo di un monoide (M, +M, 1M) una funzione f per cui f(x+My) = f(x)+Mf(y). In pratica, è un omomorfismo su se stesso.

Si dice isomorfismo quando il morfismo è biiettivo, cioè formato da due funzioni biiettive.

Si dice automorfismo un isomorfismo di una funzione in se stessa (quindi è un endomorfismo biiettivo).

Gruppi

Un gruppo è un monoide in cui ogni elemento è invertibile.

Per intenderci, (ℤ, +, 0) è un gruppo, perché per ogni x ∈ ℤ esiste un elemento che ne è l'inverso (visto che si parla di somma, -x).

Invece (ℕ, +, 0) no, perché -x non appartiene all'insieme.

Altro esempio: (ℝ, *, 1), dove * è l'operatore di moltiplicazione, non lo è, perché per x=0, l'inverso di x sarebbe 1/0.

Se l'operazione è commutativa, si chiama gruppo abeliano.

Classi resto

Già viste in matematica discreta, una classe resto è un insieme di insiemi in cui tutti gli elementi danno lo stesso resto di una divisione.

Per esempio, ℤ≡ 7 è l'insieme di sette insiemi di resti di una divisione per sette.

Il primo insieme contiene tutti i numeri interi che, divisi per sette danno come resto zero: {0, 7, -7, 14, -14, ...}

Il secondo tutti i numeri che danno resto 1: {1, 8, -6, 15, -13...}

e così via, fino all'insieme di resto sei: {6, -1, 13, -8...}

Anello

Un anello è una struttura con un insieme, due operazioni e un elemento neutro per la prima operazione, per cui vale la proprietà distributiva tra la prima e la seconda operazione.

(ℤ, +, *, 0) è un esempio: a*(b+c) = a*b + a*c

Se anche la seconda operazione ha un elemento neutro, allora si chiama Anello con identità (è necessario che l'elemento neutro della prima e della seconda operazione siano diversi).

Se la seconda operazione è commutativa, allora si dice Anello commutativo.

Campo

Un campo è un anello commutativo con identità in cui ogni elemento non nullo è invertibile.

E poi, si parla di spazi vettoriali...

Semigruppo Insieme, operazione associativa S → S
Monoide Insieme, operazione associativa, elemento neutro S → S, el. neutro ∈ S
Monoide Insieme, operazione associativa, elemento neutro, ogni elemento è invertibile a + (-a) = 0, oppure a * (1/a) = 1 (a∈ℝ\{0})
Relazione Insieme, sottoinsieme di un prodotto cartesiano S ⊆ AxB
Funzione Insieme, sottoinsieme di un prodotto cartesiano in cui ogni elemento in A ha uno e un solo elemento in B S ⊆ AxB
Morfismo Una funzione che va da un monoide a un secondo tale per cui f(x+My) = f(x)+Nf(y) Monoidi: (M, +M, 1M) e (N, +N, 1N)
Gruppo Monoide in cui ogni elemento è invertibile
Anello Insieme,
operazione "somma" commutativa,
operazione "prodotto",
elemento neutro per la prima operazione;
vale la proprietà distributiva
(R, +, *, 0) t.c.
monoide: (R, +, 0)
semigruppo: (R, *)
Campo Insieme,
operazione "somma" commutativa,
operazione "prodotto" commutativa,
elemento neutro per la prima operazione,
elemento neutro per la seconda operazione;
vale la proprietà distributiva, gli elementi neutri sono diversi. Ogni elemento è invertibile.
(R, +, *, 0, 1) t.c.
monoide: (R, +, 0)
monoide: (R, *, 1)