Lezione di algebra e geometria (algoritmi e lemmi )

Spazi vettoriali finitamente generati e algoritmi

V^k è finitamente generato se ∃ {u₁, ..., u_k} k ∈ ℕ / Span (u₁, ..., u_k) = V.

Se V^k ammette una base è finitamente generato.

B = {v₁, ..., v_n} u_i linearmente dipendente e Span (v₁, ..., v_n) = V^k.

Algoritmo di estrazione

Sia {u₁, ... , u_k} una lista di generatori di V. Mediante l'algoritmo estraiamo una base.

• U_k ∈ Span (u₁, ... , u_k-1): sì → lo scartono → lo tengo.
• U_k+1 ∈ Span (u₁, ... , u_k-1): sì → lo scartono → lo tengo.
• U₁ = 0: sì → scartono → tengo.

In ogni passaggio io scarto sempre un vettore superfluo.

Esempio: 3 vettori che formano un generatore di R³.

Base canonica → (1 0 0) (0 1 0) (0 0 1).

Vⁿ è finitamente generato se ∃ {u₁, ..., u_k} k ∈ N / Span(u₁, ..., u_k) = V.

Se Vⁿ ammette una base è finitamente generato.

B = {v₁, ..., v_n} lin. indipendente e Span (v₁, ..., , v_n) = V.

Algoritmo di estrazione

Sia {u₁, ..., u_n} una lista di generatori di V. Mediante l'algoritmo estraiamo una base.

• U_k ∈ Span (u₁, ..., u_k-1)? Sì → lo scartono → lo tengo.

V_k è un generatore superfluo.

• U_k+1 ∈ Span (u₁, ..., u_k+1)? Sì → lo scartono → lo tengo.

V_k+1 è un generatore superfluo di Span (u₁, ..., u_k-1).

• U_k ≠ 0: sì → scartono → tengo.

In ogni passaggio io scarto sempre un vettore superfluo.

Esempio: 3 vettori che formano un generatore di R³.

Base canonica → (1 1 0) (0 1 0) (0 1 1).

Esempio

U = Span (u₄, u₅) = Span {u₁, u₂, u₃, u₄, u₅}.

Applichiamo l'algoritmo del Fondo.

1^o passo: u₅ ∈ Span (u₁, u₂, u₃, u₄).

u₅ = u₁ + u₂. Se SCARTO u₅ (xk appartiene allo Span).

2^o passo: u₄ ∈ Span (u₁, u₂, u₃).

u₄ = a₁u₁ + a₂u₂ + a₃u₃.

a₁ + 3a₃ = 1 ← Impossibile.

a₂ + 3a₂ = 0.

TENGO u₄.

3^o passo: u₃ ∈ Span (u₁, u₂).

u₃ = 3u₁ + 2u₂ SCARTO u₃.

4^o passo: u₂ ∈ Span (u₁) TENGO u₂.

5^o passo: u₁ ≠ 0 TENGO u₁.

B_o = {u₁, u₂, u₄} s.n.r. (spazio vettoriale reale) finitamente generato ₁, ₂ ∈ è possibile trovare una base di che contiene ₁, ₂.

Trovo una qualunque base = {₁, ..., }.

{₁, ₂, ₁, ₂, ..., } en sono generatori di tipico algoritmo di estrazione → Trovo una base.

Algoritmo di completamento

{₁, ₂, ₄}.

(1 0 0 0 0)^T (0 1 0 0 0)^T (0 0 1 0 0)^T (1 0 0 1 0)^T (0 0 0 1 1)^T di ℝ⁴ contenenti ₁, ₂, ₄.

Ci chiediamo se può essere scritto come combinazione lineare.

₁(1 0 0 0 0)^T + ₂ (0 1 0 0 0)^T + ₃ (0 0 1 0 0)^T + ₄ (1 0 0 1 0)^T + ₅ (0 0 0 1 1)^T + ₆ (0 0 0 0 1)^T.

₁ + ₃ + ₅ = 0.

₂ + ₆ = 0.

₃ + ₄ = 0.

₂ = 1.

Abbiamo scoperto.

₅ = -1.

₂ = 1.

Non importa che la soluzione non sia unica (l'importante è trovarla).

e₄ = e₁ - e₂.