Matematica Discreta III Lezione del giorno 31 marzo 2008 Richiami sulla teoria dei campi e degli spazi vettoriali.

Matematica Discreta III

Lezione del giorno 31 marzo 2008

Richiami sulla teoria dei campi e degli spazi vettoriali.

Ricordiamo che un campo F è un insieme non vuoto dotato di 2 operazioni (indicate formalmente con somma x+y e prodotto xy) tali che

1) F sia un gruppo commutativo rispetto alla somma (valgono la proprietà associativa x+

(y+z)=(x+y)+z x,y,zF e la proprietà commutativa x+y=y+x x,yF; esiste un elemento neutro 0FF tale che x+0F=x xF; per ogni elemento xF esiste un elemento opposto -xF tale che x+(- x)= 0F)

2) F sia un monoide commutativo rispetto al prodotto (valgono la proprietà associativa x(yz)=(xy)z x,y,zF e la proprietà commutativa xy=yx x,yF; esiste un elemento neutro 1FF tale che x1F=x xF)

3) vale la proprietà distributiva x(y+z)=xy+xz x,y,zF

4) per ogni elemento xF, x≠0F esiste un elemento inverso x^-1F tale che xx^-1=1F (se sono verificate solo 1),2),3) si dice che F è semplicemente un anello commutativo con unità).

Esempi di campi sono il campo Q dei numeri razionali e il campo R dei numeri reali rispetto alle usuali operazioni di somma e prodotto.

Per ogni intero n>1, l’insieme Zn = {[0], [1],…., [n-1]} delle classi di congruenza modulo n è un anello commutativo con unità rispetto alle operazioni di somma e prodotto di classi:

[x]+[y] = [x+y] [x][y] = [xy]

L’anello Zn è un campo (finito di cardinalità n) se e solo se n è un numero primo.

Se F è un campo, un F-spazio vettoriale è un insieme non vuoto V (i cui elementi sono detti vettori, mentre gli elementi di F sono detti scalari) in cui è definita un’operazione interna di somma di vettori v+wV (con v,wV) rispetto a cui V è un gruppo commutativo (l’elemento neutro 0V è detto vettore nullo), e in cui è definita un’operazione di prodotto esterno αvV (con αF, vV) che soddisfa le seguenti proprietà:

- (α+β)v=αv+βv α,βF, vV - α(v+w)=αv+αw αF, v,wV - (αβ)v=α(βv) α,βF, vV - 1Fv=v vV

E’ facile verificare che per ogni vettore vV si ha 0Fv=0V .

Per ogni numero naturale n ed ogni campo F, l’insieme Fⁿ = {(α1,….., αn) / αiF} delle n-uple di elementi di F è un F-spazio vettoriale rispetto alle operazioni:

(α1,…..,αn)+(β1,…..,βn)=(α1+β1,…..,αn+βn) α(α1,….., αn)=(αα1,…..,ααn).

Se V è un F-spazio vettoriale e se SV è un sottoinsieme non vuoto, una combinazione lineare di vettori di S a coefficienti in F è un vettore della forma α1v1+…..+ αkvk con αiF, viS (gli αi sono detti coefficienti della combinazione lineare). Un sottoinsieme non vuoto SV è un insieme di vettori linearmente indipendenti se l’unica combinazione lineare di vettori di S a coefficienti in F che dà come risultato il vettore nullo 0V è quella con coefficienti tutti nulli; se invece esiste una combinazione lineare di vettori di S a coefficienti in F non tutti nulli che dà come risultato il vettore nullo 0V, si dice che S è un insieme di vettori linearmente indipendenti. Un sottoinsieme non vuoto SV è un insieme di vettori generatori di V se ogni vettore di V è combinazione lineare di

vettori di S a coefficienti in F. Il sottoinsieme non vuoto SV è una base di V se è un insieme di vettori linearmente indipendenti e generatori.

In ogni F-spazio vettoriale V esiste una base, e tutte le basi di V hanno la stessa cardinalità (detta dimensione di V su F e indicata con dimFV): ci limiteremo sempre al caso di spazi vettoriali di dimensione finita.

Se B={vi}i=1,…,n è una base di V, ogni vettore vV si scrive come combinazione lineare dei vettori vi

a coefficienti in F e tali coefficienti sono univocamente determinanti da v: infatti se v=





i iv

α =



1,..,n i

i iv

β allora



1,..,n i

i i i -β )v

(α =0V da cui αi=βi per ogni i=1,…,n, essendo i vettori {vi}i=1,…,n linearmente indipendenti.

Per ogni numero naturale n ed ogni campo F, un esempio di base dell’F- spazio vettoriale Fⁿ è costituita dagli n vettori ei=(0F,0F,…,1F,…..,0F) con tutti gli elementi nulli tranne l’elemento di posto i che è uguale a 1F : in particolare dimFFⁿ=n.

Se V è un F-spazio vettoriale e se WV è un sottoinsieme non vuoto, W è un F-sottospazio vettoriale di V se W è esso stesso un F-spazio vettoriale rispetto alle operazioni di V.

Se V è un F-spazio vettoriale e se WV è un sottoinsieme non vuoto, W è un F-sottospazio vettoriale di V se e solo se:

- v+wW v,wW

- αvW vW, αF

Ogni sottospazio contiene il vettore nullo 0V .

Se WV è un sottospazio di V si ha sempre dimFW≤ dimFV e inoltre l’eguaglianza dimFW= dimFV vale solo per V=W.

Per ogni numero naturale n ed ogni campo F, considerato l’F- spazio vettoriale Fⁿ, e due vettori v=(α1,…..,αn), w=(β1,…..,βn)Fⁿ, si definisce prodotto scalare di v e w il seguente elemento del campo F:

vw=α1β1+…….+αn βn

Valgono le seguenti proprietà:

- vw=wv v,wV

- (αv)w=v(αw) αF, v,wV - (v+z)w=vw+zw v,w,zV

Se F é un campo, considerata una matrice nxm (n righe , m colonne) ad elementi in F:

M = (αij) i=1,…,n; j=1,….m si può identificare ognuna delle n righe:

Ri = (αi1 ………. αim) i=1,….,n

con un vettore dello spazio F^m, ed ognuna delle m colonne:

Cj =





















nj 1j

α . . α

j=1,….,m

con un vettore dello spazio Fⁿ. Con tale identificazione, date due matrici ad elementi in F:

M = (αij) i=1,…,n; j=1,….m (matrice nxm) T = (βij) i=1,…,m; j=1,….r (matrice mxr)

in cui il numero delle colonne della prima coincide con il numero delle righe della seconda, si definisce il prodotto righe per colonne di M per T uguale alla matrice nxr in cui il generico elemento ij di riga i e colonna j coincide con il prodotto scalare della riga i di M per la colonna j di T:

MT = (ij) dove ij= αi1β1j+…….+αimβmj i=1,…,n; j=1,…..,r

In particolare se M=(α1,…..,αm) è una matrice 1xm (quindi un vettore riga di F^m), e T è una matrice mxr (con r generico) allora si verifica facilmente che il prodotto righe per colonne MT (che è una matrice 1xr dunque un vettore riga di F^r) coincide con la seguente somma:

MT = α1R1+….. αmRm

dove R1,….. , Rm sono i vettori riga della matrice T (quindi coincide con la combinazione lineare dei vettori riga di M avente per coefficienti gli elementi dell’unica riga di M).

Spazi vettoriali sul campo Z2 .

Se rappresentiamo le classi del campo F=Z2={[0], [1]} delle classi di congruenza modulo 2 con i numeri 0, 1, le operazioni di somma e prodotto in tale campo seguono le seguenti regole:

0+0=0, 0+1=1+0=1, 1+1=0, 00=10=01=0, 11=1

In particolare se V è un qualunque Z2-spazio vettoriale, per ogni vettore wV si ha:

w+w =1w+1w=(1+1)w=0w=0V

dunque

w= -w per ogni vettore w.

Inoltre una combinazione lineare dei vettori v1,…..,vkV a coefficienti in Z2 sarà (essendo 0,1 gli unici valori possibili dei coefficienti) semplicemente una somma di alcuni dei vettori v1,…..,vkV (quelli il cui coefficiente è =1), eccetto nel caso in cui tutti i coefficienti siano nulli.

Se V è uno Z2-spazio vettoriale e se WV è un sottoinsieme non vuoto, W è un F-sottospazio vettoriale di V se e solo se è chiuso rispetto alla somma:

v+wW v,wW

perché la seconda proprietà (αvW vW, αF) è certamente verificata da W per α=0,1.

Codici lineari.

Nello studio dei codici (binari) di lunghezza n come sottoinsiemi di {0,1}ⁿ, converremo da ora in poi di identificare l’insieme delle cifre dell’alfabeto binario {0,1} con gli elementi del campo Z2 e le parole di lunghezza n di {0,1}ⁿ con i vettori dello spazio vettoriale Z2n sul campo Z2.

Dunque due parole di lunghezza n in Z2n si sommano bit per bit seguendo le regole dell’operazione di somma in Z2.

Un codice CZ2n è detto codice lineare se C è uno Z2-sottospazio vettoriale di Z2n, e dunque (secondo quanto osservato sopra) se C è chiuso rispetto alla somma di parole:

v+wC v,wC

In particolare ogni codice lineare contiene la parola nulla 0=(00….0) .

Per quanto premesso sugli spazi vettoriali sul campo Z2, per ogni parola wZ2n si ha w= -w . Esempio: il codice di ripetizione di lunghezza n:

C={00….0, 11….1}{0,1}ⁿ

è un codice lineare perché si verifica facilmente essere chiuso rispetto alla somma.

Il codice C={ 00000, 01101, 10110, 11011 } è un codice lineare per gli stessi motivi.

Il codice C={ 00000, 00111, 00100, 11111 } non è un codice lineare perché per esempio:

00111+00100=00011C

Se CZ2n è un codice lineare, essendo C un sottospazio di V=Z2n, si può considerare la sua dimensione come spazio vettoriale su Z2 , detta dimensione del codice : si ha sempre k≤dimFZ2n=n, e k=n se e solo se C= Z2n.

Se k=dimFC, esiste una base di C di cardinalità k:

B = {v1,…..,vk}

ed ogni parola vC si rappresenta come combinazione lineare dei vettori vi a coefficienti in F univocamente determinati: v=α1v1+…..+ αkvk con αi=0,1 (come visto sopra, in pratica ogni parola di C, tranne la parola identicamente nulla, è somma di alcune delle parole della base).

Poiché ogni coefficiente assume 2 valori possibili, il numero di parole in C è 2^k: dunque se k=dimFC, si ha necessariamente C=2^k (in particolare ogni codice lineare ha sempre cardinalità uguale ad una potenza di 2).

Se CZ2n è un codice lineare e se k=dimFC, si ha sempre 1≤k≤n (perché studiamo solo codici di cardinalità >1).

Esempio: il codice di ripetizione di lunghezza n:

C={00….0, 11….1}{0,1}ⁿ

è un codice lineare di cardinalità 2¹ dunque di dimensione k=1: una base è B={11….1}.

Il codice C={ 00000, 01101, 10110, 11011 } è un codice lineare di cardinalità 2² dunque di dimensione k=2: una base è per esempio B={01101, 10110}.

Poiché in un codice lineare la dimensione è strettamente legata alla cardinalità, per un codice lineare C si considerano 3 parametri: lunghezza n, dimensione k, distanza . In tale caso diremo che C è un [n, k, ]-codice lineare (notare che C é anche un (n, 2^k, )-codice nella terminologia dei codici generici) .

In particolare il rateo di informazione di un [n, k, ]-codice lineare è (log22^k)/n=k/n , quindi il rateo di informazione di un codice lineare si ottiene dividendo la dimensione per la lunghezza.

Vedremo ora che in un codice lineare è computazionalmente più semplice il calcolo della distanza

.

Data una parola wZ2n definiamo peso di w il numero (w) dei bits non nulli di w. E’ ovvio che il peso di una parola coincide con la sua distanza dalla parola nulla: (w)=(w,0), e che l’unica parola di peso 0 è la parola nulla.

Teorema.

1) Se v, wZ2n si ha (v,w)=(v+w)

2) Se C è un [n, k, ]-codice lineare, la distanza  di C coincide con il peso minimo di una parola non nulla di C.

Dimostrazione:

1) Il bit in posizione j di v+w si ottiene sommando i corrispondenti bits in posizione j di v, w, dunque è non nullo (cioè =1) se e solo se i corrispondenti bits di v, w sono diversi: si conclude che il numero di bits non nulli di v+w coincide con il numero di bits in cui v, w differiscono, da cui la tesi

2) Sia A l’insieme dei pesi delle parole non nulle di C, e sia B l’insieme delle distanze di parole distinte di C. Dimostriamo che A=B.

Se xA, si ha x=(w) dove wC, w≠0: ma (w)=(w,0)B.

Viceversa se xB, si ha x=(v,w), con v,wC, v≠w, e per la 1) (v,w)=(v+w)B (perché v+wC essendo C lineare, e v+w≠0 essendo v≠w= -w).

Poiché gli elementi minimali di A, B sono rispettivamente il peso minimo di una parola non nulla di C e la distanza  di C, si ottiene la tesi.

Dunque, per un [n, k, ]-codice lineare C di cardinalità m=2^k, il calcolo della distanza  si può effettuare calcolando il peso minimo delle m-1 parole non nulle di C, invece di calcolare la distanza minima fra m(m-1)/2 parole distinte di C.

Esempio: nel codice lineare C={ 00000, 01101, 10110, 11011 } la distanza  è 3, come si vede esaminando i pesi delle 3 parole non nulle (2 di peso 3, e 1 di peso 4).